16234번: 인구 이동 / gold 5 / 구현, 시뮬레이션

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

16234번: 인구 이동

'''
16234번: 인구 이동 / gold 5 / 구현, 시뮬레이션
'''
import sys

sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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


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


# 입력받기
N, L, R = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

# 시뮬레이션
turn = 0
while True:
    change_graph = False
    visited = [[False for _ in range(N)] for _ in range(N)]
    for x in range(N):
        for y in range(N):
            if not visited[x][y]:
                # 현재 국가 graph[x][y] 와 국경개방 하는 나라 찾기
                graph_info = [[x, y]]
                graph_num = [graph[x][y]]
                # dfs로 국경개방 나라 정보 담기
                dfs(x, y)
                if len(graph_num) >= 2:
                    change_graph = True
                div_num = sum(graph_num) // len(graph_num)
                for p, q in graph_info:
                    graph[p][q] = div_num
    if not change_graph:
        break
    else:
        turn += 1
print(turn)

코드 리뷰

- 해당 문제를 푸는데 약 70분 소요되었고, 정답 판정을 받았습니다. 

 

- 처음에 구현 방식을 너무 디테일하게 설정해서 코드가 길어지다 보니 시간이 많이 소요되었습니다.

(처음 구현 방식)

1. 각 나라 국경선 (가로, 세로) 만들고 -> 둘이 개방해야 하는지 체크해서 국경선 정보 담기 

2. 국경선 정보를 활용해서 그래프 변환 하기 / 이 부분에서 많이 고민하면서 빡 구현하다가 코드가 길어졌습니다.

결국 위 코드와 같이 수정을 했습니다.