11403번 - 경로 찾기
BFS로 풀어보고 싶어서, 각각의 정점 i행에 대해서 1~N까지 갈 수 있는지를 확인하는 방식으로 코드를 짰습니다.
그런데, 이렇게 짜면, 1 -> 2 -> 3 -> 1일 경우에,
1번째 행에서 1->2->3->1 이 반복되고,
2번째 행에서도 2->3->1->2 가 반복되고,
3번째 행에서도 마찬가지라는 걸 깨달았습니다.
비효율적인 것 같은데, n이 크지 않아서 그런지 코드가 통과된 것 같습니다.
1->2->3->1 이 되면은, 2번째행에서도, 3번째 행에서도 체크를 해주고 싶은데, 효율적으로 고칠 수 있는 방법이 없는지 궁금합니다.
Set을 이용하는 방법도 생각해봤었는데, 뭔가 잘못 짰는지 제대로 동작하지 않았습니다
일반적인 bfs로 할 땐 정점마다 visited를 초기화해서 말씀하신 반복적인 경로 탐색이 발생합니다.
N이 작아서 플로이드 워셜을 사용하면 한번에 모든 정점의 경로를 구할 수 있습니다.
플로이드 와샬을 이용해서 풀어봤었는데, O(N^3)이라서 혹시라도 최적화..? 할 수 있을까봐 BFS로 풀어봤었습니다!
결국 BFS를 이용해서 풀려면은 반복적인 경로 탐색이 발생하는 수밖에 없군요..
알려주셔서 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
rud15dns 1년 전
BFS로 풀어보고 싶어서, 각각의 정점 i행에 대해서 1~N까지 갈 수 있는지를 확인하는 방식으로 코드를 짰습니다.
그런데, 이렇게 짜면, 1 -> 2 -> 3 -> 1일 경우에,
1번째 행에서 1->2->3->1 이 반복되고,
2번째 행에서도 2->3->1->2 가 반복되고,
3번째 행에서도 마찬가지라는 걸 깨달았습니다.
비효율적인 것 같은데, n이 크지 않아서 그런지 코드가 통과된 것 같습니다.
1->2->3->1 이 되면은, 2번째행에서도, 3번째 행에서도 체크를 해주고 싶은데, 효율적으로 고칠 수 있는 방법이 없는지 궁금합니다.
Set을 이용하는 방법도 생각해봤었는데, 뭔가 잘못 짰는지 제대로 동작하지 않았습니다