[백준2468/Python] 안전 영역(DFS)

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

DFS문제이다. BFS로도 당연히 풀 수 있지만 지금은 DFS를 파고있기 때문에 DFS로 풀어보았다.

import sys
sys.setrecursionlimit(10000)

def dfs(x, y, k):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if (0<= nx <n) and (0<= ny <n) and not visited[nx][ny] and graph[nx][ny] > k:
            visited[nx][ny] = True
            dfs(nx, ny, k)
                

n = int(input())

graph = []

result = 1

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

for k in range(1, max(map(max, graph))):
    cnt = 0
    visited = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if graph[i][j] > k and not visited[i][j]:
                cnt += 1
                visited[i][j] = True
                dfs(i, j, k)
    result = max(result, cnt)
    
print(result)

• 지도 입력받기(graph)
• 높이에 따라서 for문으로 생성(높이:k)
• 지도 인덱스에 따른 이중for문 생성(i, j)
• 높이에 따라 나뉘어지는 영역 dfs 구현 (이것이 관건...)