DFS - 장마철 안전영역 최대수 (백준 2468)

필기를 해보는 건 나한테 너무 필요한 작업이다. 손으로 정리해보면 괜히 정리가 다 된 것 같다는 느낌적인 느낌이 들 때도 있지만,, 역시나 이번에도 손-단계에서는 빠뜨렸던 부분이 아주 퐁퐁 나왔다^--^

'아니 왜 안 될까?' 하다가 디버깅해보면,, 아래 빨간 색처럼 visited 배열만 만들어놓고 조건에서 안 썼다든가 하는, 나의 엉성과 멍청을 깨닫는다ㅎㅎ (친절한 파이참 덕분에 디버깅 해볼 수 있어서 다행이다)

import sys
sys.setrecursionlimit(10**6) ## 제출시에는 recursion error 나오길래 백준의 안내에 따라 이 친구 추가해주었다.
n = int(input())
area = []
for _ in range(n):
    row = map(int, sys.stdin.readline().split())
    area.append(list(row))

max_h = 0
for row in area:
    if max(row) > max_h:
        max_h = max(row)

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

def DFS(x, y):
    global rain
    if area[x][y] <= rain:
        return
    else:
        visited[x][y] = 1
        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]
            if 0 <= new_x < n and 0 <= new_y < n and area[new_x][new_y] > rain and visited[new_x][new_y] == 0:
                DFS(new_x, new_y)

max_ans = 0
for rain in range(max_h):
    visited = [[0] * n for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(n):
            if area[i][j] > rain and visited[i][j] == 0:
                DFS(i,j)
                count += 1
    if count > max_ans:
        max_ans = count
print(max_ans)

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

2468번: 안전 영역

+ 궁금한 점

sys.setrecursionlimit(10**6) 이거 안 썼을 때는 recursion error 였다.

아무튼 엄청 많이 depth를 들어가는 건 좋은 것 같지 않은데(아닌가? 사실 아직 잘 모르겠다)

재귀를 쓰더라도 더 효율적인 방법을 할 수 있을지(가지치기?), 아니면 재귀가 아닌 방법으로 풀 수 있을지 궁금하다.

(다른 분들 코드를 봐야지!)