[백준 #16234 파이썬] 인구 이동

생각한 방법

전형적인 그래프 탐색이나 bfs 문제라고 생각했다. 바이러스 처럼 퍼지는 유형의 경우 dfs로 활용해서 푸는 것은 뎁스가 너무 깊어지기 때문에 이부분은 미리 배제하고 시작했다. 전형적인 bfs 풀이 방식으로 계획해야겠다고 생각한 이후 더 생각해야 하는 부분을 고려했다.

 

1. 전체 탐색

그래프에 있는 모든 값과 그를 중심으로 한 주변 값의 차이를 조사해야 한다. 어디에서 인구 이동이 일어날 지는 예측할 수 없으므로 모든 값에 대한 bfs 탐색이 필요하다.

2. 전체 탐색의 반복

인구 이동은 2일 이상 소요될 수 있다. 인구 이동이 일어난 이후 인구 이동이 일어난 지역과 일어나지 않았던 지역끼리 다시 비교해보면 새로운 인구 이동의 가능성이 있을 수 있다. 그러므로 bfs는 반복되어야 한다.

3. 방문 여부의 탐색 

매일 방문 여부를 고려한다. bfs 탐색 과정에 있어서 중복이 발생할 수 있다. 이 점을 고려하여 탐색 과정에서 내가 해당 위치를 방문했는지 점검하고 변경하는 과정이 필요하다. 물론, 하루가 지나면 이는 모두 초기회되어야 한다는 점도 잊지 말아야 한다. 

4. flag 활용

항상  생각해보아야 하는 문제다. for문을 다 돌았음에도 bfs가 실행이 되었는지, 안되었는지 판단해야 하는 요소가 필요하다. 이는 flag를 1로 바꾸어 주면서 표현을 한다. 이는 for - else문으로도 대체되는 경우도 본 적이 있는데 이 경우에도 적용이 되는 지는 조금 더 고민해봐야 한다.

 

 

from collections import deque

n,l,r = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

dx = [0,0,-1,1]
dy = [-1,1,0,0]
day = 0

def bfs(a,b):
    q = deque()
    q.append([a,b])
    t = []
    t.append([a,b])
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx, ny = dx[i]+x,dy[i]+y
            if 0<=nx<n and 0<=ny<n and visited[nx][ny]==0:
                if l <= abs(graph[x][y] - graph[nx][ny]) <= r:
                    visited[nx][ny] = 1
                    q.append([nx,ny])
                    t.append([nx,ny])
    return t

           
while 1:
    visited = [[0]*n for _ in range(n)]
    flag = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                visited[i][j] = 1
                country = bfs(i,j)
                if len(country) >= 2:
                    flag = 1
                    number = sum([graph[x][y] for x, y in country]) // len(country)
                    for x,y in country:
                        graph[x][y] = number
    if flag == 0:
        break
    day += 1
print(day)