berrydelicious   1년 전

처음엔 BFS 썼다가 틀려서 O를 최소로 지나야 한다는 것을 깨닫고 우선순위 큐를 사용하도록 바꿨는데요.
맞는가 싶다가 51%에서 틀리네요.

1. A에서 A로 O를 최소로 지나는 경로를 구합니다.
1-2. 경로가 없으면 -1을 출력합니다.
2. O를 짝수 개 지나왔으면 횟수를 출력하고 종료합니다.
2-2. 경로를 역추적해서 지났던 곳(A 제외)을 방문 처리하고 큐에 넣습니다.
3. 다른 O에 도달할 수 있으면 횟수를 출력하고 종료합니다.
3-2. 다른 O에 도달하지 못하면 -1을 출력합니다.

랜덤 마라톤에 나온 문제라 내일까지 풀고 싶습니다.
푼 사람이 별로 없어서 힌트를 얻기가 어렵네요.

zenith82114   1년 전

반례입니다.

4 5
A.O.A
.###.
.#O#.
..O..

[o] 2
[x] -1

berrydelicious   1년 전

아 그럴 수 있네요.

감사합니다.

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