[BOJ] 16234. 인구 이동

1. 해결방법

"""
1. 아이디어
- 2중 반복문을 통해서 graph[0][0]부터 시작해서 BFS를 돈다.
- 위치를 추가시켜 해당 그래프의 인구 수가 만약 L명 이상 R명 이하면, 방문 기록을 체크하고 큐에 삽입한다.
- 인구 수 이동을 하고 인구수의 평균 값을 구하기 위해 temp라는 배열을 추가해서 인구 이동이 가능한 나라의 위치 값을 append한다.
- while문을 계속 돌때마다 check 방문 기록 체크 배열을 초기화 하고 0, 0위치부터 계속 검사한다.
- 연합된 나라의 총 인구수 / 카운트 로 계산해서 인구수를 이동시킨다. (소수점 버림)
- while문이 끝날 때 마다 answer 지나간 날 +1 을 한다.
"""

 

 

2. 정답 코드

입력 예제(1)

2 20 50
50 30
20 40

출력 예제(1)

1

 

입력 예제(2)

2 40 50
50 30
20 40

출력 예제(2)

0

입력 예제(3)

2 20 50
50 30
30 40

출력 예제(3)

1

 

입력 예제(4)

3 5 10
10 15 20
20 30 25
40 22 10

출력 예제(4)

2

 

입력 예제(5)

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

출력 예제(5)

3

 

코드

import sys
from collections import deque
input = sys.stdin.readline


def bfs(y, x):

    q = deque()
    q.append((y, x))
    check[y][x] = True
    temp = []
    temp.append((y, x))

    while q:
        ey, ex = q.popleft()
        for i in range(4):
            ny = ey + dy[i]
            nx = ex + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                if check[ny][nx] == False:
                    if L <= abs(graph[ey][ex] - graph[ny][nx]) <= R:
                        q.append((ny, nx))
                        check[ny][nx] = True
                        temp.append((ny, nx))

    return temp


# main
N, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

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


while True:
    check = [[False] * N for _ in range(N)]
    is_flag = False
    for i in range(N):
        for j in range(N):
            if check[i][j] == False:
                temp = bfs(i, j)
                if len(temp) > 1:
                    is_flag = True
                    num = sum([graph[y][x] for y, x in temp]) // len(temp)
                    for y, x in temp:
                        graph[y][x] = num

    if is_flag == False:
        break
    answer += 1

print(answer)

 

문제에 대한 아이디어 생각은 어렵지 않았지만, 세부세부에 코드가 들어갈 타이밍을 잘 못잡은 것 같다.특히나, temp를 이용해서 국경선 개방했을 때의 나라 위치 값을 저장해둔 배열이나방문 기록을 while문이 새로 돌 때마다 초기화해줘야 하는 부분에서 많이 삽질한 것 같다.