99클럽 코테 스터디 4일차 TIL + DFS

문제

Baekjoon 2468: 안전 영역

• 설명: 영역의 높이가 주어질 때, 안전 영역의 개수를 최대화 하라.

풀이

• 비의 양이 100이 넘어가면 당연히 최대 높이를 넘어가기에 100까지만 비가 온다고 생각해보면

• 모든 위치는 $100 \times 100$개 이고 이를 $0 ~ 100$의 강수량에 따라 안전지역을 Bruteforce로 찾으면

• 충분히 시간 내에 안전지역을 찾을 수 있다.

• 안전지역을 찾는 것은 현재 주어진 강수량을 기준으로 더 큰 값들이 이어지는 개수를 세준다.

  • 이렇게 DFS, BFS를 통해 그래프에서 이어진 부분을 탐지한 후 안전지역의 숫자를 늘려준다.

오늘의 회고

• 모든 지역의 높이가 1이고 비가 하나도 오지 않을 때 답은 1이지만,
• 비가 무조건 올 것이라고 생각하여서 이 경우 1을 반환하여서 틀렸었다.
• 조금 더 엄밀하게 엣지 케이스를 생각하면서 풀어야겠다

Code

# Baekjoon02468.py
import sys
input = sys.stdin.readline

sys.setrecursionlimit(1_000_000)

MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]

n = int(input())

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

def get_safe_area(rain):
    visited = [[False] * n for _ in range(n)]

    def dfs(curr):
        for i, j in MOVES:
            new_row, new_col = curr[0] + i, curr[1] + j

            if (0 <= new_row < n) and (0 <= new_col < n):
                if not visited[new_row][new_col] and area[new_row][new_col] > rain:
                    visited[new_row][new_col] = True
                    dfs((new_row, new_col))

    result = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and area[i][j] > rain:
                visited[i][j] = True
                dfs((i, j))

                result += 1

    return result

ans = 0
for i in range(0, 101):
    ans = max(ans, get_safe_area(i))

print(ans)