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

2206번 : 벽 부수고 이동하기

 

 

말 그대로 벽을 부수며 이동할 수 있는 문제이다. 벽은 단 한번만 부술 수 있다.

 

BFS를 통해 탐색하면서 벽을 부쉈는지 안 부쉈는지에 따라 분기하면 된다.

 

내 코드:

# dawitblog.tistory.com/156
from sys import stdin
from collections import deque
input = stdin.readline

R, C = map(int,input().split())
mat = [input().rstrip() for _ in range(R)]
# 방문 확인
visited = [[[0,0] for _ in range(C)] for _ in range(R)]
visited[0][0][0] = 1
# 큐
q = deque([(0,0,1,0)])
move = [(0,1),(1,0),(-1,0),(0,-1)]

while q:
    r,c,d,isWallBroken = q.popleft()
    # 목적지 도달시
    if r == R-1 and c == C-1:
        print(d)
        exit()

    for dr,dc in move:
        newR = r+dr
        newC = c+dc
        if 0<= newR < R and 0<= newC < C and not visited[newR][newC][isWallBroken]:
            # 벽이 아니라면
            if mat[newR][newC] == '0':
                visited[newR][newC][isWallBroken] = d+1
                q.append((newR,newC,d+1,isWallBroken))
            # 벽이지만 벽을 부순 적이 없다면
            elif not isWallBroken:
                visited[newR][newC][1] = d+1
                q.append((newR,newC,d+1,1))

print(-1)

 

3차원 배열을 만들어야 해서 좀 머리가 아프긴 하다. python3 기준 메모리량이랑 시간이 조금 촉박한 것 같다. 거의 비슷한 로직으로 다른 방법으로 풀었을 때는 시간초과나 메모리 초과가 나온다.