[백준 16234] 인구 이동 (Python)

👩🏻‍💻문제링크

[백준 16234] 인구 이동 (Python)

✍️Idea Sketch

2021-08-09

1. 이번 문제는 80% 에서 시간 초과가 발생해 애를 먹은 문제다.

• Python3에는 약 1000회의 재귀 제한이 있다.
• PyPy3는 재귀 제한 횟수가 더 커서 통과할 수 있었다.

import sys
sys.setrecursionlimit(10**6)

2. BFS와 DFS

• DFS, BFS 둘 중 어느 것을 해도 상관없지만
• BFS로 구현한 사례가 많다.
• 이번에 DFS로 구현해봤는데 재귀 제한으로 애를 많이 먹었다.
• 다시 이 문제를 본다면 BFS로 구현해볼 것.

3. 로직 이해하기

• 로직 이해에 많은 도움이 된 마이구미님 블로그
• dfs(x, y) : 상하좌우 인접한 나라와 인구 차이를 확인한다.
• flag : 인접한 나라가 있는 경우 True를 반환한다.
• main : 연합한 나라의 좌표 group과 총 인구 수 sum을 정의한다.
• exit
  1) 인접한 나라가 있는 경우 False, graph에 인구 이동을 반영한다.
  2) 인접한 나라가 없고 graph 탐색을 끝낸 경우 True, while문을 종료한다.

✍️소스코드

2021-08-09

• Python3로 제출할 경우 80%에서 시간 초과
• PyPy3로 제출할 경우 900ms 통과

import sys

def dfs(x, y):
  global sum
  flag = False
  if (0<=x<n) and (0<=y<n):
    visit[x][y] = 1
    if (0<=x-1<n) and (0<=y<n):
      if visit[x-1][y] == 0:
        if l <= abs(graph[x][y] - graph[x-1][y]) <= r:
          group.append([x-1, y])
          sum += graph[x-1][y]
          flag = True
          dfs(x-1, y)
    if (0<=x+1<n) and (0<=y<n):
      if visit[x+1][y] == 0:
        if l <= abs(graph[x][y] - graph[x+1][y]) <= r:
          group.append([x+1, y])
          sum += graph[x+1][y]
          flag = True
          dfs(x+1, y)
    if (0<=x<n) and (0<=y-1<n):
      if visit[x][y-1] == 0:
        if l <= abs(graph[x][y] - graph[x][y-1]) <= r:
          group.append([x, y-1])
          sum += graph[x][y-1]
          flag = True
          dfs(x, y-1)
    if (0<=x<n) and (0<=y+1<n):
      if visit[x][y+1] == 0:
        if l <= abs(graph[x][y] - graph[x][y+1]) <= r:
          group.append([x, y+1])
          sum += graph[x][y+1]
          flag = True
          dfs(x, y+1)
  return (group, sum, flag)


if __name__ == '__main__':
  n, l, r = map(int, input().split())
  graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
  result = 0

  while True:
    visit = [[0 for _ in range(n)] for _ in range(n)]
    result += 1
    exit = True
    for i in range(n):
      for j in range(n):
        if visit[i][j] == 0:
          group = [[i, j]]
          sum = graph[i][j]
          group, sum, flag = dfs(i, j)
          if flag == True:
            exit = False
            for x, y in group:
              graph[x][y] = int(sum/len(group))
    if exit == True:
      print(result-1)
      break

✍️명답

BFS 로직

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


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


def bfs(y, x):
    global visisted, m
    queue = deque()
    queue.append((y, x))
    sum_val = m[y][x]
    visisted[y][x] = 1
    pos = [(y, x)]

    while queue:
        y, x = queue.popleft()

        for my, mx in zip(dy, dx):
            ny = y + my
            nx = x + mx
            if 0 <= ny < N and 0 <= nx < N and not visisted[ny][nx]:
                if L <= abs(m[ny][nx] - m[y][x]) <= R:
                    visisted[ny][nx] = 1
                    sum_val += m[ny][nx]
                    queue.append((ny, nx))
                    pos.append((ny, nx))

    if len(pos) > 1:  # exist group
        cnt = len(pos)
        mean = sum_val // cnt
        for i in range(cnt):
            y, x = pos[i] 
            m[y][x] = mean
            q.append((y, x))
        return 0
    else:
        return 1


def check(y, x):
    for my, mx in zip(dy, dx):
        ny = y + my
        nx = x + mx
        if 0 <= ny < N and 0 <= nx < N:
            if L <= abs(m[ny][nx] - m[y][x]) <= R:
                return 0
    return 1


N, L, R = map(int, input().split())
m = [[] for _ in range(N)]
q = deque()
for i in range(N):
    m[i] = list(map(int, input().split()))
    for j in range(N):
        q.append((i, j))

cnt = 0
flag = False 

while not flag:
    visisted = [[0] * N for _ in range(N)]
    flag = True
    size = len(q)
    for _ in range(size):
        y, x = q.popleft()
        if visisted[y][x] or check(y, x):
            continue
        if not bfs(y, x):
            flag = False 
    if not flag:
        cnt += 1
print(cnt)