jh05013   2년 전

  1. "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"  "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"  "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"  "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"  "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"   "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"   "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" 
  2. BFS를 할 때, 정점을 방문했다는 표시는 반드시 그 정점을 큐에 넣을 때 해야 합니다. 큐에서 뺄 때 표시를 하면 중복 방문이 일어날 수 있습니다. 왜 중복 방문이 일어날 수 있는지 알아야 BFS를 제대로 이해했다고 할 수 있지 않을까 생각됩니다.
    1. 그리고 이 문제에서는 영향이 없지만, 파이썬 쓰시는 분들은 제발, 제발 list.pop(0)를 쓰지 마세요! pop(0)는 모든 재앙의 근원입니다. https://www.acmicpc.net/blog/view/70
  3. DFS를 재귀로 구현했을 때도 마찬가지입니다. 정점을 방문했다는 표시는 반드시 그 정점에서 DFS 호출을 시작할 때 해야 합니다.
  4. 파이썬의 최대 재귀 깊이는 1,000 근처입니다. 그래서 재귀로 DFS를 구현하면 방법에 따라 런타임 에러가 날 수 있습니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
  5. 입력으로 주어지는 간선은 양방향입니다. 즉 a b가 한 줄에 주어진다면 a에서 b로도 갈 수 있고, b에서 a로도 갈 수 있습니다.

djm03178   2년 전

3번은 제가 이해하기로는 스택으로 DFS를 그렇게 구현하면 재귀로 구현할 때와 결과가 달라질 것 같습니다. 스택에 넣을 때 이미 방문 체크를 해버린다면, 다른 정점을 통해 그 정점에 도달할 수 있어도 방문 체크 때문에 나아가지 못할 것 같네요.

아래 코드처럼 만드는 걸 말씀하신 걸로 보이는데, 이런 케이스를 넣으면 재귀 코드와 답이 서로 다르게 나옵니다.

4 4 1

1 2

2 3

2 4

1 3

jh05013   2년 전

재귀 과정을 그대로 스택으로 구현하는 것을 생각했는데 구현량이 만만치 않겠군요. 해당 내용을 지웠습니다.

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