[Baekjoon] 24479 - 알고리즘 수업 - 깊이 우선 탐색 1

📝 문제

 

 

 

🔑 풀이 과정

이 문제는 제목이랑 문제만 보고 베이직한 문제라 생각해서 바로 풀었는데, 꽤 많은 시도를 거친... 문제이다.

알고리즘 자체는 문제에 다 나와있는대로 풀면 되고, 기본적인 DFS 문제이다.

다양한 에러

① 정점의 수(N)이 10만으로 매우 크기 때문에, 인접 행렬로 그래프를 표현하면 메모리초과 에러 발생

인접리스트로 표현해주자.

 

② 정점의 수(N)과 간선의 수(M)을 혼동하지 말고 잘 사용할 것.

간선의 수(M)은 M개의 줄을 입력받을 때 말고는 사용하지 않는다.

그 외 그래프 선언, 정렬, 출력 등은 모두 N을 사용한다.

(예제 입력은 N, M 둘 다 5라서 이 에러를 잡아내기 힘들다.)

 

③ 인접 정점을 오름차순으로 방문한다는 조건이 있으므로, 입력을 받은 뒤 인접리스트 배열을 오름차순으로 정렬해준다.

 

④ 양항뱡 간선이므로 양 정점에 간선을 각각 추가해주어야 한다.

한 정점에서만 추가해주어서 마지막에 틀렸습니다 에러가 발생했던 것(예제로는 잡을 수 없었다.)

 

⑤ 순서를 저장할 배열과, 현재 순서를 카운팅할 변수를 사용한다.

 

 

 

🔓 답안

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<Integer>[] A;
    static boolean[] visited;

    static int[] order;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //첫째 줄 입력
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //정점의 수
        int M = Integer.parseInt(st.nextToken()); //간선의 수
        int R = Integer.parseInt(st.nextToken()); //시작 정점

        A = new ArrayList[N+1];

        for(int i = 1; i <= N; i++){
            A[i] = new ArrayList<Integer>();
        }

        visited = new boolean[N+1];

        order = new int[N+1];

        //간선 입력받기
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[a].add(b);
            A[b].add(a);
        }

        //오름차순으로 정렬하기
        for(int i = 1; i <= N; i++){
            Collections.sort(A[i]);
        }

        DFS(R);

        for(int i = 1; i <= N; i++){
            bw.write(order[i] + "\n");
        }

        bw.flush();
        bw.close();

    }

    static void DFS(int s){
        if(visited[s]){
            return;
        } else{
            visited[s] = true;
            count++;
            order[s] = count;
            for(int r : A[s]){
                if(!visited[r])
                    DFS(r);
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 정렬

- 깊이 우선 탐색