콘텐츠로 이동

9.5   연습 문제

9.5.1   개념 확인

1.   같은 그래프를 두 가지 방식으로 표현하기

무방향 그래프의 정점은 A, B, C, D 4개이며, 간선은 A-B, A-C, B-C, C-D다.

  1. 이 그래프의 인접 리스트를 적어 보자.
  2. 0과 1만 들어가는 인접 행렬을 완성해 보자.
  3. A와 D가 직접 연결되어 있는지 판단할 때, 저장된 항목 하나만 확인하면 되는 표현 방식은 무엇인가?
  4. 정점이 많고 간선이 적다면 일반적으로 어느 표현 방식이 공간을 더 절약하는가?
참고 답안

  1. 인접 리스트는 다음과 같다.

    A: B, C
B: A, C
C: A, B, D
D: C

  2. 인접 행렬은 다음과 같다.

    A B C D
    A 0 1 1 0
    B 1 0 1 0
    C 1 1 0 1
    D 0 0 1 0

  3. 인접 행렬에서는 A행과 D열이 만나는 항목을 바로 확인할 수 있다. 따라서 임의의 두 정점이 직접 연결되어 있는지 판단하기에 적합하다.

  4. 정점이 많고 간선이 적을 때 인접 리스트는 실제로 존재하는 간선만 기록한다. 따라서 모든 정점 쌍에 대해 자리를 마련하는 인접 행렬보다 일반적으로 공간을 더 절약한다.

2.   너비 우선 탐색과 깊이 우선 탐색의 방문 순서

무방향 그래프의 정점은 A, B, C, D, E이며, 간선은 A-B, A-C, B-D, C-D, D-E다.

A에서 출발하고, 방문하지 않은 인접 정점이 여러 개면 알파벳순으로 선택한다고 하자.

  1. 너비 우선 탐색(BFS)의 방문 순서를 적어 보자.
  2. 재귀 깊이 우선 탐색(DFS)의 방문 순서를 적어 보자.
  3. 두 탐색 모두 이미 방문한 정점을 기록해야 하는 이유는 무엇인가?
참고 답안

  1. BFS의 방문 순서는 A, B, C, D, E다. A에서 간선 하나로 도달하는 B와 C를 먼저 방문하고, 그다음 더 멀리 있는 D와 E를 방문한다.

  2. DFS의 방문 순서는 A, B, D, C, E다. 현재 정점에서 방문하지 않은 인접 정점으로 차례대로 들어가므로 먼저 A → B → D → C를 따라간다. C에서 새로 방문할 인접 정점이 없으면 D로 돌아와 E를 방문한다.

  3. 그래프에는 A-B-D-C-A와 같은 사이클이 있다. 이미 방문한 정점을 기록하지 않으면 같은 정점들을 사이클을 따라 반복해서 방문하여 탐색이 정상적으로 끝나지 않을 수 있다.

3.   BFS 한 번으로 그래프 전체를 방문할 수 있는가

무방향 그래프의 정점은 A, B, C, D, E, F이며, 간선은 A-B, B-C, D-E뿐이다.

  1. A에서 BFS를 한 번 시작하면 어떤 정점을 방문할 수 있는가?
  2. 1번의 결과를 바탕으로, 이 BFS가 그래프의 모든 정점을 방문했는지 판단하고 이유를 설명하라.
  3. 모든 정점을 알파벳순으로 확인하면서 방문하지 않은 정점을 만날 때마다 BFS를 새로 시작한다면, 각 BFS의 시작 정점은 무엇인가? 이 그래프는 서로 연결되지 않은 부분인 연결 요소 몇 개로 이루어져 있는가?
참고 답안

  1. A에서 출발하면 A, B, C만 방문할 수 있다.

  2. 모든 정점을 방문한 것은 아니다. D, E는 서로 연결된 별개의 부분을 이루고, F는 홀로 떨어진 정점이다. 이 정점들과 A 사이에는 경로가 없으므로 A에서 출발해서는 도달할 수 없다.

  3. 세 번의 BFS는 차례대로 A, D, F에서 시작하여 각각 {A, B, C}, {D, E}, {F}를 방문한다. 따라서 이 그래프의 연결 요소는 3개다.

9.5.2   프로그래밍 연습

1.   무방향 그래프에 경로가 존재하는지 판단하기

정점이 \(n\)개인 무방향 그래프가 주어지며, 정점 번호는 \(0\)부터 \(n-1\)까지다. 배열 edges의 각 항목 [u, v]는 정점 u와 v 사이에 무방향 간선이 있음을 나타낸다.

시작 정점 source와 도착 정점 destination도 주어진다. 먼저 edges로 인접 리스트를 만든 뒤 BFS 또는 DFS를 사용하여 source에서 destination까지의 경로가 있는지 판단하라. 있으면 true를, 없으면 false를 반환하라. 그래프에는 사이클이 있을 수 있으며, 모든 정점이 서로 연결되어 있지 않을 수도 있다.

풀이 힌트
  1. 무방향 간선은 양쪽 방향을 모두 추가해야 한다.
  2. 그래프에는 사이클이 있을 수 있으므로 이미 방문한 노드를 반드시 기록해야 한다.
  3. source에서 출발하여 destination을 만나면 true를 반환한다. 탐색을 마칠 때까지 만나지 못하면 false를 반환한다.

LeetCode

댓글로 의견이나 질문, 제안을 남겨 주세요