[BOJ 16234 파이썬] 파이썬 인구이동 BFS문제풀이

 

16234번: 인구 이동

 

전형적인 BFS문제이다.

BFS 탐색 시 처리해주어야할 예외는

국경이 열려있는지를 먼저 처리하고, 열려있을 시에 연합으로 리스트를 만들어주기만 하면 된다.

 

이 문제에서 주의해야할 점은 BFS 한번으로만 끝낼 생각을 하면 안된다는 것이다.

대부분의 dp,DFS 등의 알고리즘들이 단 한번 탐색하고 마는데,

BFS는 이 문제와 비슷하게 여러번 탐색해야하는 경우가 많다.

 

즉, 땅에 대해서 BFS를 진행하는데, BFS를 한번만 하고 끝 나는것이 아니라,

국경에 의해 나눠진 다른 부분도 탐색하여야 하기 때문에

이중 for문을 통해서, 탐색하여 만약 BFS로 탐색하지 않은 곳이 있다면 거기서부터 다시 BFS를 해주어야한다.

 

BFS 함수의 return으로 연합팀의 좌표 리스트를 반환하는데, 이것의 거리가 1이라면 연합이 없는 것이므로,

거리가 1이상일때 check를 false로 만들어준다. 만약 모든 연합이 거리가 1이하라면, 연합이 존재하지 않으므로 며칠지났는지 출력해준다.

 

코드는 다음과 같다.

 

from collections import deque
import sys


#R행 C열 T초 후
N,L,R = map(int,sys.stdin.readline().rstrip().split())

country = []
visited = []

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

for _ in range(N):
    country.append(list(map(int,sys.stdin.readline().rstrip().split())))


def bfs(r,c):
    q = deque()
    q.append([r,c])
    team = []
    team.append([r,c])

    while len(q) != 0:
        y,x = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < N and ny >= 0 and ny < N and not visited[ny][nx]:
                ##국경유무 파악
                if L <= abs(country[ny][nx] - country[y][x]) and abs(country[ny][nx] - country[y][x]) <= R:
                    visited[ny][nx] = True
                    q.append([ny,nx])
                    team.append([ny,nx])
    
    return team



answer = 0

while True:
    visited = [[False] * (N) for _ in range(N)]
    check = True
    for r in range(N):
        for c in range(N):
            
            ##반복해서 연합마다 BFS를 돌려준다.
            if visited[r][c] == False:
                visited[r][c] = True
                t = bfs(r,c)
                
                ##연합의 땅크기가 1 이상일때 check를 False로 바꿔주고 그러한 연합이 없다면 종료
                if len(t) > 1:
                    check = False
                    s = 0
                    for y,x in t:
                        s += country[y][x]
                    for y,x in t:
                        country[y][x] = s // len(t)
                        
    if check:
        break
    answer+=1

print(answer)

 

전형적인 BFS문제 중의 하나인 것 같다.

예외처리가 빡쎄지 않은만큼 연습해보기 좋은 예제인것 같다.👌

 

풀이에 다른 의견이 있으시다면 댓글 남겨주세요!!