[DFS/BFS] 인구이동

[ericagong]

⭐ 성찰

✅ 🌟 BFS 경로를 저장하기 위해서는 별도의 자료 저장 공간🌟 이 필요함. 매번 큐에 넣을 때마다 저장해주어야 함. ✅ while Ture 형식을 사용할 경우, 종료 조건을 반드시 꼭! 잘 작성해주어야 함. ✅ BFS/DFS를 사용하는 경우, 방문 여부를 확인하기 위한 별도의 저장 공간 visited 가 필요한 경우가 종종 발생함. ✅ BFS/DFS 완전 탐색 시 ⭐ 모든 좌표에 대해 수행할 필요 없이, 방문하지 않은 좌표를 대상으로만 수행⭐ 해 주면 됨.

❓ 문제 상황

인구이동

👨‍💻 문제 해결: BFS

✅ 1차 풀이: 각 BFS 경로를 저장해 풀이

0. 완전 탐색으로 풀 수 있음을 시간 복잡도를 검사하여 확인함
1. 도시의 방문 여부를 별도의 2차원 리스트 visited에서 관리.
2. 각 도시에서 상/하/좌/우의 도시들에 대해, 방문하지 않았고, 국경을 열 수 있는 경우 같은 union으로 처리.
   • ⭐ union을 별도로 두어 BFS의 경로를 저장.
3. 매 BFS가 종료될 때마다 BFS 경로를 unions에 반영해 저장.
4. unions 내의 모든 union에 대해 인구 이동 수행.
   • 단, 매 인구이동이 끝날 때마다 ⭐ visited와 unions 초기화 필요.
5. ⭐ 종료 조건: 아무 union도 생기지 않을 때, 종료 ⭐

   
   # 인구이동 (https://www.acmicpc.net/problem/16234)

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)] visited = [[False] * n for in range(n)]

def can_open(cx, cy, nx, ny): return l <= abs(graph[cx][cy] - graph[nx][ny]) <= r

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

def bfs(x, y): q = deque() union = [] q.append((x, y)) union.append((x, y)) visited[x][y] = True while q: curr = q.popleft() cx, cy = curr for i in range(4): nx = cx + dx[i] ny = cy + dy[i] if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and can_open(cx, cy, nx, ny): q.append((nx, ny)) union.append((nx, ny)) visited[nx][ny] = True unions.append(union)

def move(): for union in unions: if len(union) == 1: continue else: total = 0 for city in union: x, y = city total += graph[x][y] new_pop = int(total / len(union)) for city in union: x, y = city graph[x][y] = new_pop

def log(g):

print('grpah')

for i in range(len(g)):

print('\t', g[i])

print()

cnt = 0 while True: visited = [[False] * n for _ in range(n)] for i in range(n): for j in range(n): if not visited[i][j]: bfs(i, j)

print(unions)

# log(graph)
if len(unions) == n * n:
    break
move()
cnt += 1
unions = []

print(cnt)