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

문제

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

 

 

문제풀기

 

1. 깊이 우선 탐색

무방향 그래프에서 깊이 우선 탐색을 사용해 노드 방문 순서를 출력하는 문제였다.

 

2. 무방향 그래프

무방향 그래프니 간선 정보를 입력할 때 양쪽의 노드에 모두 입력해주어야 한다는 생각이 들었다.

 

3. ArrayList

처음엔 그래프 정보를 담기 위해 2차원 배열을 사용할까 했는데 코드를 작성하다 보니 낭비 되는 메모리가 너무 많다고 생각되어 동적으로 크기를 할당하기 위해 2차원 ArrayList를 사용하였다.

 

 

작성한 코드

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static int[] visited;
    public static int cnt;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int start = sc.nextInt();
        
        for(int i=0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i=0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        for(int i=0; i < graph.size(); i++) {
            Collections.sort(graph.get(i));
        }
        
        visited = new int[n+1];
        cnt = 1;
        dfs(start);
        
        for(int i =1; i < visited.length; i++) {
            System.out.println(visited[i]);
        }
    }
    
    public static void dfs(int idx) {
        
        visited[idx] = cnt;
        
        for(int i = 0; i < graph.get(idx).size(); i++) {
            if(visited[graph.get(idx).get(i)] == 0) {
                cnt++;
                dfs(graph.get(idx).get(i));
            }
        }
    }
}