[백준] 2468번 - 안전 영역

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

예제 밑에 있는 노트를 주의깊게 봐야하는데,

혹여나 놓치고 지나갈 수 있는 부분이기 때문이다.

 

주어진 n이 2이고 [[1, 1], [1, 1]] 일 때 높이가 모두 같기 때문에

물이 잠기지 않을 수 있다고 생각할 수 있다.

 

처음에 코드를 작성하면서 문제를 잘 못 읽었는데,

해당 문제에서 요구하는 것은 높이가 설정될 때

안전한 영역을 최대로 만들 수 있는 갯수를 요구하고 있다.

 

그래서 최소한의 높이를 통해 최대로 만들 수 있는

안전 영역의 갯수를 계속해서 갱신해야 한다.

 

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

n = int(input())
maps = [list(map(int, input().split())) for _ in range(n)]

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

def bfs(y, x, num):
  q = deque([(y, x)])
  chk[y][x] = True
  while q:
    ey, ex = q.popleft()
    for k in range(4):
      ny = ey + dy[k]
      nx = ex + dx[k]
      if 0 <= ny < n and 0 <= nx < n:
        if maps[ny][nx] > num and not chk[ny][nx]:
          chk[ny][nx] = True
          q.append((ny, nx))

maxV = 0
for i in range(max(map(max, maps))):
  chk = [[False] * n for _ in range(n)]
  cnt = 0
  for j in range(n):
    for k in range(n):
      if maps[j][k] > i and not chk[j][k]:
        chk[j][k] = True
        bfs(j, k, i)
        cnt += 1
  maxV = max(maxV, cnt)

print(maxV)

 

넓이 탐색을 진행하면서, 확인한 안전 영역을 True로 표시해준다.

 

여기서 기존 문제들과의 차이점은 maps에 있는 최댓값을 뽑아서

해당 범위만큼을 돌아주어야 한다.

 

그 이유는 최댓값을 갱신하기 위함인데,

chk 리스트를 0부터 최댓값까지 계속해서 새로 만들어주면서

max 값을 갱신해주면 된다.

 

이때, 2중 for문을 돌면서 0부터 시작하는 값이 해당 인덱스의 값보다

작으면 계속 bfs를 돌아주면서 안전 영역의 갯수를 세주면 된다.

해당 갯수를 max 함수로 계속해서 갱신해준다.

 

문제를 잘 읽고, 히든 케이스까지 고려해서 코드를 작성하는

연습을 계속해서 진행해야겠다.

 

화이팅 💪