Python/BFS BOJ-16234 인구이동

Posted on | In

[Python/BFS] BOJ-16234 인구이동

📌문제링크 풀이참고

*풀이참고 링크에 들어가서 보시면됩니다.

인구이동이 없을 때까지 날짜를 구하는 문제다.

BFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import sys
import math
from collections import deque
input = sys.stdin.readline

def bfs(x,y):
    q = deque([(x,y)])
    visited[x][y] = True
    sumv = board[x][y]
    union= [(x,y)]
    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 :
                if L <= abs(board[nx][ny] - board[x][y]) <= R and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx,ny))
                    union.append((nx,ny))
                    sumv+=board[nx][ny]
    for x,y in union:
            board[x][y] = math.floor(sumv/len(union))
    return len(union)


if __name__ == '__main__':
    N,L,R = map(int,input().split())
    board = [list(map(int,input().split())) for _ in range(N)]
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    result = 0
    while True :
        visited = [[False]*N for _ in range(N)]
        flag =False
        for x in range(N):
            for y in range(N):
                if not visited[x][y]:
                    if bfs(x,y) > 1 :
                        flag = True
        if not flag : # 인구이동이 없을 경우 
            break
        result += 1
    print(result)