[백준] 2468번 안전영역 (파이썬)

문제

 

2468번: 안전 영역

비에 잠기지 않는 지역을 구하는 문제이다.

개인적인 문제 포인트는 비에 완전히 잠기지 않는 0도 고려를 해줘야한다는 점이다.

코드

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

def dfs(graph, x, y, visited, I):
    for _ in range(4):
        nx = x + dx[_]
        ny = y + dy[_]

        if  0 <= nx < N and 0 <= ny < N and graph[nx][ny] > I and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(graph, nx, ny, visited, I)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())

graph = []
big = 0
small = 100

for _ in range(N):
    n = list(map(int, input().split()))
    graph.append(n)
    m = max(n)

    big = max(m, big)

maxi = 0
for I in range(0, big + 1):
    visited =[[False] * N for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j] and graph[i][j] > I:
                visited[i][j] = True
                dfs(graph, i, j, visited, I)
                cnt += 1
                maxi = max(maxi, cnt)

print(maxi)

해설

DFS를 사용해서 풀이했다.

가장 높은 지대를 구해주고 0부터 높은지대 까지 for로 돈다.

처음엔 같은 지대를 돌지 않도록 걸어줬었는데, 함수에 카운트 하여 함수에 들어가야하는데 들어가지 않았었다. 지워주니 정상 작동했다.