백준 2468 안전 영역 파이썬

www.acmicpc.net/problem/2468

2468번: 안전 영역

import sys
import copy
sys.setrecursionlimit(10003)
if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    graph = []
    rains = set()
    for i in range(N):
        point = list(map(int, sys.stdin.readline().rstrip().split()))
        graph.append(point)

    for i in range(101):
        rains.add(i)

    def dfs(g, v, h, r):
        if v < 0 or v >= N or h < 0 or h >= N:
            return False
        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        if g[v][h] > r:
            g[v][h] = -1
            for d in direction:
                dfs(g, v+d[0], h+d[1], r)
            return True

        return False

    ans = 0
    for rain in rains:
        temp_graph = copy.deepcopy(graph)
        count = 0
        for i in range(N):
            for j in range(N):
                if dfs(temp_graph, i, j, rain):
                    count += 1

        ans = max(ans, count)

    print(ans)


# 5
# 6 8 2 6 2
# 3 2 3 4 6
# 6 7 3 3 2
# 7 2 5 3 6
# 8 9 5 2 7

DFS로 풀었고, 구현에 그리 어려운 부분은 없었다.

다만, 여러 경우에 대한 처리를 같은 그래프에서 해야하는 경우, 방문처리를 그래프내의 값을 변경할 때, 이전 변경사항이 다음 순회때

영향을 받기 때문에 copy.deepcopy 를 사용하였는데 다음부터는 방문 처리를 하는 배열을 따로 만들어야겠다.

DFS, BFS 는 이해만 하고 있다면 그리디 보다 훨씬 쉬운거같다.