[BOJ] 2206. 벽 부수고 이동하기(Python) / BFS

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

꽤 고차원적인 BFS 문제이다. 이 문제 사실 4번째 푸는 문제더라..

그 와중에 1시간 반 정도 걸려서 풀었다, 인풋부터 잘못 받아서 계속 틀렸다.

int가 아니라 str로 받아서 자꾸 BFS를 퍼트리지 못했다ㅠㅠ

 

bfs 함수 안에서 꽤 헤맸다.

• 폭탄 가지고 있을 때, 없을 때를 다른 visited에 표현
• 큐에 폭탄(벽 부술 기회) 정보와 위치 정보를 담으면서 BFS 퍼트리는 것이 핵심!
• 목적지 도달하면 거리 정보(visited[bomb][r][c]) 리턴
• 목적지 도달하지 못하면 -1 리턴

 

코드를 깔끔하게 짜려고 노력했다. 

 

파이썬 코드는 다음과 같다.

---

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

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    Q = deque([(0, 0, 1)])
    visited = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(2)]
    visited[0][0][0] = 1
    visited[1][0][0] = 1
    while Q:
        r, c, bomb = Q.popleft()
        
        # 목적지에 도달했을 때의 visited에 있는 거리 정보 리턴
        if r == N-1 and c == M-1:
            return visited[bomb][r][c]

        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            
            if not (0 <= nr < N and 0 <= nc < M):
                continue
            if visited[bomb][nr][nc]:
                continue

            # 벽 만났고 폭탄 기회 남았다면
            if A[nr][nc] and bomb:
                visited[0][nr][nc] = visited[1][r][c] + 1   # 이 부분이 헷갈린 부분
                Q.append((nr, nc, 0))

            # 벽이 아닌 경우 일반적인 bfs
            if not A[nr][nc]:
                visited[bomb][nr][nc] = visited[bomb][r][c] + 1
                Q.append((nr, nc, bomb))
    return -1

N, M = map(int, input().split())
A = [list(map(int, input().strip())) for _ in range(N)]
print(bfs())

---

• 시간 : 656ms / 메모리 : 174252 (PyPy3)
• 고찰 : 여러번 풀어본 문제임에도 자꾸 꼬인다.. BFS 문제 중 골치 아픈 문제 중 하나라고 생각한다. 벽 부술 기회 있을 때, visited 표시하면서 많은 생각을 해주면서 코드를 짰다. 아직 내공이 부족한가 보다. 더 노력하자. All the endeavors for me!