[DFS/BFS/완전탐색] ★ 2468번 - 안전 영역(BFS/DFS)

[백준] 2468번 - 안전 영역

풀이 시간: 90분 이내

 

문제를 푸는 데는 20분 정도 걸렸는데 오류를 해결하는데 시간이 오래걸렸다. 나중에 다시한번 풀어봐야할 문제인 것 같다.

 

(풀이1) BFS

1) 문제 해결 아이디어

 

첫번째 오류. TypeError

예약어를 변수명으로 사용하였기 때문에 나타난 오류다.

변수명을 min, max와 같은 예약어를 사용하면 문제가 된다!

 

[참고] https://m.blog.naver.com/passionisall/221828106961

[Python] 파이썬 'int' object is not callable 에러코드 설명

 

두번째 오류. 런타임 에러(ValueError)

코드가 계속 맞다고 생각했는데 해결이 되지 않아 다른 사람들의 풀이를 찾아보았다.

나는 원래 기준 높이(h)보다 클 때 안전영역이므로 bfs()를 호출해야한다고 생각했는데 계속 실패했다. 

실패한 결정적인 이유는 h의 범위를 (min_h, max_h + 1)으로 잘못 설정해주었기 때문이다.

 

예를 들어, graph의 모든 값이 2라면 min_h = 2, max_h = 2 가 된다.

(min_h, max_h+1)을 적용하면 (2, 3)이며 h는 2에 대해서만 bfs()를 호출하게 되고

2보다 큰 높이를 안전영역으로 인식하므로 결과값(res)가 0이된다. (모든 값은 2이므로)

그런데 실제로는 h가 1에 대해서 bfs를 호출하면 결과값(res)는 1이된다.

그러므로 기준 높이(h)보다 클 때 bfs()를 호출할 경우, (min_h - 1, max_h)으로 설정해야 맞는 코드가 된다. 참고한 코드에서는 기준 높이(h)보다 크거나 같을 때 bfs()를 호출하는 것으로 되어있고 h의 범위가 (min_h, max_h + 1)였다.

 

[참고] https://ywtechit.tistory.com/66

[ 파이썬(python) ] 백준 2468 - 안전 영역

2) 소스코드

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

# BFS
def bfs(x, y, h):
  queue = deque()
  # 시작 지점 삽입, 방문 표시
  queue.append((x, y))
  visited[x][y] = 1

  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 범위 내이이고
      if(0 <= nx < n and 0 <= ny < n):
        # 방문한적이 없고 기준 높이보다 크면 
        if(visited[nx][ny] == 0 and h < graph[nx][ny]):
          # 삽입, 방문 표시
          queue.append((nx, ny))
          visited[nx][ny] = 1

n = int(input())  # 행, 열 크기
# n * n 맵
graph = [list(map(int, input().split())) for _ in range(n)]
#visited = [[0] * n for _ in range(n)]
# 2차원 리스트 최솟값, 최댓값
min_h = min(map(min, graph))
max_h = max(map(max, graph))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

max_safe = 0  # 최대 안전 영역 수
for h in range(min_h - 1, max_h):
  visited = [[0] * n for _ in range(n)]
  safe = 0  # 안전한 영역 개수
  for i in range(n):
    for j in range(n):
      # 방문한적이 없고 기준 높이보다 크면 
      if(visited[i][j] == 0 and h < graph[i][j]):
        bfs(i, j, h)
        safe += 1  # 안전 영역 개수 1증가
  
  if(safe > max_safe): max_safe = safe

print(max_safe)

 

(풀이2) DFS

1) 문제 해결 아이디어

 

2) 소스코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# DFS
def dfs(x, y, h):
  # 현재 지점 방문 처리
  visited[x][y] = 1
  
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if(0 <= nx < n and 0 <= ny < n):
      # 방문한적이 없고 기준 높이보다 크면 
      if(visited[nx][ny] == 0 and h < graph[nx][ny]):
        visited[nx][ny] = 1  # 방문 처리
        dfs(nx, ny, h)

n = int(input())  # 행, 열 크기
# n * n 맵
graph = [list(map(int, input().split())) for _ in range(n)]
#visited = [[0] * n for _ in range(n)]
# 2차원 리스트 최솟값, 최댓값
min_h = min(map(min, graph))
max_h = max(map(max, graph))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

max_safe = 0  # 최대 안전 영역 수
for h in range(min_h - 1, max_h):
  visited = [[0] * n for _ in range(n)]
  safe = 0  # 안전한 영역 개수
  for i in range(n):
    for j in range(n):
      # 방문한적이 없고 기준 높이보다 크면 
      if(visited[i][j] == 0 and h < graph[i][j]):
        dfs(i, j, h)
        safe += 1  # 안전 영역 개수 1증가
  
  if(safe > max_safe): max_safe = safe

print(max_safe)