[BOJ]2206번: 벽 부수고 이동하기

 

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

---

기본 BFS 유형에서 '벽을 부쉈냐'라는 상태가 추가되었습니다.

 

벽을 부쉈냐 / 안 부쉈냐라는 상태를 0,1 비트로 표현할 수 있습니다.

 

즉, 같은 칸을 x,y를 방문했어도

1. 벽을 이미 한 번 부수고 이동하는 상황은 visited[0][x][y]로 표시

2. 벽을 아직 안 부수고 이동하는 상황은 visited[1][x][y]로 표시

 

이렇게 위 둘은 같은 좌표를 방문했어도 서로 다른 상태가 되는 것입니다.

 

그러므로 bfs 탐색을 할 때 벽을 부쉈냐 안 부쉈냐까지 고려해서 탐색을 해주면 됩니다.

 

탐색 종료시점은 벽을 부쉈든 안 부쉈든 N,M 지점에 도착하기만 하면 됩니다. 

---

https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2206.cc