백준 2468 안전 영역 DFS (파이썬)

아이디어

1. 탐색 할 때 추가적으로 높이를 인자로 넣어줘야한다.
2. 높이는 1부터 101까지 이다.
3. for문을 통해 높이를 전달하자.

 

---

풀이 

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(N, h, r, c):
    visited[r][c] = 1
    for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nr, nc = r + di, c + dj
        if 0 <= nr < N and 0 <= nc < N:
            '''
            이 문제는 높이 h이상인 지역을 탐색해야한다.
            '''
            if arr[nr][nc] >= h and visited[nr][nc] == 0:
                dfs(N, h, nr, nc)

N = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split()))for _ in range(N)]


result = 0
for k in range(1, 101):
    visited = [[0]*N for _ in range(N)]
    tmp = 0
    for i in range(N):
        for j in range(N):
            if arr[i][j] >= k and visited[i][j] == 0:   # 높이 k이상인 지역을 탐색
                dfs(N, k, i, j)
                tmp += 1
    if tmp > result:
        result = tmp

print(result)

 

---

후기

이 문제는 비에 잠긴 구역이 아닌, 잠기지 않은 구역을 찾아야 했다. 처음에는 잠긴 구역을 탐색해서 조금 시간낭비했다.

for문을 통해 높이를 전달하는 생각이 맞았다.

현재까지 DFS를 재귀로만 써왔는데, 반복문으로 사용하는게 더 좋다는 말이 있다. 

조금 더 알아보고 반복문이 더 효율적이라면 반복문으로 사용해야겠다.