Developer : 태하팍/코딩 테스트

코테준비) 간단 DFS를 풀어보자!

태하팍 2025. 11. 12. 13:48
반응형
코딩테스트...준비하지 않으면 못풉니다ㅋㅋㅋ
차근차근 준비를 해보아요!!! 
  •  DFS : 너비 우선 탐색, 쭉~~따라가는 스타일!! 그래프 완전 탐색
    • 재귀함수로 구현, 스택자료구조 이용
    • 시간복잡도 : O(V + E) 
      • V : 노드 수
      • E : 엣지 수 
      • 아래에서 N이 노드,  M이 엣지 = O(1000 + 1000*(1000-1)/2) 1억정도 안넘으면 오케이!
    • 백준(연결 요소의 개수)

문제

아래의 포맷으로 시작!! 

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

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());        
        int N = Integer.parseInt(st.nextToken()); // 정점의 개수
        int M = Integer.parseInt(st.nextToken()); // 간선의 개수 
        
    }
}

input : 첫번째 줄에 정점의 개수 N과 간선의 개수 M / 두번째 줄부터는 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.

6 5
1 2
2 5
5 1
3 4
4 6

output : 연결요소의 개수를 출력

2

문제를 풀기 위해 필요한 것?

6개의 정점(graph)에 대한 변수
간선 5개 - 정점에 넣어줘야 한다. 서로 연결!
1  2
2  5
5  1
3  4
4  6
방문체크 : visited (boolean) - 방문했던건 다시 재방문 하지 않는다.
재귀함수(dfs())-어떤 기능을 반복적으로 처리해줘야하나??
방문체크에 대한 로직, 정점에 붙어있는 간선들의 데이터(또 다른 정점)를 가져와서 체크 -> 재귀 함수호출  
리턴 : 연결된 개수 

6개의 정점(graph)에 대한 변수 그리고 방문체크 visited boolean 객체 생성(default false)

// static으로 만들어줘야 함 / dfs 재귀함수에서 사용
static boolean [] visited;
static List<Integer>[] graph;

public static void main(String[] args) throws Exception {

   graph = new ArrayList[N+1];
   visited = new boolean[N+1];
        
   for(int i = 1; i <= N; i++) {              
	   graph[i] = new ArrayList<>();          // 초기화 
   }

 정점을 받아서 서로 연결 시켜줍니다. 양방향이라 서로 연결시켜 줍니다.

// save data
for(int j = 1; j <= M; j++) {
	st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    graph[v].add(u); // graph 연결
    graph[u].add(v);
}

이제 서로 연결된 상태 입니다.

이제 방문하면서 체크를 해줘야 합니다.

 int cnt = 0;
 for(int t=1; t <= M; t++) {
 	if(!visited[t]) { // 방문하지 않았다면 아래 수행(false)
    	dfs(t);
        cnt++;
    }
 }

 System.out.println(cnt);

dfs()재귀함수의 역할은?
아래처럼 방문했다는 표시를 해주고
연결된 다음 정점으로 이동합니다.(재귀함수 호출)
다시 방문했다고 표시를 해주며 다음 정점으로 이동 (반복)

즉, graph[node]에 연결된 다른 정점들을 가져와서 체크 합니다. 깊게 쭉~~들어가겠죠!
아직  for문이 끝나지 않았을테구요
다시 재귀로 dfs를 호출하면 또 for문을 통해 연결된 것들을 가져옵니다.
가져왔는데 아직 방문하지 않은게 있다면 다시 dfs()재귀함수 호출!

결국은 호출한 for문들로 돌아가게 됩니다.
나중엔 cnt++;해주고 다시 for문을 돌겠죠!

public static void dfs(int node) {
    visited[node] = true;
    for(int i=0; i < graph[node].size(); i++) { // for(int i : graph[node])
        int next = graph[node].get(i);
        if(!visited[next]) dfs(next);
    }
}

좀 더 반복해서 풀어보도록 합시다!!

반응형