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

 

문제

백준 알고리즘 수업 - 깊이 우선 탐색 1  | 실버 2

#그래프 이론 #그래프 탐색 #정렬 #깊이 우선 탐

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

 

풀이 & 코드

* 전형적인 DFS 문제

* 문제에서 list 내부의 숫자들을 '오름차순'으로 관리한다 했으므로, Collections.sort를 진행해준다

* 1,2,3,4,5 가 예시일 경우, 답변은 1이 언제, 2가 언제 등 각 노드가 언제 연결되는지를 결정해줘야 하므로 visited 배열에 cnt로 체킹해준 값을 넣어준다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] visited;
    static List<List<Integer>> graph;
    static int n,m,r,cnt = 0;

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); //정점의 수
        m = Integer.parseInt(st.nextToken()); //간선의 수
        r = Integer.parseInt(st.nextToken()); //시작정점
        visited = new int[n+1];
        graph = new ArrayList<>();

        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<visited.length; i++){
            sb.append(visited[i]).append("\n");
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int start){
        visited[start] = cnt;
        for(int i =0; i<graph.get(start).size(); i++){
            int next =  graph.get(start).get(i);
            if(visited[next] == 0){
                cnt++;
                dfs(next);
            }
        }
    }
}

 

회고 & 배운점

* DFS 공부 (https://www.notion.so/dev-if/f2a7fe2bdc3b4878aef9442fe5ff0d20?pvs=4#3ad2c8d068724daf82aa03e733406e6e)

 

* 처음에는 배열로 풀었을 때 타임아웃이 발생했음 

   * DFS를 할 때, 배열로 풀게되면 재귀 호출마다 '깊은 복사'가 발생함 => 시간과 메모리 비용이 커져서 타임아웃이 발생할 가능성이 높음

   * 반면, 리스트는 주로 '얕은 복사'가 발생함 => 즉, 참조만 넘기기 때문에 메모리 복사가 덜 일어나 기능 상 이점이 있음 !! 

 

* 마지막에 visited 출력해줄 때도, print 하는 것보단 string builder 사용해서 출력시 메모리가 훨씬 효율적이다.