leejuy1140   5년 전

1. 해당 방향으로 k칸 이동 가능한지 찾기

2. 갈 수 있으면 그 방향으로 회전 후, 방향과 명령 횟수 갱신 (180도 회전 고려)

3. 해당 방향에서 k 칸 이동 가능하면, 큐에 push

4. 방문 체크는 해당 칸에 얼마만의 k로 도착했는지의 여부로 확인

대체 어디가 잘못됐을까요ㅠㅠㅠ 진짜 모르겠어요..

seico75   5년 전

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는 도착하면 끝나니까  먼저 도착하는 것이 최적이라는 보장이 필요할 것 같습니다.

leejuy1140   5년 전

@seico75

감사합니다.

회전과 이동을 각각 큐에 넣었더니 맞았습니다.

그런데, 회전과 이동을 함께 큐에 넣으면 틀리는 이유가 뭘까요?

leejuy1140   5년 전

처음에는 위의 탈출 조건을

if (cur.r == dest.r && cur.c == dest.c && cur.dir == dest.dir) return cur.cnt;

이렇게 바꿨더니 알려주신 반례는 통과를 했는데 그 후에도 틀렸습니다가 나와서,

회전과 이동을 따로 처리해봤습니다.

seico75   5년 전

어떻게 설명을 드려야 할지 잘 모르겠는데....

처리할 것을 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 부분에서 끝나버릴 수 있는 거죠.

                                                               

leejuy1140   5년 전

@seico75

감사합니다. 이해했습니다..

그러면 목표 지점에 도달했을 때 바로 종료하지 않고 최소값을 갱신하는 방법으로 코드를 바꿔봤는데,

아래 코드가 틀리는 이유는 뭘까요..?

seico75   5년 전

추측으로는 visited 때문이 아닌가 합니다.

cnt 가 더 큰 경우가 먼저 특정 상태를 방문하고 visited 를 set 하면

더 작은 경우는 방문을 못하고, 결국 정답(최소턴 찾기)에 이르지 못할 것 같습니다.


위와 같이 중간에 종료를 하지 않는다는 것은 완전 탐색일텐데, 

이 경우는 dfs 로 해서 들어갈때 visited 셋하고 나올때 reset 하면서 하면 답이 나오지 않을까요?

예를 만들고 싶지만 머리가 딸려서 ㅠㅠ

leejuy1140   5년 전

@seico75

추측하신대로 방문 체크 때문이었습니다.

그래서 방문 체크 시 cnt를 저장해 이보다 작은 상태는 큐에 삽입 가능하도록 바꿔서 통과했습니다.

시간도 더 걸리고, bfs의 특징을 보았을 때 좋은 방법은 아닌 것 같지만, 원인을 알아서 너무 속시원합니다 !

덕분에 많이 알아갑니다. 감사합니다 !

lwh1992   4년 전

저도 cnt값에 회전과 go를 같이 넣어서 계산하고 최소값일때 다시 갱신하는 코드도 넣었는데

왜 틀린지 알 수 있을까요..

어떻게 회전과 진행을 다르게 처리하는건지 이해가 안됩니다..

알려주시면 감사하겠습니다.

댓글을 작성하려면 로그인해야 합니다.