[백준 2468] 안전 영역 파이썬 풀이 - BFS

문제

문제 링크 : 백준 2468

---

접근

BFS DFS 모두 가능하다고 생각한다.
그러나 경로를 찾는 문제가 아니기 때문에 상대적으로 속도가 빠른 BFS로 풀었다.

생각한 풀이는

1. 우선 높이의 최대를 확인한 후에 높이가 제일 낮을 때부터 최대 높이까지 물을 채워서 확인한다.
2. 하나씩 확인해서 물이 차지 않는 영역을 너비우선탐색으로 해당높이보다 크면 1을 체크하고 영역 카운트한다.
   그리고 낮거나 같으면 0인 상태로 둔다.
3. 현재 체크하는 높이에서 영역 탐색을 마쳤다면 카운트한 영역을 case에 포함한다.
4. 최대 높이 전까지 위를 반복한다. 어차피 최대 높이까지 찼다면 최대 영역은 0이기때문이다.
5. 포함된 case 리스트에서 최대인 영역을 추출한다.

---

풀이

위 접근을 통해 그림으로 푸는 방식을 표현해봤다.

과정

따라서 모든 안전영역은 case에 누적이 되고
누적된 case에서 제일 큰 수를 뽑아내면 정답이다.
즉 높이가 4이거나 5일 때 영역이 5로 최대가 되므로 5를 출력한다.

정답 코드

# 2468
import sys
from collections import deque
input = sys.stdin.readline

def bfs(x,y,crit):
  queue = deque()
  queue.append((x,y))
  while queue:
    x,y = queue.popleft()
    visited[x][y]=1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or nx >= n or ny < 0 or ny >= n:
        continue
      if a[nx][ny] > crit and visited[nx][ny] == 0:
        queue.append((nx,ny))
        visited[nx][ny]=1


n = int(input())
a = []
dx = [0,0,1,-1]
dy = [1,-1,0,0]
check =0

for i in range(n):
  a.append(list(map(int, input().split())))

j =[]
for i in range(n):
  j.append(max(a[i]))
check = max(j)
case = []
if check != 1:
  for i in range(1,check):
    count =0
    visited = [[0 for _ in range(n)] for j in range(n)]
    for k in range(n):
      for q in range(n):
        if a[k][q] > i and visited[k][q] ==0:
          bfs(k,q,i)
          count+=1
    case.append(count)
  print(max(case))
else:
  print(1)

---

느낀점

최대 높이가 1일 때(모든 영역의 높이가 1일 때) 예외 처리를 하지못해 어디가 틀렸는지 몰라 고민을 많이 했다.
bfs 문제가 전체적으로 비슷한 느낌이 많이 들어서
초기 입력과 탐색을 어느 부분에서 어떻게 할지가 키포인트였다.🤔