[BOJ] 백준 2206 벽 부수고 이동하기 (Swift)

문제

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

2206번: 벽 부수고 이동하기

풀이

BFS로 풀 수 있는 문제입니다.

벽은 최대 1번 부수고 이동이 가능합니다.
방문 배열을 2차원 배열로 선언하는 것이 아닌,
벽을 한 번 부시고 방문했는지, 부시지 않고 방문했는지의 여부를 알 수 있도록 3차원 배열로 선언해주어야 합니다.

BFS를 작성할 때, Queue에 다음과 같이 담아주었습니다. (y, x, 벽 부순 횟수, 몇 칸 이동)

현재 칸에서 다음 칸으로 이동을 할 때는 두가지 경우가 있습니다.

1. 벽이 아닌 경우
2. 벽인 경우

벽이 아닌 경우는 이동이 가능하므로, 이동시켜주고 방문처리를 해주어야 합니다
방문처리를 할 때, 현재 벽을 부신 경험이 있다면 visited[1][y][x], 없다면 visited[0][y][x]에 방문 처리를 해주어야겠죠?
Queue에 이미 벽을 부신 횟수가 있으므로, 그 횟수를 넣어주면 될 것입니다.

벽인 경우는 이동이 가능 할 수도, 불가능 할 수도 있습니다.
벽을 부순 경험이 있다면 이동이 불가능 할 것입니다.

하지만 벽을 부순 적이 없다면, 벽을 부수고 이동이 가능합니다.
그렇다면 visited[1][y][x]를 방문해주면 되겠네요.

이렇게 방문하여 최종 (n - 1, m - 1)에 도달한다면 몇칸을 이동했는지 출력해주고, 도달하지 못한다면 -1을 출력하면 됩니다.

소스코드

후기

벽을 부순 횟수를 방문 배열에 담아주는 것이 핵심이었던 문제였습니다.