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을 이용하는 방법도 생각해봤었는데, 뭔가 잘못 짰는지 제대로 동작하지 않았습니다

siyamaki   1년 전

일반적인 bfs로 할 땐 정점마다 visited를 초기화해서 말씀하신 반복적인 경로 탐색이 발생합니다.

N이 작아서 플로이드 워셜을 사용하면 한번에 모든 정점의 경로를 구할 수 있습니다. 


rud15dns   1년 전

플로이드 와샬을 이용해서 풀어봤었는데, O(N^3)이라서 혹시라도 최적화..? 할 수 있을까봐 BFS로 풀어봤었습니다!

결국 BFS를 이용해서 풀려면은 반복적인 경로 탐색이 발생하는 수밖에 없군요..

알려주셔서 감사합니다!!

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