[백준] 2468 - 안전 영역 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

2468번: 안전 영역

 

한 지역의 높이 정보가 NXN 배열로 주어지고 비로 인해 물에 잠기지 않은 서로 연결된 영역을 안전 영역이라 할 때, 장마철에 안전 영역의 최대 개수를 구하는 것이 이 문제의 목표입니다.

이 문제에서는 내리는 비의 양은 입력으로 주어지지 않습니다.

하지만, 지역의 높이의 최소 높이와 최대 높이를 알 수 있으므로 비의 양을 적절히 조정하여 테스트를 진행할 수 있습니다.

 

해당 문제는 그래프 탐색 문제로, 저는 너비 우선 탐색(bfs) 방법으로 해결했습니다.

접근 방식

1. 입력된 지역 정보의 높이 정보를 set으로 처리한 후 확인해야 할 비의 양을 구합니다.

2. 비의 양이 지역의 가장 낮은 높이보다 적게 왔을 때 지역 내 모든 곳이 안전 영역이므로 처음 안전 영역의 최대 개수는 1로 저장합니다.

3. (0, 0)부터 (N-1, N-1)까지 모든 지역을 확인하며 현재 확인 지역이 안전 영역이고(현재 지역 높이 > 현재 비의 양) 아직 안전 영역으로 지정이 안됐다면 해당 지역을 너비 우선 탐색을 진행합니다.

3.1 너비 우선 탐색으로 연결된 지역 중 안전 영역을 확인합니다.

4. 모든 구역의 탐색이 끝났다면 현재 안전 영역의 개수와 지금까지 안전 영역의 최대 개수를 비교합니다.

 

전체 코드

제출 언어: Python3

시간: 1464ms

 

import sys
from collections import deque

def search(sr, sc, rain):
    global N, mat, visited, dx, dy

    que = deque([(sr, sc)])

    while que:
        cr, cc = que.popleft()
        
        for i in range(4):
            nr, nc = cr+dy[i], cc+dx[i]

            if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc] and mat[nr][nc] > rain:
                visited[nr][nc] = True
                que.append((nr, nc))
    

if __name__ == "__main__":
    N = int(sys.stdin.readline().strip())

    info = []
    mat = []

    for i in range(N):
        row = list(map(int, sys.stdin.readline().strip().split()))

        info.extend(row)
        mat.append(row)

    info = list(set(info))
    info.sort()

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

    answer = 1

    for rain in info:

        visited = [ [False] * N for _ in range(N) ]
        cnt_safe_zone = 0

        for i in range(N):
            for j in range(N):
                if mat[i][j] > rain and not visited[i][j]:
                    cnt_safe_zone += 1
                    visited[i][j] = True
                    search(i, j, rain)

        answer = max(answer, cnt_safe_zone)
    
    print(answer)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