[이코테/bfs/삼성 기출] 인구 이동(정답, 풀이, 풀리지 않는 의문..)

문제

https://www.acmicpc.net/problem/16234

https://www.acmicpc.net/problem/16234

정답

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]

def process(x,y,index): # 한 연합의 인구이동 로직
    united = [] # 한 연합에 포함되는 나라가 담길 배열. 인구이동 시 필요
    united.append((x,y)) 
    q = deque() # dfs수행. 국경선을 여는 조건에 따라 연합을 확장시키기 위해 사용
    q.append((x,y)) 
    union[x][y] = index # 각 연합을 구분할 인덱스 번호 부여
    summary = graph[x][y]
    count = 1 # 한 연합에 속할 나라 개수

    while q: # 연합이가능한 모든 나라를 연합시키는 작업
        x,y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            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
       
    return count # 인구이동 발생했는지를 체크하기 위한 변수를 return

total_count = 0

while True:
    move = False
    union = [[-1]*n for _ in range(n)] # 전역변수처럼 process함수 안에서 사용이 가능
    index = 0 # 다른 연합들과 구분되는 연합 번호를 매기는 것. 한 번의 이동이 끝나면 초기화됨
    for i in range(n):
        for j in range(n): # 전체 나라를 돌아가며 인구이동. 
            if union[i][j] == -1: # 만약 한 연합의 이동이 끝나고 연합이 된 나라를 다시 이동시키지 않도록 검사
                if process(i,j,index) > 1:
                    move = True
                    index +=1 # 한 연합의 인구이동이 끝났다면 index를 증가시켜 다른 연합을 만듦
    
    if move == False: # 인구이동이 일어나지 않았다면 프로세스 종료
        break

    total_count+=1 # 인구이동이 총 몇 번 일어났는지를 체크하는 변수

print(total_count)

 

풀이

코드에 주석을 달아서 설명했음.

인구이동이 일어나지 않았을 때를 어떻게 뭘로 판단하느냐가 제일 어려웠던 것 같다. 

본문처럼 move변수를 이용해 인구이동 함수 process()를 실행한 후 리턴값으로 각 연합에 속한 나라 수를 설정하는 방법은 쉬웠는데 정답지에는 index == n*n이 될 때 전체 프로그램을 종료시키는 것으로 구현했다.

이 index가 n*n이 되는게 대체 무슨 말인지 이해를 못해서 한참을 고민했는데 결국 알아내지 못함..

hoxy... ㅇㅏ는사람이 있다면 알려주길..  

 

참고

이것이 취업을 위한 코딩테스트다(with.python)