DFS/BFS 정복하기 -영역을 구분하는 BFS의 성질 응용-

1. 문제

 

16234번: 인구 이동 (acmicpc.net)

16234번: 인구 이동

 

N*N 크기의 배열에서 인접한 두 칸의 크기 차이가 L이상, R이하이면 연합을 이룬다.

 

모든 연합을 이루게 하고, 크기를 조절한 다음에 이러한 과정을 반복할때, 몇번이나 가능한지 구하는 프로그램을 작성

 

 

2. 풀이

 

문제를 잘 읽어보면 시뮬레이션을 수행해야한다

 

주어진 배열에서 인접한 두 칸의 차이가 L 이상, R 이하인지를 파악한다.

 

그러한 두 칸을 서로 연결하고, 이것을 배열의 모든 칸에 대해 수행하여 서로 연결되는 영역이 얼마나 되는지 구한다

 

그 다음 그 영역의 모든 값은 (영역 값들의 총합)//(영역의 칸 개수)로 조정한다

 

위 과정을 반복하여 언제까지 가능한지 구한다

 

그러면 영역을 구해야하니까 결국 BFS/DFS를 이용해서 "인접한 두 칸의 차이가 L 이상, R 이하"가 어디까지 영역으로 만들어지는지 생각해야하는데

 

내가 알고 있는 BFS로 영역을 만드는 방법을 잘 한번 생각해보면

 

배열의 모든 점 (x,y)에 대해 탐색을 한다

 

(0,0)부터 (n-1,n-1)까지 탐색을 수행할건데,

 

어떤 지점 (a,b)에서 조건을 만족하는 인접한 지점을 찾기만 하면, 그 지점에서 BFS가 끝나면, 하나의 영역이 완성된다.

 

그때 내가 고민했던 부분은 이때 만들어진 영역이 다른 (c,d)에서 만들어지기 시작한 영역과 합쳐질 수 있나? 이거였는데

 

그림그려보면서 조금만 생각해보면 불가능하다는 것을 파악할 수 있다

 

 

그러므로 이제 나의 전략은...

 

1회차에 주어진 배열에서 BFS를 이용해 배열의 모든 점에서 탐색을 시작한다

 

탐색하면서, 값 차이가 L이상 R이하이면 방문 가능하다

 

(a,b)에서 방문 가능한 영역을 찾는 순간, 하나의 연합 1이 완성된다.

 

또 배열의 모든 점에서 순회하다가 (c,d)에서 L이상 R이하이면 방문 가능한 점을 찾기 시작하면, 이 연합은 연합1과는 절대로 같을 수 없고 다른 연합 2가 된다.

 

모든 점 순회가 끝나면, 1회차에 존재하는 모든 연합들을 찾을 수 있다

 

각 연합들의 값 총합을 이용해서 배열의 값을 조정하고, 위 과정을 반복한다

 

-----------------------------------------------------------------

 

먼저 BFS 함수 완성하기

 

시작점 (x,y)와 해당 점에서의 인구값 maps[y][x]를 큐에 저장

 

s는 연합 번호이다.

 

visited를 이용해 연합들을 구분하고자 한다

 

s 연합에 현재 시작점 (x,y)를 넣고, visited에 s로 방문처리한다.

 

cnt는 연합인 칸의 개수이고 pop_sum은 연합들의 인구 합이다. 순회하고나서 나중에 찾지말고, 순회하면서 찾을 것

 

def bfs(x,y,n,l,r,maps,visited,s,union):
    
    queue = deque([(x,y,maps[y][x])])

    visited[y][x] = s

    union[s].append((x,y))

    cnt = 1

    pop_sum = maps[y][x]

    find = False

    while queue:
        
        x,y,p = queue.popleft()

        for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dx = x + ni
            dy = y + nj

            if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1 and visited[dy][dx] == 0:
                
                if abs(p-maps[dy][dx]) >= l and abs(p-maps[dy][dx]) <= r:
                    
                    find = True

                    queue.append((dx,dy,maps[dy][dx]))
                    visited[dy][dx] = s
                    cnt += 1
                    pop_sum += maps[dy][dx]
                    union[s].append((dx,dy))

    if find == False:
        
        union[s] = []

    return visited,union,int(pop_sum/cnt)

 

큐에서 시작점을 빼고 탐색을 시작

 

사방 탐색이 가능하고, 배열안에 존재하면서, visited가 0이면... 방문 가능한 최소조건이다

 

이때, 또 하나의 조건은 이동하고자 하는 점 (dx,dy)의 인구 값 maps[dy][dx]와 현재 점 (x,y)의 인구 값인 p=maps[y][x]의 차이가 L이상 R이하여야한다.

 

그러면 탐색 가능하므로, find를 True로 바꿔서 연합을 찾았다고 표시하자.

 

큐에 넣어주고 방문처리 해주고, 연합의 칸 개수 1 증가시키고, 연합 인구수에 maps[dy][dx]를 더해주고, 연합 union[s]에 append해주고..

 

모든 bfs가 끝나면 연합 s가 완성되는데..

 

만약 반복문이 끝나더라도 find=False이면 연합을 찾지 못한 것이다.

 

