[백준/JAVA] 24479번: 알고리즘 수업 - 깊이 우선 탐색 1

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, R, cnt;
    
    static ArrayList<Integer>[] A;
    static int[] visited;
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());   // 정점
        M = Integer.parseInt(st.nextToken());   // 간선
        R = Integer.parseInt(st.nextToken());   // 시작 정점
        
        A = new ArrayList[N + 1];
        for(int i = 1 ;  i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            A[u].add(v);
            A[v].add(u);
        }
        
        // 🔔 인접 정점들, 오름차순 정렬
        for(int i = 1 ; i <= N ; i++) {
            Collections.sort(A[i]);
        }
        
        visited = new int[N + 1];
        cnt = 1; // 시작 정점도 순서에 포함
        dfs(R);
        
        for(int i = 1 ; i < visited.length ; i++) {
            sb.append(visited[i]).append("\n");
        }
        System.out.println(sb);   
    }
    
    private static void dfs(int num) {
        visited[num] = cnt; // 📍 탐색할 노드에 순위 저장 📍
        
        for(int i = 0 ; i < A[num].size() ; i++) {    // 📍 인접 정점 탐색 📍
            int next = A[num].get(i);
            
            if(visited[next] == 0) {
                cnt++;
                dfs(next);
            }
        }
    }
}

✅ 해결 아이디어
✔ DFS

 

💥 유의사항

• 인접 행렬로 풀면 O(n^2)으로 메모리 초과한다 함 (참고)

 

 

---

💬 느낀 점

기본 문제인데... dfs 함수 인자에 cnt값 가져가려고 막 하다가 계속 1%에서 틀렸었다,,,

이렇게 하면 틀림.. 왠지는 모르겠음.

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[자바] 백준 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 (boj java)