DFS 알고리즘

 

 

 

 

 

DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 깊이 방향으로 그래프를 탐색하는 방법입니다. DFS는 스택(Stack) 또는 재귀 함수를 통해 구현할 수 있습니다.

 

DFS의 동작 방식은 다음과 같습니다:

1. 시작 노드를 방문하고, 해당 노드를 방문한 것으로 표시합니다.
2. 현재 노드와 연결된 이웃 노드들 중에서 아직 방문하지 않은 노드를 선택합니다.
3. 선택한 이웃 노드로 이동하여 재귀적으로 탐색합니다. 선택한 이웃 노드가 없을 때까지 이 과정을 반복합니다.
4. 모든 이웃 노드를 방문한 후에는 이전 단계로 돌아가서 다음 이웃 노드를 선택하고 탐색을 진행합니다.
5. 스택이 비어있을 때까지 위 과정을 반복합니다.

DFS는 깊이를 우선으로 탐색하기 때문에, 그래프의 한 가지 경로를 가능한 멀리까지 탐색한 후에 다른 경로를 탐색합니다. 이러한 특성 때문에 DFS는 미로 찾기, 그래프 연결 여부 확인, 그래프의 사이클 검사 등 다양한 문제에서 활용될 수 있습니다.

다만, DFS는 무한 루프에 빠질 가능성이 있으며, 방문한 노드를 기록해야 한다는 점에서 메모리 사용량이 크게 증가할 수 있습니다. 또한, 그래프가 순환 구조를 가지고 있을 경우에는 탐색이 끝나지 않을 수 있습니다. 이러한 단점을 보완하기 위해 백트래킹 등의 기법을 함께 활용할 수 있습니다.

 

 

 

 

 

 

DFS 알고리즘과 BFS 알고리즘 중 어떤 것을 선택해야 할까?

 

1. 탐색 순서:
   • 목표는 그래프에서 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 수행하여 원하는 결과를 찾는 것입니다.
   • 만약 최단 경로를 찾아야 한다면, BFS가 더 적합합니다. BFS는 레벨별로 탐색하므로 가까운 이웃 노드를 먼저 방문하게 되어 최단 경로를 찾을 수 있습니다.
   • 만약 해를 찾기 위해 모든 경로를 탐색해야 한다면, DFS가 더 적합합니다. DFS는 깊은 경로를 우선으로 탐색하므로 가능한 모든 경로를 탐색할 수 있습니다.
2. 메모리 사용량:
   • DFS는 스택(Stack)을 사용하여 탐색 경로를 추적합니다. 재귀적으로 구현되는 경우 호출 스택의 깊이가 커질 수 있습니다. 따라서 메모리 사용량이 크게 요구되지 않는 경우에 적합합니다.
   • BFS는 큐(Queue)를 사용하여 탐색을 수행합니다. 모든 인접한 노드를 큐에 저장하므로 탐색할 노드의 수에 따라 메모리 사용량이 증가합니다. 그래프의 크기가 크고 메모리 제한이 있는 경우에는 메모리 사용량을 고려해야 합니다.

 

 

 

 

---

프로그래머스 - 게임 맵 최단거리

-> 정확성 100%

-> 효율성 실패 ㅜㅜ

최단 거리이므로 BFS를 사용하는게 더 적합하다.

 

 

class Solution {
    boolean[][] visited;
    int[][] direction = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int min = Integer.MAX_VALUE;
    
    public int solution(int[][] maps) {
        int[] idx = {0, 0};
        visited = new boolean[maps.length][maps[0].length];
        visited[0][0] = true;
        dfs(idx, maps, 1);
        if(min == Integer.MAX_VALUE) {
            return -1;
        }
        return min;
    }
    
    public void dfs(int[] idx, int[][] maps, int count) {
        if(count >= min) {
            return;
        }    
        for(int i=0; i<4; i++) {
            int row = idx[0] + direction[i][0];
            int column = idx[1] + direction[i][1];
            if(row < 0 || row > maps.length - 1 || column < 0 || column > maps[0].length - 1) {
                continue;
            }
            if(maps[row][column] == 0 || visited[row][column] == true) {
                continue;
            }
            if(row == maps.length-1 && column == maps[0].length-1) {
                min = Math.min(min, count + 1);
                return;
            }
            int[] tmpIdx = {row, column};
            visited[row][column] = true;
            dfs(tmpIdx, maps, count + 1);
            visited[row][column] = false;
        }
    }
}

 

 

 

 

 

---

 

프로그래머스 - 피로도

-> 성공

 

class Solution {
    boolean[] visited;
    int count;
    
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(0, k, dungeons);
        return count;
    }
    
    public void dfs(int depth, int fatique, int[][] dungeons) {
        for(int i=0; i<dungeons.length; i++) {
            if(visited[i] || fatique<dungeons[i][0]) {
                continue;
            }
            visited[i] = true;
            dfs(depth+1, fatique - dungeons[i][1], dungeons);
            visited[i] = false;
        }    
        count = Math.max(depth, count);
    }
}

 

 

---

백준 - 연산자 끼워넣기

 

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

public class Main {
    static int[] signs;
    static int[] num;
    public static int max = Integer.MIN_VALUE;
    public static int min = Integer.MAX_VALUE;

    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());

        st = new StringTokenizer(br.readLine());
        num = new int[n];
        signs = new int[4];

        for(int i=0; i<n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<4; i++) {
            signs[i] = Integer.parseInt(st.nextToken());
        }

        int cur = num[0];
        for(int i=0; i<4; i++) {
            if(signs[i] > 0) {
                signs[i]--;
                dfs(1, i, cur, n);
                signs[i]++;
            }
        }

        System.out.println(max);
        System.out.println(min);
    }

    public static void dfs(int depth, int sign, int cur, int n) {
//        System.out.println("cur: "+cur+", depth: "+depth);
        if(sign == 0) {
            cur += num[depth];
        }
        else if(sign == 1) {
            cur -= num[depth];
        }
        else if(sign == 2) {
            cur *= num[depth];
        }
        else {
            cur /= num[depth];
        }

        depth++;
        if(depth == n) {
            max = Math.max(cur, max);
            min = Math.min(cur, min);
            return;
        }

        for(int i=0; i<4; i++) {
            if(signs[i] > 0) {
                signs[i]--;
                dfs(depth, i, cur, n);
                signs[i]++;
            }
        }
    }
}