[Python][백준/BOJ] 2468번 : 안전 영역

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

2468번: 안전 영역

 

내 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

def dfs(x, y, h):
    dx = [1, -1, 0,0]
    dy = [0,0,1,-1]
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if 0 <= nx < n and 0<= ny < n and board[nx][ny] > h and not visited[nx][ny]:
            visited[nx][ny]=1
            dfs(nx, ny, h)
            
answer = 1
for k in range(1, 101):
    visited = [[0]*n for _ in range(n)]
    cnt =0
    for i in range(n):
        for j in range(n):
            if board[i][j] > k and not visited[i][j]:
                cnt+=1
                visited[i][j]=1
                dfs(i, j, k)
    answer = max(cnt, answer)

print(answer)

 

반복문이 한 번 더 필요한 DFS

기존에 풀던 DFS에서 조건이 하나 더 추가된 부분이 있었다.

 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

1. 안전한 영역이 최대가 되는 높이를 찾는다.
2. DFS를 실행해서 해당 높이에 대한 안전 영역의 개수를 구한다.

2번은 기존의 DFS와 같지만, 1번이 까다로웠던 문제였다. 1번을 조금 더 효율적으로 풀 수도 있지만 생각이 나지 않아서 가능한 높이(1~100)를 다 대보는 방식으로 풀었다.

for k in range(1, 101):
    visited = [[0]*n for _ in range(n)]
    cnt =0
    for i in range(n):
        for j in range(n):
            if board[i][j] > k and not visited[i][j]:
                cnt+=1
                visited[i][j]=1
                dfs(i, j, k)
    answer = max(cnt, answer)

그래서 이 부분을 보면 k가 곧 dfs 함수에 들어갈 높이이고, if문을 보면 k보다 큰 부분이 어디인지 세는 것을 볼 수 있다.

높이마다 계속 새롭게 판을 짤 것이므로, visited를 계속 초기화해준다.