[이것이 코딩 테스트다 with Java] 깊이 우선 탐색과 너비 우선 탐색 (DFS & BFS)

깊이 우선 탐색과 너비 우선 탐색 (DFS & BFS)

 

탐색

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 두 알고리즘을 이해하기 위해서는 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다.

• 깊이 우선 탐색(DFS, Depth First Search):
  • 동작 원리: 스택
  • 구현 방법: 재귀 함수 사용
  • 탐색 순서: 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5 (1부터 시작하고 작은 순서부터 탐색한다고 가정)
  • 수행 과정
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
    2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리하고 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
• 너비 우선 탐색 (BFS, Breadth First Search): 가까운 노드부터 탐색하는 알고리즘 
  • 동작 원리: 큐
  • 구현 방법: 큐 자료 구조 사용
  • 탐색 순서: 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6 (1부터 시작하고 작은 순서부터 탐색한다고 가정)
  • 수행 과정
    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

 

자료 구조

데이터를 표현하고 관리하고 처리하기 이한 구조를 의미하고 그 중 스택과 큐는 자료구조의 기초 개념으로 삽입과 삭제 두 가지 핵심적인 함수로 구성된다. 스택은 선입후출 구조를 큐는 선입선출 구조를 가지고 있다. 

 

깊이 우선 탐색(DFS)

자바로 작성한 깊이 우선 탐색의 소스 코드는 아래와 같다.

import java.util.*;

public class Main
{
    public final static int GRAPH_LIST_SIZE = 9;
    public static boolean[] visitedFlag = new boolean[GRAPH_LIST_SIZE];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    
    public static void main(String[] args) {
        // 리스트 초기화
        for (int i = 0; i < GRAPH_LIST_SIZE; i++) {
            graph.add(new ArrayList<Integer>());
        }
        
        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        dfs(1);
    }
	
    // DFS 탐색을 위한 재귀함수
    public static void dfs(int point){
        // 현재 노드 방문 처리 
        visitedFlag[point] = true;
        System.out.print(point + " ");
	    
        // 인접 노드 방문
        for(int node : graph.get(point)){
            if(!visitedFlag[node]){
                 dfs(node);
            }
        }
    }
}

 

너비 우선 탐색(BFS)

자바로 작성한 너비 우선 탐색의 소스 코드는 아래와 같다.

import java.util.*;

public class Main
{
    public final static int GRAPH_LIST_SIZE = 9;
    public static boolean[] visitedFlag = new boolean[GRAPH_LIST_SIZE];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    
	public static void main(String[] args) {
		// 리스트 초기화
        for (int i = 0; i < GRAPH_LIST_SIZE; i++) {
            graph.add(new ArrayList<Integer>());
        }
        
        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        bfs(1);
	}
	
	// BFS 탐색을 위한 재귀함수
	public static void bfs(int point){
	    Queue<Integer> queue = new LinkedList<Integer>();
	    
	    // 현재 노드 방문 처리 
	    queue.offer(point);
	    visitedFlag[point] = true;
	    
	    while(!queue.isEmpty()){
	        int target = queue.poll();
	        System.out.print(target + " ");
	        
	        // 인접 노드 방문
	        for(int node : graph.get(target)){
	            if(!visitedFlag[node]){
	                queue.offer(node);
	                visitedFlag[node] = true;
	            }
	        }
	    }
	    
	}
}

 

예제 1 - 음료수 얼려 먹기

난이도 ●◐○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

문제 N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 
이때 얼음 틀의 모양이 주어졌을 때 생성되는 아이스크림의 총 개수를 구하는 프로그램을 작성하시오.
다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

 

입력 조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 ≤ N, M ≤ 1,000)
• 두 번째 줄부터 N+1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

 

출력 조건

• 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
15 14 00000111100000 11111101111110 11011101101110 11011101100000 11011111111111 11011111111100 11000000011111 01111111111111 00000000011111 01111111111000 00011111111000 00000001111000 11111111110011 11100011111111 11100011111111	8

 

요점

• DFS를 적용한다.
• 상하좌우를 인접한 노드라고 본다.

 

소스 코드

import java.util.*;

public class Main
{
    public static int n;
    public static int m;
    public static int frame[][];
    
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt();
		m = scan.nextInt();
		frame = new int[n][m];
		
		scan.nextLine();
		
		for(int i = 0; i < n; i++){
		    String row = scan.nextLine();
		    
		    for(int j = 0; j < m; j++){
		        frame[i][j] = Character.getNumericValue(row.charAt(j));
		    }
		}
		
