그래프의 탐색_DFS

: Depth-First-Search, 루트 노드나 임의의 노드에서 시작하여 최대한 깊숙이 들어가서 탐색한 후 다시 원점으로 돌아가 다른 루트로 탐색하는 방법이다.

 

DFS의 특징

• 자동 미로 생성 또는 미로 탐색에 사용된다.
• 모든 노드를 방문하고자 경우에 사용한다.
• 자기 자신을 호출하는 순환 알고리즘의 형태
• 노드 방문 여부를 확인해야 한다. 그렇지 않을 경우 무한 루프에 빠질 위험이 있다.

 

DFS의 구현

인접 행렬을 이용한 코드

class DFS {
	private int nV;
	private int[][] graph;
	private boolean[] visited;

	public DFS(int nV) {
		this.nV = nV;
		this.graph = new int[nV+1][nV+1];
		this.visited = new int[nV+1];
	}

	public void clear() {
		for(int i = 0; i < visited.length; i++)
			visited[i] = false;
	}

	public void dfs(int V) {
		this.visited[V] = true;
		
        for(int i = 1; i < this.nV + 1; i++)
			if(graph[V][i] == 1 && visited[i] = false)
				dfs(i);
	}
}

 

인접 리스트를 이용한 코드

class DFS {
	private int V; // 정점의 개수
	private ArrayList<ArrayList<Integer>> graph;
	private boolean[] visited;

	public DFS(int V) {
		this.V = V;
		this.graph = new ArrayList<ArrayList<Integer>>();
        
        for(int i = 0; i < V+1; i++) {
        	this.graph.get(i).add(new ArrayList<Integer>());
        }
        
		this.visited = new int[V+1];
	}
    
    public void put(int x, int y) {
		graph.get(x).add(y);
		graph.get(y).add(x);
	} // 양방향 추가

	public void clear() {
		for(int i = 0; i < visited.length; i++)
			visited[i] = false;
	}

	public void dfs(int S) {
		this.visited[S] = true;
		
        for(int i = 1; i < this.V + 1; i++)
			if(graph[S][i] == 1 && visited[i] = false)
				dfs(i);
	}
}

 

DFS 알고리즘 코드

 

출처 : https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    
    public static int N, M, K, count;
    public static int[][] farm;
    public static boolean[][] visited;
    
    public static void dfs(int i, int j) {
        
        visited[i][j] = true;
        
        if(checkCabbage(i - 1, j)) {
            farm[i - 1][j] = count;
            dfs(i - 1, j);
        }
            
        if(checkCabbage(i + 1, j)) {
            farm[i + 1][j] = count;
            dfs(i + 1, j);
        }
            
        if(checkCabbage(i, j - 1)) {
            farm[i][j - 1] = count;
            dfs(i, j - 1);
        }
            
        if(checkCabbage(i, j + 1)) {
            farm[i][j + 1] = count;
            dfs(i, j + 1);
        }
            
        
    }
    
	public static boolean checkCabbage(int row, int col) {
        
        if(row >= N || col >= M || row < 0 || col < 0)
            return false;
        if(farm[row][col] != 1 || visited[row][col] == true)
            return false;
            
        return true;
        
    }
    
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine()); // 테스트케이스
		
		StringBuilder sb = new StringBuilder();
		
		while(T --> 0) {
		
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		    N = Integer.parseInt(st.nextToken());
		    M = Integer.parseInt(st.nextToken());
		    K = Integer.parseInt(st.nextToken());
		
		    farm = new int[N][M];
		    visited = new boolean[N][M];
		    
		    count = 0;
		    
		    for(int i = 0; i < K; i++) {
		    	st = new StringTokenizer(br.readLine(), " ");
		    	int x = Integer.parseInt(st.nextToken());
		    	int y = Integer.parseInt(st.nextToken());
		    	
		    	farm[x][y] = 1;
		    }
		
		    for(int i = 0; i < N; i++)
		        for(int j = 0; j < M; j++)
		            if(farm[i][j] == 1 && visited[i][j] == false) {
        		        count++;
        		        dfs(i, j);
		            }
		            
		    sb.append(count).append("\n");
	    }
	    
	    System.out.println(sb);
	
	}
}

 

---

 

DFS 참고 사이트

• https://freestrokes.tistory.com/88