[파이썬/Python] 백준 2468번: 안전 영역

숨·2024년 7월 16일

코테

알고리즘 문제 풀이

목록 보기

34/105

📌 문제 : 백준 2468번

📌 문제 탐색하기

N : 정점의 수 (2 ≤ N ≤ 100)

✅ 입력 조건
1. N 입력
2. N번 반복해 N개의 높이 정보 입력
✅ 출력 조건
1. 물에 잠기지 않는 안전한 영역의 최대 개수 출력

지역의 높이 정보를 통해 물에 잠기지 않는 안전 영역이 최대 몇 개 만들어지는 찾는 문제이다.

내리는 비의 양에 따라 일정 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.
경우에 따라 아무 지역도 물에 잠기지 않을 수 있다고 한다.

물에 잠기지 않는 안전 영역이란,
물에 잠기지 않은 지점이 위, 아래, 오른쪽, 왼쪽으로 인접하며 그 크기가 최대인 영역을 의미한다.

비의 양에 따라 잠기는 높이가 따로 주어지지 않으므로 입력 받은 높이 정보 중 최댓값을 구한다.
0부터 최대 높이까지 직접 잠기는 높이를 지정하여 해당 높이마다 안전 영역이 몇개 생기는지 계산한다.

하나의 노드를 탐색할 때 위, 아래, 오른쪽, 왼쪽을 모두 확인해야 하므로 N*N 크기 내에서 4가지 방향을 이동할 수 있도록 한다.

재귀로 인해 발생할 수 있는 문제를 피하고자 BFS를 구현하였다.
해당 지역을 방문 처리해주며,
1) 위, 아래, 오른쪽, 왼쪽에 연결된 지역 중 방문 처리가 안되었고
2) N*N 내에 있으며
3) 잠기는 높이보다 위에 있는 지역
이 있는지 확인하며 BFS를 수행하도록 한다.

0부터 최대 높이까지 잠기는 높이 제한을 두고,
N*N 영역을 이중 for문을 통해 돌면서 탐색을 수행한다.
한번 탐색이 끝났다는 것은 안전 영역 1개를 찾았다고 할 수 있으므로 안전 영역 개수를 1 증가시킨다.

위의 탐색 과정을 반복하면서 안전 영역 개수가 최대가 되도록 갱신한다.

가능한 시간복잡도

그래프 저장 → $O(N^2)$
최대 높이 계산 → $O(N^2)$
0부터 최대 높이까지 N*N에서 BFS 수행 → $O(N^2*N^2) = O(N^4)$

최종 시간복잡도
$O(N^4)$ 으로 최악의 경우, N이 최대 100일 때
$O(100,000,000)$ 이 되어 1초 내로 계산이 가능할 것 같다.

알고리즘 선택

전체 지역 높이에서 최대 높이를 구하고
0부터 최대 높이까지 전체 지역을 돌며 BFS 수행하기

📌 코드 설계하기

N 입력
N번 반복해 높이 정보 저장
잠기는 높이 리스트 정의
bfs 구현
N*N에서 bfs 수행해 최대 개수 찾기
원하는 형식으로 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# 1. N 입력
N = int(input())

# 2. N번 반복해 높이 정보 저장
heights = [list(map(int, input().split())) for _ in range(N)]

# 3. 잠기는 높이 리스트 정의
max_height = max(max(height) for height in heights)

# 4. 최대 안전 지역 개수 초기화
max_safe_zones = 0

# 5. 상하좌우 이동 방법 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 4. bfs 구현
def bfs(x, y, visited, heights, limit):
    queue = deque([(x, y)])
    # 방문 처리
    visited[x][y] = 1
    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        # 4가지 방향 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 범위 내에서 방문 처리 안된 곳이 있는지 확인
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and heights[nx][ny] > limit:
                visited[nx][ny] = 1
                queue.append((nx, ny))


# 6. N*N에서 bfs 수행해 최대 개수 찾기
for limit in range(max_height + 1):
    visited = [[0] * N for _ in range(N)]
    safe_zones = 0

    for i in range(N):
        for j in range(N):
            if heights[i][j] > limit and not visited[i][j]:
                bfs(i, j, visited, heights, limit)
                safe_zones += 1

    max_safe_zones = max(max_safe_zones, safe_zones)

# 7. 원하는 형식으로 출력
print(max_safe_zones)