99클럽 코테 스터디 4일차 TIL

백준 - 24479번

문제 이해

• N개의 정점, M개의 간선으로 구성된 무방향 그래프
• 모든 간선의 가중치는 1이다.
• 인접 정점은 오름차순으로 방문한다.

한 줄마다 입력된 u v 정점은 양방향 간선을 가진다.

첫 번째 u v 입력을 보면, 정점 1은 정점 4를 방문할 수 있고, 정점 4 또한 정점 1을 방문할 수 있다.

 

예제 입력을 그림과 표로 나타내보자.

시작 정점	방문할 수 있는 정점
1	2, 4
2	1, 3, 4
3	2, 4
4	1, 2, 3
5	0

시작 정점들에 대한 인접 리스트를 만들고, 각 정점이 방문할 수 있는 정점 번호들을 리스트에 넣는다.

정점 번호가 작은 순서대로 탐색하기 위해 리스트 안의 정점들을 오름차순으로 정렬한다.

그리고 시작 정점(r)에서부터 DFS를 수행하여 방문 순서를 기록한다.

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    static ArrayList<Integer>[] graph; // 정점의 인접 리스트
    static int[] visited; // 방문 노드
    static int root = 1;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int r = sc.nextInt();

        // 그래프 초기화
        graph = new ArrayList[n + 1];
        visited = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 입력
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }

        // 정점 번호가 작은 순서로 방문하기 위해 정렬
        for (int i = 1; i <= n; i++) {
            Collections.sort(graph[i]);
        }

        // 깊이 우선 탐색
        dfs(r);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(visited[i]).append("\n");
        }
        System.out.print(sb);
    }

    static void dfs(int node) {
        visited[node] = root++;

        for (int nextNode : graph[node]) {
            if (visited[nextNode] == 0) {
                dfs(nextNode);
            }
        }
    }
}

그래프를 이중 배열로도 구현할 수 있다.

이중 배열의 경우, 초기화할 때 배열의 크기를 정해줘야 하며, 모든 정점 간의 연결을 저장하기 위해 n * n의 크기가 필요하다.

만약 정점의 수가 많고, 연결되는 간선이 적은 경우 불필요하게 DFS를 수행하게 되고 많은 메모리를 사용하게 된다.

이중 배열은 모든 간선이 연결되어 있는 경우에 효율적이다.

---

백준 24479번 알고리즘 수업 - 깊이 우선 탐색 1

https://www.acmicpc.net/problem/24479