sshhss0312   1년 전

코드의 흐름으로는 우선 가로 출발상태인 끝점이 1,2인 점을 큐에 삽입 후 하나씩 꺼내어 출발 상태의 경우의 수(가로는 2개, 세로 2개, 대각선 3개)를 모두 고려하여 만족하면 큐에 삽입하는 방식으로 동작합니다. 그렇게 어떤 모양으로 도착했는지를 나눠서 dp에 값을 누적시킵니다. visited배열은 각 지점의 모양별로 한번씩만 큐에 삽입 하면 되기때문에 사용하였습니다. 제 생각엔 누락될 부분이 없는데 결과가 틀리게 나옵니다. 다음은 반례입니다. 특이하게 정답과 1씩 차이가 납니다.

8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

출력 32 정답 33

9
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

출력 51 정답 52

9
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0

출력 674 정답 675

sharkeligator   1년 전

같은 좌표를 여러 번 처리하는 과정에서 큐의 순서가 정답이 보장되지 않는 것 같습니다.

늦게 값이 업데이트 될 때 누락되는 경우가 있는 것 같네요.

9
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0

output : 144

정답 : 168

sshhss0312   1년 전

이 글 보고 다시생각해보니까 같은 좌표와 방향일 때 누락될 수가 있네요, 다른 방식을 시도해봐야겠어요 감사합니다!

sshhss0312   1년 전

그냥 dp만 사용하는 방식으로 다시해결했습니다 감사합니다!

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