[김태원 알고리즘] 안전영역 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

import sys
sys.setrecursionlimit(10**6)

dx, dy = [0,-1,0,1], [1,0,-1,0]
def DFS(x, y, height):
    visited[x][y] = 1
    for w in range(4):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] <= height or visited[xx][yy] == 1:
            continue
        DFS(xx, yy, height)

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

MAX = max(map(max, board)) # ✅ 2차원 리스트 최대값
mx = -2147000000
for H in range(MAX + 1): # ✅ 높이를 0부터 MAX 까지 설정
    visited = [[0] * N for _ in range(N)] # ✅ 매번 초기화 !! 
    cnt = 0
    for i in range(N):
        for j in range(N):
            if board[i][j] <= H or visited[i][j] == 1:
                continue
            cnt += 1
            DFS(i, j, H)
    mx = max(mx, cnt)

print(mx)

• 정답!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기