[백준2468&파이썬] BFS를 사용할때 탐색 단위에 대한 생각이 필요하다.

# 문제

백준 2468 안전 영역 파이썬 풀이

2468번: 안전 영역

# 코드

import copy
import sys
from collections import deque

N = int(sys.stdin.readline())

board = list()
for _ in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

dirs = [
  (-1,0),(0,1),(1,0),(0,-1)
  ]

maxCount = 0
for tick in range(1,101) :
  mBoard = copy.deepcopy(board)

  # 일단 안전영역 구하기
  for i in range(len(mBoard)) :
    for j in range(len(mBoard[i])) :
      if mBoard[i][j] <= tick :
        board[i][j] = -1 # 잠긴 곳임, 방문표시

  # 안전영역의 개수 세기
  cnt = 0
  for i in range(len(mBoard)) :
    for j in range(len(mBoard[i])) :
      if mBoard[i][j] == -1 :
        continue # 방문한 곳 또는 이미 잠긴 곳이면

      cnt +=1
      dq = deque()
      dq.append((i,j)) # 현재 위치 넣기
      mBoard[i][j]  # 현재 위치 방문 처리

      while len(dq) != 0 :
        cur = dq.popleft()

        for dir in dirs :
          next = (cur[0] + dir[0], cur[1] + dir[1])

          if 0 <= next[0] < N and 0 <= next[1] < N : # 범위 안이고
            if mBoard[next[0]][next[1]] != -1 : # 방문했던곳이 아니면
              # 방문처리
              mBoard[next[0]][next[1]] = -1
              dq.append(next)
  maxCount = max(maxCount,cnt)

print(maxCount)

# 풀이

## 깊은 복사를 사용하는 방법

[python] 파이썬 얕은복사, 깊은복사 (copy, deepcopy, [:], =) 총 정리

import copy

mBoard = copy.deepcopy(board)

• 깊은 복사와 얕은 복사의 개념을 안다면, 깊은 복사를 사용해야지 추후에 생각할 건덕지가 사라진다. 물론 immutable한 int와 같은건 별문제 없겠지만 2차원배열을 썻기 때문에 깊은 복사가 필요하다.

 

## 탐색의 단위를 잘 생각해보면 쉽다

• BFS를 어떤 단위로 끊어서 생각하느냐에 따라서 문제를 쉽게 생각할 수 있다.
• BFS를 처음 공부했던 시기에는 이 생각하는 힘이 약해서 쉬운문제도 엄청 깊게 생각하거나 어렵게 겨우 구현해냈다. BFS를 쉽게 푸려면 그 탐색 단위를 어떻게 끝는지가 중요한거 같다.
• 이 문제에서는 두번단위로 끝어서 생각해야 한다. 
• 일단 안전영역이 가장 많이 생길때의 그 갯수를 구해야 한다. 비는 1~100까지 올 수 있기 때문에 여기서 한번 단위를 끊는다. 
• 그리고 나서 안전영역을 마킹한다. (난 비안전영역을 마킹했다, 즉 비 안전영역을 방문처리 했다.)

maxCount = 0
for tick in range(1,101) :
  mBoard = copy.deepcopy(board)

  # 일단 안전영역 구하기
  for i in range(len(mBoard)) :
    for j in range(len(mBoard[i])) :
      if mBoard[i][j] <= tick :
        board[i][j] = -1 # 잠긴 곳임, 방문표시
        
  # 이제 이 아래서부터 BFS를 돌린다.
  pass

 

• 첫번째로 끊었다면 이제 두번째로 끊을 차례다.
• 요즘 문제를 풀때는 한 탐색 단위로 deque를 만들어서 끊어 사용한다. 옛날에는 이 생각을 못해서 문제를 복잡하게 풀어버리곤 했었다. 하나의 탐색 시작점을 통하여 탐색이 끝났다면, 다시 큐를 만들어 처음부터 반복한다. 이 과정을 계속해서 전체에 대한 탐색을 마친다.

 

## 방문처리를 위한 visit배열을 항상 만들 필요는 없는거 같다.

이건 전에도 적었었다. 입력받아 표기한 board에 그대로 활용할 수 있다면 그냥 활용해도 될 듯 하다. 굳이 방문처리를 위한 visit를 만들어 메모리를 낭비하지 말자.  상황에 맞게 잘 활용하자.