5 6 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 2 2 3 4 5 1
BFS는 도착하면 끝나니까 먼저 도착하는 것이 최적이라는 보장이 필요할 것 같습니다.
1726번 - 로봇
처음에는 위의 탈출 조건을
if (cur.r == dest.r && cur.c == dest.c && cur.dir == dest.dir) return cur.cnt;
이렇게 바꿨더니 알려주신 반례는 통과를 했는데 그 후에도 틀렸습니다가 나와서,
회전과 이동을 따로 처리해봤습니다.
어떻게 설명을 드려야 할지 잘 모르겠는데....
처리할 것을 queue 에 넣고
queue 에 넣은 것을 하나씩 꺼내서 처리하고 도착 지점에 도달하면 끝내는 것이 bfs 잖아요...
다시 말하면 각 step 에서 가능한 모든 조합을 모두 동시에 고려하면서 도달했는지 검사하는 거겠죠.
Queue 에 들어가 있는 cnt 부분을 보면 아래와 같이 커져가겠죠...
{x, y, d, 0},
{x, y, d, 1}
, {x, y, d, 1}
, {x, y, d, 2}
, {x, y, d, 2}
, {x, y, d, 2}
, {x, y, d, 2}
, {x, y, d, 2},
{x, y, d, 3}....
그런데 회전과 전진을 같이 처리하면 cnt 가 한 step 에 1 이상이 증가해서 cnt 가 단조증가가 안되죠.. 아래와 같이.
{x, y, d, 0}, {x, y, d, 1} , {x, y, d, 1} , {x, y, d, 2} , {x0, y0, d, 3} , {x1, y1, d1, 2} , {x, y, d, 2} , {x, y, d, 2}, {x, y, d, 3}....
요기가 회전과 전진 동시
이 경우 더 빠른 해는 뒤에 나오는 {x1, y1} 에서 나오는데 x0, y0 부분에서 끝나버릴 수 있는 거죠.
추측하신대로 방문 체크 때문이었습니다.
그래서 방문 체크 시 cnt를 저장해 이보다 작은 상태는 큐에 삽입 가능하도록 바꿔서 통과했습니다.
시간도 더 걸리고, bfs의 특징을 보았을 때 좋은 방법은 아닌 것 같지만, 원인을 알아서 너무 속시원합니다 !
덕분에 많이 알아갑니다. 감사합니다 !
댓글을 작성하려면 로그인해야 합니다.
leejuy1140 5년 전
1. 해당 방향으로 k칸 이동 가능한지 찾기
2. 갈 수 있으면 그 방향으로 회전 후, 방향과 명령 횟수 갱신 (180도 회전 고려)
3. 해당 방향에서 k 칸 이동 가능하면, 큐에 push
4. 방문 체크는 해당 칸에 얼마만의 k로 도착했는지의 여부로 확인
대체 어디가 잘못됐을까요ㅠㅠㅠ 진짜 모르겠어요..