		int iceCnt = 0;
		
		// 모든 칸에 음료수 채우기
	    for(int x = 0; x < n; x++){
		    for(int y = 0; y < m; y++){
		        if(dfs(x, y)){
		          iceCnt++;            
		        }
		    }
		}
		
		System.out.println("result = " + iceCnt);
	}
	
	public static boolean dfs(int x, int y){
	    // 범위를 넘어갈 경우 처리
	    if(x <= -1 || y <= -1 || x >= n || y >= m) return false;
	   
	    if(frame[x][y] == 0){
	        // 방문 처리
	        frame[x][y] = 1; 
	        
	        dfs(x - 1, y);
	        dfs(x + 1, y);
	        dfs(x, y - 1);
	        dfs(x, y + 1);
	        
	        return true;
	    } else {
	        return false;
	    }
	}
	
}

 

예제 2 - 미로 탈출

난이도 ●◐○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

동빈이는 N x M 미로에 갇혀있다. 동빈이의 위치는 (1,1) 이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있으며 괴물을 피해 탈출해야 한다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력 조건

• 첫째 줄에 두 정수 N, M (4 ≤ N, M ≤ 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수 (0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
5 6 101010 111111 000001 111111 111111	10

 

요점

• BFS를 적용한다.
• 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.
• 0, 0 칸은 1이 아니어도 상관 없다. 최종적으로는 3이 출력되는데 나는 이걸 어떻게 처리해야 되나 고민했지만 굳이 처리할 필요가 없다.

 

소스 코드

import java.util.*;

// 좌표 저장을 위한 Class
class Position {
    int x;
    int y;
    
    public Position(int x, int y){
        this.x = x;
        this.y = y;
    }
    
    public int getX(){ return this.x; }
    public int getY(){ return this.y; }
}

public class Main
{
    public static int n;
    public static int m;
    public static int maze[][];
    
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt();
		m = scan.nextInt();
		maze = new int[n][m];
		
		scan.nextLine();
		
		for(int i = 0; i < n; i++){
		    String row = scan.nextLine();
		    
		    for(int j = 0; j < m; j++){
		        maze[i][j] = Character.getNumericValue(row.charAt(j));
		    }
		}
		
		System.out.println("result = " + bfs(0, 0));
	}

	public static int bfs(int x, int y){
	    //상하 좌우 이동 방향 
	    int directionX[] = {-1, 0, 1, 0};
	    int directionY[] = {0, 1, 0, -1};
	    
	    Queue<Position> queue = new LinkedList<Position>();
	    queue.offer(new Position(x, y));
	    
	    while(!queue.isEmpty()){
	        Position now = queue.poll();
	        
	        for(int i = 0; i < directionX.length; i++){
	            int nextStepX  = now.getX() + directionX[i];
	            int nextStepY = now.getY() + directionY[i]; 
	            
	            // 범위를 넘어갈 경우 
	            if(nextStepX <= -1 || nextStepY <= -1 || nextStepX >= n || nextStepY >= m) continue;
	            
	            // 처음 방문하는 경우에만
	            if(maze[nextStepX][nextStepY] == 1){
	                maze[nextStepX][nextStepY] =  maze[now.getX()][now.getY()] + 1;
	                queue.offer(new Position(nextStepX, nextStepY));
	            }
	        }
	    }
	    
	    return maze[n-1][m-1];
	}
}

 

탐색 예제를 풀어본 후

DFS와 BFS는 너무 유명한 알고리즘이라 많이 봐왔지만 막상 구현을 하려고 하면 그때마다 고민을 하게 되는 문제인 것 같다. 우선 구현 문제처럼 로직은 쉽게 이해가 돼도 실제로 코드로 구현하기가 쉽지 않다. 최근에도 실행 순서 관련해서 DFS 알고리즘을 변형하여 실무에 적용한 적이 있었는데 그때도 꽤나 고민을 했던 기억이 있다. 이 알고리즘을 예제로 풀어본 적이 거의 없어서 예제 문제는 어려웠다. 내가 푼 거 60% 나동빈님께서 풀어주신 게 40% 정도인 것 같은데 둘 중 어떤 알고리즘을 정해야 할지 헷갈리는 것도 컸다. 그래도 다음에 또 이런 문제를 만나면 풀이 과정을 지금보다는 수월하게 생각해낼 수 있을 것 같다. 제발 부탁 소원!

 

 

GitHub: https://github.com/Leeyeonjae/coding-test/tree/main/5_DFS_BFS

참고서적 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