[baekjoon] 백준 2206번 : 벽 부수고 이동하기 (by python 파이썬) bfs

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

정답 code

#벽부스고 이동하기

from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y,z):
    queue = deque()
    queue.append((x,y,z))

    while queue:
        a,b,c = queue.popleft()
        #끝에 도달한경우 결과값 반환
        if a == n-1 and b == m-1 :
            return visited[a][b][c]
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            #다음 이동할 곳이 벽이고 벽파괴 횟수가 0인 경우 - 벽 파괴하고 이동한후 파괴횟수 1로 저장
            if graph[nx][ny] == 1 and c == 0:
                visited[nx][ny][1] = visited[a][b][0] + 1
                queue.append((nx,ny,1))
            #다음 이동할 곳이 벽이 아니고 방문하지 않은 곳이면 이동
            elif graph[nx][ny] == 0 and visited[nx][ny][c] == 0:
                visited[nx][ny][c] = visited[a][b][c] + 1
                queue.append((nx,ny,c))

    return -1


n,m = map(int,input().split())

graph = []
visited = [[[0]*2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1

for i in range(n):
    graph.append(list(map(int, input())))


print(bfs(0,0,0))

 

solution

벽을 부수고 이동한다는 개념이 상당히 헷갈렸다.

벽은 한번만 부술수 있기때문에 이를 어떻게 처리할지가 문제였다.

 

이를 해결하기위해 좌표 값에 벽을 파괴한 경우와 파괴하지 않은 경우를 저장하기위해 3차원으 배열을 저장한다.

 x 좌표와 y 좌표 그리고 0과 1로 벽을 1회 부순 상태인지 아니면 아직 부수지 않았는지 확인 할 수 있다.

 

bfs안에서 만약 벽을 부순횟수가 없고 앞에 벽이 있다면 해당 벽을 부수고 해당 벽에 위치에 이동해 벽을 부순 횟수를 1로 늘려준다.

 

만약 앞이 벽이 아니라면 벽을 부순횟수는 볼 필요가 없고 방문을 했지 않은 곳이면 이동해준다.

 

만약 끝에 도달했다면 마지막 값을 return해준다.