[2024.10.29(화)] 코드트리 : DFS/그래프 탐색

 

억만년만에 코테문제를 풀었다.

오랜만에 푸는 것인만큼 쉬운 문제를 골라서 풀었음.

 

 

https://www.codetree.ai/missions/2/problems/graph-traversal/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

난이도

• 하
• 나중에 긴가민가 할 때 코드 한번 다시 보는 정도면 충분

 

배운 점 + 실수한 점

• 그래프 탐색을 할 수 있는 방법에는 2가지가 있다는 것
  1. 2차원 배열 활용
  2. 인접리스트 활용(1차원 배열 각각에 ArrayList 달아둔거임)
• arraylist의 메서드를 활용할 때, []가 아니라 ()라는 점(계속 get[]으로 쓰려고 해서 컴파일 오류가 났다)

import java.util.*;
public class Main {
    static int n;
    static int m;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int vertexNum = 0;

    public static void DFS(int vertex){
        for(int i = 0; i<graph[vertex].size(); i++){
            int currV = graph[vertex].get(i);
            if(!visited[currV]){
                vertexNum++;
                visited[currV] = true;
                DFS(currV);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        graph = new ArrayList[n+1];
        visited = new boolean[n+1];
        visited[1] = true;

        for(int i = 0; i<n+1; i++){
            graph[i] = new ArrayList<Integer>();
        }
        for(int i = 0; i<m; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            graph[start].add(end);
            graph[end].add(start);
        }
        DFS(1);
        System.out.println(vertexNum);
    }
}