ksr315   2년 전

테스트 케이스 몇가지 해봤는데 다 맞게 잘 되는거 같은데 

어떤 부분을 놓치고 있는지 잘 모르겠습니다 ㅠㅠ

채점하면 틀리다고 나오는데 어느 부분을 수정해야 될까요?

+반례를 찾았는데 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이 체크가 되있어서 못가네요..ㅠㅠ

djm03178   2년 전

BFS는 좌표에 대해서만 사용할 수 있는 테크닉이 아니고, "현재 상태"를 나타낼 수 있는 것이라면 모두 가능합니다.

이 문제의 경우 (x좌표, y좌표, 남은 말 움직임 횟수)를 하나의 "상태"로 나타낼 수 있고, 여기까지는 잘 알고 계신 것 같습니다. 큐의 원소로써 넣으셨다는 게 그 증거입니다.

그러면 이제 여기서 한 가지만 더 하면 됩니다. BFS 할 때 방문 체크를 모든 "상태"에 대해 전부 하면 됩니다. x, y 좌표가 특별한 것이 아니라 그것들도 모두 "상태"를 나타내는 변수 중 하나입니다. 그러면 "남은 말 움직임 횟수" 역시 똑같이 해주면 되겠죠?

visited[x][y][jump]와 같이 체크해주면 "(x, y) 좌표에, 말 움직임 횟수를 jump회 남기고 도달할 수 있는 최소 횟수" 라고 정의하면 됩니다.

ksr315   2년 전

감사합니다~ ㅎㅎ 

개념을 쉽게설명해주셔서 바로 수정했어요~

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