DFS로 구현하니 시간초과가 나길래 BFS로 다시 구현했구요,

구멍인 부분은 배열에 -1을 넣어서 다음번 방문하는 곳이 -1이면 안넣어줬어요!

그리고 visit배열에 몇번째 방문하는 점인지를 적어서(result값 이용)

큐에 넣을 때 이전에 방문했던 노드인지 확인해서

방문하지 않은 노드이면 큐에 넣어주고, 

이전에 방문했던 노드이면 순환하는걸로 판단해서 -1 출력하고 끝내도록 했어요.

어느부분이 잘못된건가요..?

indioindio   10달 전

음 제가 코드를 맞게 이해한건지는 모르겠지만 경로가 다르게 되면 이미 방문한 점을 또 방문하더라도 사이클이 안 생길 수 있어서 -1을 출력하지 않아야 할 때도 있을 것 같습니다.

(지금 당장은 visit[tx][ty] <= result에 걸리지 않으면서 다시 방문해도 사이클이 안 생기는 경우를 생각은 못하겠는데 충분히 존재 할 수 있을 것 같네요)

시작하는 루트(0,0)가 동일하기 때문에 경로가 다르더라도 방문한 점을 또 방문하게 되면 만나는 점에서 시작점으로 다시 돌아갈 수 있는 것이기 때문에 사이클이 생기는거라고 생각했는데 그게 아닌건가요..?

생각이 한방향으로 자꾸 향해서 저 방법 말고는 사이클이 생기는 경우가 잘 떠오르지 않네요..ㅠㅠ

힌트를 조금 더 주실 수 있으실까요..?

indioindio   10달 전

133
5HH
HHH
21H
이런 경우를 생각해보시면 1 - 5를 방문하고 끝난 후에, 1 - 3 - 1 - 2 - 5의 경로를 갈 때 5를 다시 방문하게 되어 사이클이라고 인식하게 됩니다. (물론 방문순서에 따라서 visit[tx][ty]<=result 때문에 -1을 출력하지 않을 수도 있지만 visit[tx][ty] <= result를 통과하는 이런 케이스가 충분히 있다고 생각됩니다.)

이런 경우가 생길 수 있겠네요.. 더 생각해봐야할것같네요ㅠㅠ  감사합니다!

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