[Python] 백준, 16234(DFS)

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

16234번: 인구 이동

개요

- 해결법을 고민하다 DFS/BFS 문항이라는 걸 알았다. (감 유지할 겸 아무거나 풀어서 분류를 몰랐다)

- 문제가 혼란스러우나 나름 논리적이다.

- x, y 설정이 난잡하다. 이 문제의 경우 가로, 세로의 배열 길이가 같아서 기준을 어떻게 잡던 상관이 없었지만, 조금 복잡한 문제를 다룰 때는 이 부분을 유의해야 할 것 같다.(풀 때마다 다른 거 같은 느낌)

- 마무리가 낯설다. 간만에 풀어서 그런 것도 있지만 dfs의 순기능을 최대한 이용하는 기분.

 

아이디어

- 거창하게 설명할 아이디어가 없다. 그간 푼 DFS랑 많이 유사하며, 마지막 while문 작성만 조금 생각이 더 필요한 것 같다.

 

# PYTHON CODE

import sys
sys.setrecursionlimit((100000))

n, l, r = map(int, sys.stdin.readline().split())
world = []

for _ in range(n):
    world_list = list(map(int, sys.stdin.readline().split()))
    world.append(world_list)

with_list = []
count = 0


def dfs(a, b):
    visit[a][b] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    for k in range(4):
        nx, ny = a + dx[k], b + dy[k]
        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
            if l <= abs(world[nx][ny] - world[a][b]) <= r:
                with_list.append([nx, ny])
                dfs(nx, ny)
    return with_list


while True:
    visit = [[0] * n for _ in range(n)]
    is_finish = True

    for i in range(n):
        for j in range(n):
            with_list = []
            if visit[i][j] == 0:
                with_list.append([i, j])
                dfs(i, j)

                if len(with_list) > 1:
                    is_finish = False
                    avg = sum([world[x][y] for x, y in with_list]) // len(with_list)
                    for new_x, new_y in with_list:
                        world[new_x][new_y] = avg

    if is_finish:
        break

    count += 1

print(count)