[BOJ 2468] 안전 영역(Python)

문제

안전 영역

---

문제 해설

BFS 또는 DFS를 활용하는 문제입니다. DFS로 풀었지만 백준 내 재귀 함수의 깊이가 1000으로 고정되어있어 DFS로 푸시려면 sys.setrecursionlimit(100000)를 작성하여 깊이 제한을 풀어야합니다.

1. 최고 지점을 구한다.
2. 물을 1부터 최고 지점까지 높이며 2차원 리스트를 완전탐색한다.
3. 물보다 높은 지점을 발견하면 그 지점에서 DFS를 진행하여 물보다 높은 지점을 모두 구해준다.
4. DFS가 끝나면 안전 영역이 하나 구해진 것이므로 3. 반복

BFS로 푸는 방법은 다음과 같습니다.

1. 물을 1부터 최고 지점까지 높입니다.
2. 모든 지점을 탐색하여 물에 잠기는 영역을 bfs탐색으로 체크합니다.
3. 모든 지점을 탐색하여 안전영역이 몇개인지 체크합니다.

저는 여기서 안전영역을 구할 때 물의 높이에 따라 체크 리스트를 계속 초기화 했지만, 그럴 필요 없이 방문 체크 리스트 처럼 처음에 선언해놓고 써도 될 것 같습니다.

---

풀이 코드(DFS)

import sys
import copy

sys.setrecursionlimit(100000)
input = sys.stdin.readline
n = int(input())
high = -1  # 최대 높이
answer = 1
graph = []
arr = [[False] * n for _ in range(n)]

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

for i in range(n):
    for j in range(n):
        high = max(high, graph[i][j])


def dfs(height, visited, x, y):
    global n
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -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] > height
        ):
            visited[nx][ny] = True
            dfs(height, visited, nx, ny)


for height in range(1, high):
    visited = copy.deepcopy(arr)
    cnt = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > height and not visited[i][j]:
                cnt += 1
                # dfs로 물에 잠기지 않은 영역 구하기
                dfs(height, visited, i, j)
    answer = max(cnt, answer)
print(answer)

---

풀이 코드(BFS)

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
max_value = 0
answer = 1
for i in range(n):
    for j in range(n):
        max_value = max(max_value, board[i][j])

# 해당 높이 이하는 반드시 체크
# command 0 = 물에 잠기는 영역 체크 1 = 안전영역 체크
def bfs(x, y, height, safezone, command):
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -1
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if command == 0 and not visited[nx][ny] and board[nx][ny] <= height:
                    visited[nx][ny] = True
                    q.append((nx, ny))
                if command == 1 and not safezone[nx][ny] and board[nx][ny] > height:
                    safezone[nx][ny] = True
                    q.append((nx, ny))


for day in range(1, max_value):
    safezone = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # 물에 잠기는지 체크
            if not visited[i][j] and board[i][j] <= day:
                visited[i][j] = True
                bfs(i, j, day, safezone, 0)
    cnt = 0
    for i in range(n):
        for j in range(n):
            # 안전영역이 몇개인지 체크
            if not safezone[i][j] and board[i][j] > day:
                safezone[i][j] = True
                bfs(i, j, day, safezone, 1)
                cnt += 1
    answer = max(answer, cnt)
print(answer)