관련 문제

• 백준 16954 움직이는 미로 탈출
• 백준 2206 벽 부수고 이동하기.
• 백준 14442 벽부수고 이동하기 2.
• 백준 16933 벽부수고 이동하기 3.
• 백준 1600 말이 되고픈 원숭이

개념

• 일반적인 bfs에서 [y][x] visited 배열을 통해 진행했는데,
  새로운 상태값이 주어져서 문제에 영향을 주는 경우
  visited 차원을 더 늘려서 진행해야 한다.

문제 중에서 동일한 상황이 아닌 경우에 visited 변수에 상태 개수에 따른 값을 배열에 1차원 더 추가해서 진행하자.

• 상태를 추가함으로써 얻는 이점으로는 모든 상황에 대해 생각할 수 있다는 것이다.

• 백준 2206. 을 예제로 설명.

• 생각을 해보자.
  0,0의 정점에서 n,m 으로 가는 최단 경로 인데,
  벽을 한 번 부수고 갈 때의 최단 경로, 벽을 부수지 않고 갈 때의 최단 경로가 있다고 하자.

• 억지로 1개로 하면 되지 않을까?
  : [y][x] 그냥 이걸로 2차원 배열로
  -> 단순하게 생각하면 그래도 될듯 하지만,
  갱신할 때를 생각해보자.
  동일한 좌표에 대해 부수고 들어오지 않을때 보다, 1개 부수고 들어왔을 때 값이 좋아서 갱신했다.
  해당 좌표에서 next값 진행하려고 한다.
  그런데 next 좌표 입장에서는 여기까지 오는데, 벽을 뚫고 왔을때의 최단경로
  그냥 왔을 떄의 최단 경로를 알아야 한다.
  그래야 내 입장에서도 벽을 부술까? 말까??? 에 대한 생각을 할 수 있다.
  -> 지금 이 생각은 모든 상황에 대해서 생각을 하고 있는 것이다.

• 그러면 2개로 분류해서 진행하면 된다.
  [y][x][벽 부쉈는지 안부쉈는지.] 3차원 배열이 필요한다.
  굳이 억지로 1개로 퉁쳐서 하기에는 그 상황에 대한 정보를 알 수 없다. 1개로 하게 되면 해당 y,x 에 도달했을 때, 이 때 벽을 부쉈는지, 부수지 않았는지 알수 없다.

어디서 상태가 변경되는지를 찾아라.

: 움직이는 미로 탈출의 문제의 경우, 매초마다 벽의 위치가 변경되고, 즉 시간마다 좌표들의 상태가 변경된다.
-> r,c로 이동하는데 몇초 뒤에 이동할 것인지에 따라서 상태가 다르다. 벽이 있어서 못갈 수 있고,

중요.

• 1) 중간 지점을 거치면서 방문을 하는데 벽을 부쉈는지,
  안 부쉈는지에 대한 정보를 얻어서 추후에 벽이 나오면,
  부술까???? 생각을 할 수 있따. 정보가 없다면, 부술까? 말까?
  에 대한 생각을 할 수 없다.

• 2) 벽을 부수고 온상태에서의 dist값과
  벽을 부수고 오지 않았을 때의 dist 값
  모든 상황에 대해서 생각해야 한다.