그런데 union[s]에는 시작점 (x,y)가 들어가있으니까 빈 연합으로 초기화시키고 return을 하자

 

방문배열 visited, 연합이 들어간 배열 union, 해당 연합의 조정된 인구수 pop_sum/cnt를 모두 return하자

 

n,l,r = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

ans = 0

while 1:
    
    s = 1
    
    visited = [[0]*n for _ in range(n)]

    union = [[] for _ in range(2501)]

    pop_list = []

    for y in range(n):
        
        for x in range(n):
            
            visited,union,pop = bfs(x,y,n,l,r,maps,visited,s,union)

            if union[s] != []:
                
                s += 1

                pop_list.append(pop)
    
    if s == 1:
        
        break

    for i in range(1,s):

        for x,y in union[i]:
            
            maps[y][x] = pop_list[i-1]

    
    ans += 1


print(ans)

 

다음 필요한 입력을 모두 받고 시뮬레이션을 시작하자

 

먼저 s=1은 첫번째 연합을 찾겠다는 초기화

 

visited는 모든 점을 순회하면서 연합을 찾을 때 쓰고자하는 방문 배열

 

union은 연합을 담을 배열인데, 배열 maps의 최대 크기는 50*50이므로 연합은 2500개까지 가능하다

 

근데 n*n으로 해도 될것 같은데?

 

아무튼 이제 모든 점을 순회하기 시작

 

for y in range(n):

    for x in range(n):

        visited,union,pop = bfs(x,y,n,l,r,maps,visited,s,union)

        if union[s] != []:

            s += 1

            pop_list.append(pop)

if s == 1:

    break

 

모든 점에 대해 BFS를 수행하면서, union[s]가 비어있는지 아닌지를 확인하자.

 

비어있지 않다면 연합을 찾았다는 의미이므로 s에 1을 증가시킨다

 

pop_list는 각 연합의 인구수를 조정시키기 위한 값들을 모아놓을 것이다

 

그런데 모든 반복문을 다 돌고서라도 s가 여전히 1이라면, 더 이상 연합을 이룰 수 없는 상태라는 의미다. 그러므로 전체 반복문을 탈출한다

 

    for i in range(1,s):

        for x,y in union[i]:
            
            maps[y][x] = pop_list[i-1]

    
    ans += 1

 

 

반복문을 탈출하지 않았다면 연합은 1번부터 s-1번까지 존재한다(연합을 하나만 찾으면 s=2이고.. 2개 찾으면 s=3이고..)

 

pop_list에 연합 s의 조정된 인구수가 s-1번 index에 존재한다

 

union[s]에는 연합 s의 좌표가 모두 존재한다

 

maps[y][x] = pop_list[i-1]하면 i번 연합의 모든 (x,y)에 조정된 인구수로 바꾸는 작업이 된다.

 

반복문을 탈출하지 않고 이러한 작업을 수행했다면 다음 날로 넘어가야하므로 ans에 1을 더해준다

 

그러면 모든 작업을 초기화하므로 연합 s=1로 초기화하고

 

방문배열도 새로 visited 초기화하고 union도 빈 상태로 초기화하고... 반복문도 완성이 잘 되어있다

 

from collections import deque
from sys import stdin

def bfs(x,y,n,l,r,maps,visited,s,union):
    
    queue = deque([(x,y,maps[y][x])])

    visited[y][x] = s

    union[s].append((x,y))

    cnt = 1

    pop_sum = maps[y][x]

    find = False

    while queue:
        
        x,y,p = queue.popleft()

        for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dx = x + ni
            dy = y + nj

            if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1 and visited[dy][dx] == 0:
                
                if abs(p-maps[dy][dx]) >= l and abs(p-maps[dy][dx]) <= r:
                    
                    find = True

                    queue.append((dx,dy,maps[dy][dx]))
                    visited[dy][dx] = s
                    cnt += 1
                    pop_sum += maps[dy][dx]
                    union[s].append((dx,dy))

    if find == False:
        
        union[s] = []

    return visited,union,int(pop_sum/cnt)



n,l,r = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

ans = 0

while 1:
    
    s = 1
    
    visited = [[0]*n for _ in range(n)]

    union = [[] for _ in range(2501)]

    pop_list = []

    for y in range(n):
        
        for x in range(n):
            
            visited,union,pop = bfs(x,y,n,l,r,maps,visited,s,union)

            if union[s] != []:
                
                s += 1

                pop_list.append(pop)
    
    if s == 1:
        
        break

    for i in range(1,s):

        for x,y in union[i]:
            
            maps[y][x] = pop_list[i-1]

    
    ans += 1


print(ans)

 

 

3. 되돌아보기

 

 

결국 "한 점에서 영역을 찾기 시작하고 BFS가 끝나면, 완전한 하나의 영역이 완성된다" 

 

"이 영역은 다른 점에서 발견하기 시작한 영역과 합쳐질 수 없다"

 

그래서 모든 점에 대해 순회하여 영역을 찾기 시작하면, 매 순간 배열에 존재하는 모든 영역을 찾을 수 있다

 

그러면 시뮬레이션이 가능하겠지 상당히 핵심을 잘 찾았다