DFS (깊이 우선 탐색)

DFS

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입 선출 구조의 스택 사용

인접 행렬

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

public class AdjMatrix_dfs {
	static int[][] map;
	static boolean[][] visited;
	static int N;
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		visited = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		visited[0][0] = true;
		dfs(0, 0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(visited[i][j] + " ");
			}
			System.out.println();
		}
		br.close();
	}
	static void dfs(int y, int x){
		for(int i = 0; i < 4; ++i){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if(!visited[ny][nx] && map[ny][nx] == 1){
				visited[ny][nx] = true;
				dfs(ny, nx);
			}
		}
	}
}
/*
입력
3
1 1 0
0 1 1
1 0 1
출력
true true false 
false true true 
false false true 
 */

인접 리스트

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

public class AdjList_dfs {
    static List<Integer>[] adj;
    static boolean[] visited;
    static int V, N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        adj = new List[V + 1];
        for (int i = 0; i < V + 1; i++) {
            adj[i] = new ArrayList<>();
        }
        visited = new boolean[V + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            adj[from].add(to);
        }

        visited[1] = true;
        dfs(1);

        for (int i = 1; i < V + 1; i++) {
            System.out.println(visited[i]);
        }
        br.close();
    }
    static void dfs(int now){
        for (Integer there : adj[now]) {
            if(visited[there]) continue;
            visited[there] = true;
            dfs(there);
        }
    }
}
/*
입력
4 5
1 2
1 3
2 3
3 2
3 1
출력
true
true
true
false
 */

DFS 활용

• 출발점에서 도착점까지의 경로의 개수를 구할 때, 사용한다.