2468. 안전영역 - 파이썬. BFS

2468. 안전영역

 

사용한 알고리즘, 자료구조 및 기법

1. BFS, 큐
2. 델타를 이용한 2차원 배열 완전탐색

접근 방식

1. BFS로 순회. '수위'와 '건물의 높이'를 각 수행마다 비교하며 '구역'의 넓이를 구해야 한다.

2. 수위: 가장 낮은 건물의 높이보다 1 낮을 때~ 가장 높은 건물의 높이와 같을 때까지 모든 경우의 수를 완전탐색.

문제 특이사항

탐색 시작 / 끝 조건 설정이 헷갈릴 수 있다.

어려웠던 점

1. 종료조건의 설정: 높이가 올라갈수록 '구역'의 갯수가 수위에 따라 지속적으로 증가하다가 감소한다고 생각해서 아래와 같은 전제를 짜고 풀었다가 오답 처리당했다.

종료조건: 모두 물에 잠기거나

높이가 상승했을 때 '구역'의 갯수가 이전보다 줄었을 때.

느낀 점 

좀 더 범용성 있는 방식으로 구현한 후 시간 복잡도를 줄이는건 어떨까?

풀었을 당시의 백준 티어

골드 5, 21-09-16

 

from collections import deque # BFS를 위해 deque import
import sys # 빠른 입출력을 위해 sys import
input = sys.stdin.readline # 빠른 입출격을 쉽게 사용하기 위함.

# 3. 연산
def bfs(starting_point):
    # 3-1. BFS시작점
    Q = deque() # 큐 선언 후
    Q.append(starting_point) # '시작점'을 큐에 삽입.

    while Q: # 큐가 비어있지 않을 때
        y, x = Q.popleft() # 좌표를 확인.

        for i in range(4): # 각각 이동한 후의 새로운 좌표값.
            ny = y + dy[i] # 상, 하, 좌, 우
            nx = x + dx[i] # 상, 하, 좌, 우


            # 1) 지도의 번호를 벗어나지 않고
            # 2) 아직 방문하지 않았으며
            # 3) '수위'보다 높은 구역일 때
            if 0 <= ny < N and 0 <= nx < N\
                and not visited[ny][nx]\
                and sq_lst[ny][nx] > water_level:

                Q.append([ny, nx]) # Q에 더해준 후
                visited[ny][nx] = 1 # 방문 표시.


# 델타 선언 -  상 하 좌 우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


# 1. 입력

N = int(input()) # 지도의 한 변의 길이
sq_lst = [] # 지도 받을 빈 리스트
min_heights = 101 # 가장 낮은 건물 높이
max_heights = 0 # 가장 높은 건물 높이

for i in range(N): # 한번에 한 행씩
    ipt = list(map(int, input().split())) # 값을 입력받아
    sq_lst.append(ipt) # 지도에 더해줌

    mx = max(ipt) # 건물 높이의 최대값과
    mn = min(ipt) # 건물 높이의 최소값을

    if mx > max_heights: # 비교 후
        max_heights = mx # 갱신

    if mn < min_heights: # 비교 후
        min_heights = mn # 갱신(2)

# 2. 선언
mx_area = 0 # '구역'의 갯수 최댓값

for water_level in range(min_heights-1, max_heights+1): # 해당 경우의 수를 분석.
    area = 0 # 현재 구역의 수
    visited = [[False]*N for _ in range(N)] # 방문 리스트 선언

    for i in range(N): # 2차원 배열을
        for j in range(N): # 완전탐색 하며
            if not visited[i][j] \
                    and sq_lst[i][j] > water_level: # 방문하지 않았고
                                                    # 수위보다 높은 지점을
                visited[i][j] = 1 # 방문 표시 후
                bfs([i, j]) # BFS 연산
                area += 1 # BFS가 한 번 시행될 때마다 구역의 갯수 1개 가산.

    if area > mx_area: # 구역의 갯수 최대값을
        mx_area = area # 갱신 (필요시)

# 4. 출력
print(mx_area)