# 연습 문제

## 개념 확인

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

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

<!-- numbered-subquestions -->

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

??? success "참고 답안"

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

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

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

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

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

<!-- numbered-subquestions -->

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

??? success "참고 답안"

    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`와 같은 사이클이 있다. 이미 방문한 정점을 기록하지 않으면
        같은 정점들을 사이클을 따라 반복해서 방문하여 탐색이 정상적으로 끝나지 않을 수 있다.

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

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

<!-- numbered-subquestions -->

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

??? success "참고 답안"

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

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

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

## 프로그래밍 연습

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

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

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

??? tip "풀이 힌트"

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

[LeetCode](https://leetcode.com/problems/find-if-path-exists-in-graph/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }