백준 2468 - 파이썬

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

2468번: 안전 영역

문제 풀이

기본적인 BFS를 이해하고 있다면 크게 어렵지 않은 문제이나 처음에 문제를 잘 못 이해하여 오답 처리를 받았다. n이 비의 양인 줄 알고 계산했었는데, 알고 보니 0부터 최대높이-1 중에서 안전영역의 최댓값을 구하는 것이었다.

# 물에 잠기지 않는 안전 영역 조사

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

n = int(input())
graph = []
maxNum = 0

for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    if graph[i][j] > maxNum:
      maxNum = graph[i][j]

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

def bfs(x,y,value,visited):
  q = deque()
  q.append((x,y))
  visited[x][y] = True

  while q:
    x, y = q.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < n and 0 <= ny < n:
        if graph[nx][ny] > value and not visited[nx][ny]:
          visited[nx][ny] = True
          q.append((nx, ny))

result = 0
for i in range(maxNum):
  visited = [[False] * n for _ in range(n)]
  cnt = 0

  for j in range(n):
    for k in range(n):
      if graph[j][k] > i and visited[j][k] == 0:
        bfs(j,k,i,visited)
        cnt += 1

  if result < cnt:
    result = cnt

print(result)

코드에서 짚어야 할 포인트는 visited 리스트를 for문을 돌때마다 초기화해준다는 점이다. 이걸 놓치면 탐색이 안될 수 있으니 주의해야 한다.

 

이번 문제를 풀면서 느낀 점은 문제를 넘겨짚지 말고 제대로 이해한 다음에 풀어야 한다는 것이다. 성격이 급한 편이라 대충 훑어보는 경향이 있는데 다음부터는 꼼꼼히 읽어봐야 되겠다.