99클럽 코테 스터디 4일차 TIL - 백준[24479]

---

문제 풀이

오늘의 문제 - 백준24479.알고리즘 수업[깊이우선탐색1]

나의 풀이

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

public class Main {
    public static int[] visited;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public 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 = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        
        visited = new int[n+1];
        
        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        
        // 그래프 값 넣기
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        
        // 한 정점에 대해 오름차순 정렬하기
        for (int i = 1; i <= n; i++) {
            Collections.sort(graph.get(i));
        }
        
        // DFS
        count++;
        dfs(r);
        
        for (int i = 1; i < visited.length; i++) {
            bw.write(String.valueOf(visited[i] + "\n"));
        }
        bw.flush();
        bw.close();
    }
    
    public static void dfs(int r) {
        visited[r] = count;
        for (int i = 0; i < graph.get(r).size(); i++) {
            int v = graph.get(r).get(i);
            if (visited[v] == 0) {
                count++;
                dfs(v);
            }
        }
    }
}

해결과정

• 깊이우선탐색을 처음 접했고, 그래프?! 감이 안잡혀 구글서치로 다른 사람들의 풀이를 보고 공부했다...ㅠ
• DFS를 공부해야한다!!!
• ArrayList<ArrayList> 로 이차원 배열을 선언해서 푼다는 것을 기억해두기!

---

오늘 배운 점

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

• 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다.
• 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에, 완전탐색 알고리즘에 속하기는 하지만, 항상 완전탐색으로 사용되지는 않는다.
• DFS는 주로 반복문을 활용하거나, 재귀문을 통하여 구현된다.

DFS의 탐색 과정

DFS의 기본 탐색 과정은 특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 것이다. 탐색하는 과정은 다음과 같다.
1. 현재 노드를 방문한 것으로 표시한다.
2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.
3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking) 한다.
4. 모든 정점을 방문할 때까지 프로세스를 반복한다.

DFS의 장단점

• DFS의 장점
  • DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
  • DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
  • DFS를 사용하여 그래프에서 순환을 감지할 수 있다.
• DFS의 단점
  • 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
  • DFS는 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.
  • DFS는 특정 시나리오에서 매우 유용할 수 있지만 항상 최선의 선택은 아니다. 해결하려는 특정 문제에 따라 BFS(Breadth-first Search)와 같은 다른 알고리즘이 더 적합할 수 있다.

정렬기능

• Collections.sort() : 오름차순 정렬
• Collections.sort(ArrayList, Collections.reverseOrder()) : 내림차순 정렬