BFS는 좌표에 대해서만 사용할 수 있는 테크닉이 아니고, "현재 상태"를 나타낼 수 있는 것이라면 모두 가능합니다.
이 문제의 경우 (x좌표, y좌표, 남은 말 움직임 횟수)를 하나의 "상태"로 나타낼 수 있고, 여기까지는 잘 알고 계신 것 같습니다. 큐의 원소로써 넣으셨다는 게 그 증거입니다.
그러면 이제 여기서 한 가지만 더 하면 됩니다. BFS 할 때 방문 체크를 모든 "상태"에 대해 전부 하면 됩니다. x, y 좌표가 특별한 것이 아니라 그것들도 모두 "상태"를 나타내는 변수 중 하나입니다. 그러면 "남은 말 움직임 횟수" 역시 똑같이 해주면 되겠죠?
visited[x][y][jump]와 같이 체크해주면 "(x, y) 좌표에, 말 움직임 횟수를 jump회 남기고 도달할 수 있는 최소 횟수" 라고 정의하면 됩니다.
ksr315 5년 전
테스트 케이스 몇가지 해봤는데 다 맞게 잘 되는거 같은데
어떤 부분을 놓치고 있는지 잘 모르겠습니다 ㅠㅠ
채점하면 틀리다고 나오는데 어느 부분을 수정해야 될까요?
+반례를 찾았는데 visit때문에 뭔가 문제가 있는거 같은데 어떻게 해결해야 될지 모르겠어요ㅠㅠ
1
4 4
0 1 1 1
0 0 1 1
1 0 1 1
1 1 1 0
이렇게 하면 (2,1)에서 종료지점으로 점프해야되는데 (2,1)의 visit이 체크가 되있어서 못가네요..ㅠㅠ