백준 16234번 인구 이동 삼성SW역량테스트 (Python)

백준 16234번 인구 이동 문제 바로가기

문제 이해

문제를 간단히 말하면 인접해있는 칸에 써져있는 숫자의 차이가 L이상 R이하라면 그 칸들을 연합이라고 하여 숫자를 모두 더한 값에 연합에 들어간 칸에 개수를 나누고 이를 연합인 칸들에 다시 넣어주면 된다.
이때 더이상 이 연산을 진행할 수 없을 때까지 반복하고 그렇게 반복한 횟수를 출력하는 문제이다.

국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
연합을 해체하고, 모든 국경선을 닫는다.

문제 접근

아무래도 이렇게 지도 구조로 되어있고 완전탐색을 진행해야 하는 문제는 거의 BFS로 풀기 때문에 BFS를 사용해야겠다고 생각하고 시작했다!
문제에 들어가기 앞서 3가지로 나누었다.

• 연합이 될 수 있을지 확인하고 연합이 된다면 이를 저장하기
• 연합의 합을 계산하고 개수로 나누어 각 나라의 인구를 재배치하기
• 소요된 날 계산하기

문제 풀이

연합이 될 수 있을지 확인하고 연합이 된다면 이를 저장하기

하나의 좌표의 상,하,좌,우를 확인하고 연합이 되기 위한 조건에 적합하면 방문표시와 q, 연합에 추가해줬다.
q에 추가된 na,nb는 다시 a,b가 되어 더 이상 연합에 적합한 나라를 찾지 못할 때까지 반복한다.
이렇게 x,y가 속한 연합을 모두 찾으면 연합의 인구를 재배치해야한다.

dx = [1,0,-1,0]
dy = [0,1,0,-1]
def bfs(x,y):
    q.append((x,y))
    union = []
    union.append((x,y))
    while q:
        a,b = q.popleft()
        for i in range(4):
            na = a + dx[i]
            nb = b + dy[i]
            if na>=N or nb>=N or nb<0 or na<0 or visited[na][nb]==1:
                continue
            if R>=abs(pan[a][b]-pan[na][nb])>=L:
                visited[na][nb] = 1
                q.append((na,nb))
                union.append((na,nb))

연합의 합을 계산하고 개수로 나누어 각 나라의 인구를 재배치하기

아래 코드는 BFS에 속해진 코드이다.
sum을 사용해서 연합에 속한 인구를 재배치하고 있다.
여기서 return 0, return 1을 사용한 이유는 소요된 날을 계산하기 위해서 사용되었다.

	if len(union)<=1:
        return 0
    result=sum(pan[a][b] for a,b in union)//len(union)
    for a,b in union:
        pan[a][b] = result
    return 1

소요된 날 계산하기

(0,0) 부터 (N-1,N-1)까지 bfs를 모두 돌린다. 이 때 visited[i][j]=1일 때는 하지 않는다. 이미 연합에 속해져있는 좌표기 때문이다.
bfs에서 return 0또는 return 1을 했는데 이 값을 stop에 더하며 저장한다.
따라서 stop에 0이 아닌 값이 들어간다면 연합이 생성된 나라가 있다는 것이고, stop에 0이 들어간다면 더이상 연합이 생성되지 않는다는 뜻이기에 무한루프를 벗어나게 되며 소요된 날을 출력할 수 있다.

while 1:
    stop = 0
    visited = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0:
                visited[i][j] = 1
                stop += bfs(i,j)
    if stop==0:
        break
    day += 1

제출 코드

import sys
from collections import deque 
N, L, R = map(int, sys.stdin.readline().split())
pan = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# 연합이 될 수 있는지?를 확인하고 만약 된다면 하나로 묶어 인구수/칸의 개수를 구하고 각 칸에 값을 넣는다.
# 이를 연합이 될 수 없을 때까지 반복한다.
# 그 때 소요된 날짜를 출력한다.
q = deque()
dx = [1,0,-1,0]
dy = [0,1,0,-1]
def bfs(x,y):
    q.append((x,y))
    union = []
    union.append((x,y))
    while q:
        a,b = q.popleft()
        for i in range(4):
            na = a + dx[i]
            nb = b + dy[i]
            if na>=N or nb>=N or nb<0 or na<0 or visited[na][nb]==1:
                continue
            if R>=abs(pan[a][b]-pan[na][nb])>=L:
                visited[na][nb] = 1
                q.append((na,nb))
                union.append((na,nb))
    if len(union)<=1:
        return 0
    result=sum(pan[a][b] for a,b in union)//len(union)
    for a,b in union:
        pan[a][b] = result
    return 1
day = 0
while 1:
    stop = 0
    visited = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0:
                visited[i][j] = 1
                stop += bfs(i,j)
    if stop==0:
        break
    day += 1
print(day)