인구 이동 [백준 16234번]

문제

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

16234번: 인구 이동

 

내 풀이

 

BFS를 사용해서 국경선을 공유하는 그룹을 찾고, 국경선을 공유하는 그룹에는 몇 개의 나라가 있는지 리턴하는 함수를 만들었다.

 

인구 이동이 며칠 동안 이루어지는지 구해야 하므로 while 반복문을 사용했고, 여기서 while문을 중단시키기 위한 조건이 중요하다.

국경선을 공유하는 그룹이 1개 이상인 경우 flag를 True로 만들었다.

flag가 계속 False라면 인구이동이 이루어지지 않았다는 뜻이므로, 그때 while문을 중단시켰다.

 

import sys
from collections import deque

input = sys.stdin.readline
N, L, R = map(int, input().strip().split())
A = [list(map(int, input().strip().split()))for x in range(N)]
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
check = None

def bfs(i, j):
    num, cnt = A[i][j], 1
    mem = [(i, j)]
    q = deque()
    check[i][j] = True
    q.append((i, j))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if not check[nx][ny] and L <= abs(A[x][y]-A[nx][ny]) <= R:
                    num, cnt = num+A[nx][ny], cnt+1
                    mem.append((nx, ny))
                    check[nx][ny] = True
                    q.append((nx, ny))
    for x, y in mem:
        A[x][y] = int(num//cnt)
    return len(mem)

ans = 0
while True:
    flag = False
    check = [[False]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not check[i][j]:
                if bfs(i, j) > 1:
                    flag = True
    if not flag: break
    ans += 1
print(ans)

 

총평

빡구현!!!