[TIL] 99클럽 코테 스터디 4일차 TIL + 백준 24479 깊이 우선 탐색 1

 

문제 풀이

 

문제 탐색하기

깊이 우선 탐색(DFS, Depth-First Search)

그래프 탐색 알고리즘으로, 노드를 탐색할 때 깊이를 우선하여 끝까지 탐색하는 방식입니다.
시작 노드에서 출발하여 갈 수 있는 만큼 깊이 들어가고, 더 이상 갈 곳이 없으면 직전 노드로 돌아가 다른 경로를 탐색하는 방식으로 진행됩니다. 

DFS 는 스택 자료 구조를 사용하여 구현할 수도 있고 재귀호출을 통해 구현할 수도 있습니다.

 

DFS의 동작 원리

1. 시작 노드에서 출발하여, 방문한 노드를 스택에 저장합니다.
2. 현재 노드에서 갈 수 있는 노드가 있다면, 그 노드를 방문하고 스택에 추가합니다.
3. 갈 수 있는 노드가 없으면 스택에서 가장 최근 노드를 꺼내와(백트래킹) 다음 가능한 노드를 탐색합니다.
4. 위 과정을 모든 노드를 방문할 때까지 반복합니다.

DFS 특징

• 시간 복잡도: 그래프의 모든 노드를 탐색하므로, O(V + E) (V: 정점 수, E: 간선 수)
• 장점: 경로 탐색에 유리하며, 특정한 목표까지의 경로를 찾는 문제에 적합합니다.
• 단점: 경로가 매우 깊어질 경우 재귀 호출이 많아져 메모리 초과나 스택 오버플로우가 발생할 수 있습니다.

 

 

DFS 알고리즘 활용하여 문제 설계하기

간선이란 양 점을 잇는 선 입니다. [ 1 4 ] 가 간선으로 주어진다면 1은 4와 이어져있는 것이고 4는 1하고 이어져있는 것과 마찬가지 입니다.

정점의 개수만큼 ArrayList를 선언하여 정점이 도달할 수 있는 다른 정점을 해당 리스트에 담아줘야하는데 위의 원리를 바탕으로 1의 리스트에 4가 들어가고 4의 리스트에 1이 들어가야합니다. 

 

1. 첫번째 정점으로 DFS 탐색을 시작합니다.
2. 첫번째 정점 리스트 중 가장 작은 값을 새로운 점으로 부여합니다.
3. 정점의 방문 순서를 카운트
4. 새롭게 얻어낸 정점의 값을 변수로 넣어서 재귀탐색 합니다.
5. 위 과정을 반복한뒤 탐색이 종료되면 방문순서를 저장한 배열을 출력해줍니다.

 

고려해야할 점

DFS 탐색을 하기위해서 각 ArrayList를 오름차순으로 정렬해줘야 하기에 정렬하는 과정을 빠트리면 안됩니다.

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int cnt;
    static int[] result;
    static ArrayList<ArrayList<Integer>> graph;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        result = new int[N+1];

        for(int i=0; i<=N; i++){
            graph.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        for(int i=1; i<=N; i++){
            Collections.sort(graph.get(i));
        }

        cnt = 1;
        dfs(R);

        for(int i=1; i<result.length; i++){
            System.out.println(result[i]);
        }
    }

    private static void dfs(int R){
        result[R] = cnt;

        for(int i=0; i<graph.get(R).size(); i++){
            int newIndex = graph.get(R).get(i);
            if(result[newIndex] == 0){
                cnt++;
                dfs(newIndex);
            }
        }
    }


}

 

 

오늘의 회고

DFS 알고리즘에 대한 문제를 풀어보고 개념에 대해서 알아갈 수 있는 좋은 시간이었습니다.

배열로 문제를 풀어봤더니 바로 메모리초과... 결국 검색찬스를 이용하여 ArrayList로 문제를 풀 수 있었습니다.

문제를 풀때 메모리도 고려하면서 푸는 것도 중요하다는 것을 느끼는 날이었습니다,,,