[DFS/BFS/완전탐색] ★★ 2206번 - 벽 부수고 이동하기(BFS)

[백준] 2206번 - 벽 부수고 이동하기

풀이 시간: 

 

1) 문제 해결 아이디어

언제 벽을 부숴야 할지 조건을 떠올리는게 쉽지 않았다. 최근에 푼 BFS 문제 중에는 난이도가 가장 높은 문제인 것 같다. 여러가지 아이디어를 떠올려보고 시도해봤으나 잘 되지 않고 시간이 너무 지체되서 풀이를 봤는데도 한 번에 이해가가지 않아 복습이 필요한 문제다.

 

Q. visited 3차원 배열 생성 시 초기화하는 이유는?

visited를 생성하는 부분에서 시작 좌표(0, 0)에 해당하는 부분을 1로 초기화해야한다.

그렇지 않으면 (0,1)이나 (1,0)의 인접좌표를 검사할 때 (0, 0)의 graph값이 0이므로 검사를 진행하게 되는 문제가 발생한다. 사실상 정답에 영향을 미치지는 않지만 헷갈리니 그냥 다 초기화하는 걸로 하자.

 

Q. visited 3차원 배열 형태

아직도 왜 visited[x][y][c] 형태로 만들었는지 정확히 이해가 안간다.

print(x, y, c) 주석 처리한 부분을 주석 해제하면 어떤 식으로 동작하는지 모두 나오므로 보고 잘 이해해보자.

 

2) 소스코드

from collections import deque
# 세로, 가로
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 3차원 리스트(0: 방문하지 않은 곳, 1: 방문한 곳)
# visited[0][0][0]: 벽 파괴 가능, visited[0][0][1]: 벽 파괴 불가능
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]  # 3차원 행렬
visited[0][0][0] = 1
visited[0][0][1] = 1

# BFS(현재 좌표, 부순 위치)
def bfs(x, y, c):
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, y, c))
  
  while queue:
    x, y, c = queue.popleft()
    #print(x, y, c)
    # 끝 점에 도달하면(종료 조건)
    if(x == n - 1 and y == m - 1):
      return visited[x][y][c]  # 이동 칸 수
    # 상하좌우 탐색
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if(0 <= nx < n and 0 <= ny < m):
        # 길이고 아직 방문하지 않은 곳이면
        if(graph[nx][ny] == 0 and visited[nx][ny][c] == 0):
          # 삽입, 방문 처리
          queue.append((nx, ny, c))
          visited[nx][ny][c] = visited[x][y][c] + 1
        # 벽이고 아직 벽을 부순적이 한 번도 없으면
        elif(graph[nx][ny] == 1 and c == 0):
          # 해당 좌표 벽 부수기          
          queue.append((nx, ny, 1)) 
          visited[nx][ny][1] = visited[x][y][0] + 1
  return -1
 
# 시작 지점(0,0)에서 아직 벽을 부수지 않은 상태로 호출
print(bfs(0, 0, 0))