[DFS/BFS] 인구 인동 (BAEKJOON - 16234)

1. 문제

땅의 크기 N

각 영역별로 나라가 존재하고

최소 인구 이동, 최대 인구 이동 범위가 L, R 사이 일 때

인구 이동이 몇번 일어나는가?

2. 입력

# SET - 1
2 20 50
50 30
20 40

# SET - 2
2 40 50
50 30
20 40

# SET - 3
2 20 50
50 30
30 40

# SET - 4
3 5 10
10 15 20
20 30 25
40 22 10

# SET - 5
4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

 

3. 출력

# SET - 1
1

# SET - 2
0

# SET - 3
1

# SET - 4
2

# SET - 5
3

 

4. 풀이

bfs로 확산하는것만 이해하고 같은 그룹으로 묶는거를 까먹었다보니, 푸는데 헤맸다.

나동빛 풀이를보면 참 간단한데, 직접 칠려면 왜이렇게 돌아가는지 모르겠다..

 

전체적으로 돌면서 이미 확인한 부분인지, 아닌지 확인하고 확인한 부분이면 넘어간다.

bfs로 범위 내의 왕국들을 묶어주고 인구를 분배한다.

 

index라는 변수가 왕국 크기 (N*N)이면 모든 경우의수를 확인했다는 것 = 합친 곳이 하나도 없다는 것

이므로 break를 해준다.

 

같은 코드를 Python3로 돌리면 시간초과

Pypy3로 돌리면 정답입니다! ??? 컴파일러에 따라 속도 차이가 나는 것 같다.

5. 코드

N, L, R = map(int, input().split())
data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

FOUR_DIR = [(0,1), (0,-1), (1,0), (-1,0)]

from collections import deque

def bfs(i, j):
    united = [(i, j)]
    q = deque()
    q.append((i, j))
    popul = data[i][j]
    length = 1
    while q:
        x, y = q.popleft()
        for dx, dy in FOUR_DIR:
            nx, ny = x+dx, y+dy
            if 0 <= nx < N and 0 <= ny < N and union[nx][ny] == -1:
                if  L<= abs(data[nx][ny]-data[x][y]) <=R:
                    union[nx][ny] = 0
                    popul += data[nx][ny]
                    length += 1
                    q.append([nx, ny])
                    united.append([nx,ny])
    for a, b in united:
        data[a][b] = popul//length

answer = 0

while True:
    union = [[-1] * N for _ in range(N)]
    index = 0
    for i in range(N):
        for j in range(N):
            if union[i][j] == -1:
                union[i][j] = 0
                bfs(i, j)
                index+=1

    if index == N*N:
        break
    
    answer += 1

print(answer)