[삼성SW기출문제] 16234번 인구 이동

1. 문제 링크

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

16234번: 인구 이동

 

2. 코드

- 문제 소요 시간: 1시간 37분

import sys
sys.setrecursionlimit(100000)
N, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

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

def dfs(x, y):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < N and not visit[nx][ny]:
            if L <= abs(graph[x][y] - graph[nx][ny]) <= R:
                visit[nx][ny] = True
                union.append([nx, ny])
                dfs(nx, ny)


while True: # 인구 없을 때까지 지속
    visit = [[False for _ in range(N)] for _ in range(N)]
    flag = True

    for i in range(N):
        for j in range(N):
            union = []
            if not visit[i][j]:
                union.append([i, j]) # 시작 나라 저장
                visit[i][j] = True
                dfs(i, j)

                if len(union) > 1:
                    flag = False
                    value = sum(graph[x][y] for x, y in union) // len(union)
                    for x, y in union:
                        graph[x][y] = value

    if flag:
        break

    answer += 1

print(answer)

3. 문제 풀이

- 적용 알고리즘: DFS

- 포인트: 재귀로 구현하려다 보니, total, count 관련해서 제대로 되지 않았음.

 

+ BFS로 풀어보기!!