[DFS/BFS] 인구이동

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 2시간

1. 문제 설명

- 각 나라의 인구수가 주어지고, 해당 나라들의 국경을 허물고 인구를 이동할 수 있을 때, 인구를 이동한 횟수는 얼마인지 묻는 문제

2. 접근 방식

- DFS를 이용하는 문제인 줄 알고 재귀적으로 접근하려고 했으나 실패했다.

- 후에 제한 시간이 초과되어 해답을 봤는데, BFS로 코드를 구현하고 있었다. 

- BFS로 코드를 구현하고, 주어진 input의 길이가 한정적이기 때문에 완전탐색이 가능하다. 특히 인구이동을 할 때마다 값이 달라지기 떄문에 계속해서 while 문과 for문을 돌면서 값을 점검해야 했다.

3. 코드

from collections import deque

n, l, r = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
    
dx = [-1, 0, 1, 0] # 행
dy = [0, 1, 0, -1] # 열

result = 0

# 특정 위치에서 출발해 모든 연합을 체크한 뒤에 데이터 갱신

def process(x, y, index):
    # (x, y)의 위치와 연결된 연합 정보를 담는 리스트
    united = []
    united.append((x, y))
    # 너비 우선 탐색을 위한 큐 자료구조 정의
    q = deque()
    q.append((x, y))
    union[x][y] = index # 현재 연합의 번호 할당
    summary = graph[x][y] # 현재 연합의 전체 인구 수
    count = 1 # 현재 연합 수
    
    while q:
        x, y = q.popleft()
        # 현재 위치에서 4가지 방향 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 바로 옆에 있는 나라 확인해서 -1이라면
            if 0 <= nx < n and 0 <= ny < n and union[nx][ny]== -1:
                if l<= abs(graph[nx][ny] - graph[x][y]) <=r:
                    q.append((nx, ny)) # 연합에 추가
                    union[nx][ny] = index
                    summary += graph[nx][ny]
                    count+=1
                    united.append((nx, ny))
    # 연합 국가끼리 인구를 분배
    for i, j in united:
        graph[i][j] = summary // count    
        
        
total_count = 0
# 더 이상 인구 이동을 할 수 없을 때까지 반복
while True:
    union = [[-1]*n for _ in range(n)]
    index = 0
    for i in range(n):
        for j in range(n):
            if union[i][j] == -1: #해당 나라가 아직 처리되지 않았다면
                process(i, j, index)
                index += 1
    # 모든 인구 이동이 끝난 경우
    if index == n * n: # union의 모든 index가 순차적으로 들어가야만 break가 되겠구나...
        break   
    total_count += 1
print(total_count)

4. 코멘트

- 해당 코드의 경우 해답 코드를 보면서 일부 이해가 안되는 코드들이 있어서 그 부분을 이해하는데 시간을 좀 썼다.

- 초기 해답 코드에는  함수에 대한 리턴 값이 존재해서 그 리턴값의 존재 유무를 생각하느라 시간을 좀 썼고, 마지막 while True문의 break 조건문을 이해하는데 시간을 좀 많이 썼던 것 같다.

- 결국 index == n*n이라는 조건이 성립하기 위해서는 union[i][j]의 값이 모두 -1로 유지가 된 상태로 for문을 빠져나와야 한다. 그리고 process함수를 여러번 거쳐서 더 이상 graph에서 주어진 조건에 맞는 부분이 없다면 break로 나오게 되는 것이다. 

- 아직 큰 그림을 보는데 익숙하지 않은 것 같다...조금 더 시선을 크게 가질 필요가 있을 것 같다.