[백준] 2468: 안전 영역 python 구현 / BFS

한 번에 맞췄다 !!! 

나름 기념적이라 기록

문제

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

 

풀이

BFS로 풀었다 ! 

해당 문제에 노트를 확인해보면 "아무 지역도 물에 잠기지 않을 수도 있다" 라고 표기되어 있습니다 ! 

따라서 탐색 기준이 되는 수위를 0부터 시작하는 것이 문제의 포인트가 됩니다ㅎㅎ

 

CODE

import sys
from collections import deque

def bfs(st_point):
    queue = deque()
    queue.append(st_point)
    safety_map[st_point[0]][st_point[1]] = 0 # 방문처리

    # 방향설정: → ← ↑ ↓
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    while queue: # queue 가 빌때 까지
        now = queue.popleft() # queue에서 꺼냄
        x, y = now

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #지역 벗어나면 pass
            if nx<0 or ny<0 or nx>(n-1) or ny>(n-1): continue
            # 안전지대인 경우 
            if safety_map[nx][ny]:
                queue.append((nx, ny))
                safety_map[nx][ny] = 0

n = int(input())
Map = []
for _ in range(n):
    Map.append(list(map(int, sys.stdin.readline().split())))

local_max = 0
search = max([max(a) for a in Map])
for s in range(search): # 탐색 기준 (수위)
    # 잠긴지역 0 안잠긴지역 1
    safety_map = [[1 if i>s else 0 for i in m] for m in Map]

    local_cnt = 0
    for i in range(n):
        for j in range(n):
            # 안전 영역이라면 개수를 셈
            if safety_map[i][j]:
                local_cnt += 1
                bfs((i, j))

    if local_cnt > local_max:
        local_max = local_cnt

print(local_max)