[코딩테스트] DFS 와 BFS 정리

1. DFS

✅ DFS

깊이 우선 탐색

• 스택 자료구조 또는 재귀함수를 이용

 

2. BFS

✅ BFS

너비 우선 탐색

• 큐 자료구조 이용

 

3. 문제

https://school.programmers.co.kr/learn/courses/30/parts/12421

프로그래머스

 

1) 타겟넘버

정답 )

// DFS를 이용
class Solution {
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
    	// 조건에 해당하는 재귀함수를 호출 (-/+)
        dfs(-1 * numbers[0], 1, numbers, target);
        dfs(numbers[0], 1, numbers, target);
        
        return answer;
    }
    // 재귀함수
    public void dfs(int num, int cnt, int[] numbers, int target) {
    	// 종료 조건
        if(cnt == numbers.length){
        	// 타겟넘버 확인
            if(num == target){
                answer++;
            }
            return;
        }
		// 종료조건에 해당할때 까지 반복 (-/+)
        dfs(num - numbers[cnt], cnt+1, numbers, target);
        dfs(num + numbers[cnt], cnt+1, numbers, target);
    }
}

 

2) 게임 맵 최단거리

정답 ) 

// BFS를 이용
import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int rowLen = maps.length; // 행 최대길이
        int colLen = maps[0].length; // 열 최대길이
        int[][] visited = new int[rowLen][colLen]; // 방문한 지역
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[2]);
        visited[0][0] = 1; // 시작점 (0,0)
        
        while(!queue.isEmpty()){
            int[] pos = queue.poll(); // 큐에서 먼저들어가있는 값 제거하면서 반환
            int row = pos[0];
            int col = pos[1];
            if(row == rowLen -1 && col == colLen -1){
            	// 도착 지점
                return visited[row][col];
            }
            int cnt = -1;
            for(int i=0; i<4; i++){
            	// 상,하,좌,우 네번 이동가능
                int rowMove = pos[0] + (i%2 == 0 ? cnt : 0);
                int colMove = pos[1] + (i%2 > 0 ? cnt : 0);
                // 이동 불가
                if(0 <= rowMove && rowMove < rowLen && 0 <= colMove && colMove < colLen) {
                	// 이미 방문했거나 벽에 막혔을때
                    if(maps[rowMove][colMove] != 0 && visited[rowMove][colMove] == 0){
                    	// 큐 추가
                        queue.offer(new int[]{rowMove, colMove});
                        // 방문 지역에 최단 거리 값 추가
                        visited[rowMove][colMove] = visited[row][col] + 1;
                    }
                }
                if(i == 1) cnt *= -1;
            }
        }
        // 도착 불가
        return -1;
    }
}