BOJ - 인구 이동 16234번 (python)

❓ 문제 - 백준 인구 이동 16234번 - python 풀이법

출처 

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

16234번: 인구 이동

 

 

📝 문제해결법

1. 이 문제의 핵심은 그래프탐색(BFS)로 해결하는 것이다.

• 전체 나라를 탐색을 위한 queue와 국경선을 공유한 것의 지역을 담을 connet queue를 통해 해결
• 한 지역에 대해 국경선 공유할 때 연합인구수와 연합을 이루고 있는 국가 수를 저장하기 위해 count, people 변수 이용
• queue에 존재할 때까지 connet queue에 국경선을 공유하여 연합한 국가들의 위치를 append, 연합인구수(people)에 graph[x][y] 를 더하고 연합을 이루고 있는 국가수(count)를 +1 증가시켜줌
• 4방향을 돌면서 인접한 국가들과의 인구 수 차이(diff)를 계산하여 만약 diff가 주어진 L 이상 R 이하라면 국경선을 공유하기 위하여 visited에 count를 넣어서 방문 처리해주고, q에 국경선을 공유한 위치(nx, ny)를 append
• 국경선이 공유되는지 queue를 통해서 다 확인 후에, 위에서 구한 connet 큐에서 국경선을 공유한 지역에  연합인구수 // 연합을 이루고 있는 개수로 graph 값을 변경시켜줌
• bfs를 돌면서 count 즉, 국경선을 공유한 지역이 없다면 return 0
• bfs를 돌면서 count 즉, 국경선을 공유한 지역이 있다면 return 1

 

2. while 문을 돌면서 방문하지 않은 곳을 q에 append 해주고 모든 지역에 bfs를 돌려서 break_cnt(국경선을 공유한 국가)가 0, 즉 모든 지역이 국경선을 공유하지 않았다면 while을 빠져나가게 하고 만약 국경선을 공유한 국가가 있다면 answer +1 증가 시켜줌

 

 

💻 소스코드

import sys
from collections import deque

input = sys.stdin.readline
n, l, r = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

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

def bfs(a, b):
    connet = deque()
    people, count = 0, 0
    visited[a][b] = 1
    while q:
        x, y = q.popleft()
        connet.append((x, y))
        count += 1
        people += graph[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if visited[nx][ny] == 0:
                    diff = abs(graph[x][y] - graph[nx][ny])
                    if l <= diff <= r:
                        visited[nx][ny] = count
                        q.append((nx, ny))
    while connet:
        x, y = connet.popleft()
        graph[x][y] = (people // count)

    if count == 1:
        return 0
    return 1

answer = 0
while True:
    q = deque()
    break_cnt = 0
    visited = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                q.append((i, j))
                break_cnt += bfs(i, j)
    if break_cnt == 0:
        break
    else:
        answer += 1

print(answer)

 

 

🧐 Ellen's Thinking

문제를 풀 때 체계적으로 구조화를 하자 !!!!