[백준] 16234 인구 이동

📖 문제

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

💻 내 코드

import sys
from collections import deque
dx=[-1,1,0,0]
dy=[0,0,-1,1]

N, L, R=map(int, sys.stdin.readline().split())

world=[list(map(int, sys.stdin.readline().split())) for _ in range(N)]
queue = deque()

flag=False
def find(a, b):
    global flag
    cnt=1
    sum=world[a][b]
    tmp=[[a, b]]
    queue.append((a, b))
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<N and not visited[nx][ny]:
                if L<=abs(world[nx][ny]-world[x][y])<=R:
                    visited[nx][ny] = True
                    cnt+=1
                    sum+=world[nx][ny]
                    tmp.append((nx, ny))
                    queue.append([nx,ny])

    if cnt>1:
        res = sum // cnt
        flag=True
        for i, j in tmp:
            world[i][j] = res

total=0

while True:
    visited = [[False] * N for _ in range(N)]
    flag=False

    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                visited[i][j]=True
                find(i, j)
    if not flag:
        break
    total+=1

print(total)

💡 풀이

• bfs 이용함
• visited 배열을 만들어 한번 방문한 곳은 True로 바꾸고, 한 번 다 돌때까지 다시 방문하지 않음
• bfs를 진행하는 함수 안에서 만약 현재 위치에서 한군데 이상 방문했다면 그 위치는 국경이 개방된 것이므로 인구수를 계산하여 새로 지정해줌
• 더 이상 방문이 가능하지 않을 때까지 진행