[ DFS / BFS ] 개념 및 예제 정리

코딩테스트에서 자주 사용되는 완전 탐색 기법 DFS/BFS 정리

자주 나오기도 하고... 중요하기도 해서 복습겸 정리하는 포스팅!

---

DFS 

🌷특징 및 언제 사용? 

- 탐색 공간 자체는 크지만 깊이가 유한할 때(공간 복잡도가 작다)

- 최단 경로가 아니어도 괜찮을 때

- 재귀함수로 구현 -> 현재 검사하는 상태에서 전이할 수 있는 상태라면 해당 상태로 전이

- 시작하는 부분에서 한쪽 분기 정하고 최대 깊이까지 탐색 후 다른 분기로 이동, 다시 최대 깊이까지 탐색 ... 

- 단절점 찾기, 단절선 찾기, 위상정렬, 사이클 찾기 등.. 

 

🌷기본 코드 구현 시 필요한 것 

- 방문 여부를 저장할 방문 여부 배열

- 재귀함수로 구현하거나 스택 활용! 

 

🌷 로직  

1. while (스택에 값이 있는 동안)

2. 방문 여부 검사

3. state 변수(현재 방문한 변수)에 대한 처리(문제마다 다름)

4. 다음에 방문해야할 자료에 대해 범위, 방문 여부 등 문제에 따라 조건 검사

5. 조건에 위배되지 않으면 스택에 push or 재귀 함수 호출

boolean isVisited[] = new boolean[n];
Stack<Integer> stack = new Stack<>();

while (!stack.isEmpty()) {
    int state = stack.pop();
    if (isVisited[]) {
    	// continue 또는 리턴 
    }
    isVisted[state] = true;
    for (int next : getNext(state)) {
    	if (!isVisted[next]) {
        	stack.push(next);
        }
    }
}

// 재귀로 구현한다면 
static void DFS(int node) {
	if (visited[node]) {
		return ;
    } // 이미 방문한 노드인 경우엔 수행 X
    visited[node] = true; // 한 번 지난 노드는 다시 안 지나가게끔
    for (int i : graph[node]) {
    	if (!visited[i]) {
        	DFS(i);
        }
    }
}

 

 

🌷프로그래머스 lv3 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

DFS긴 DFS인데 처음에 구하려는 답을 내가 잘못 생각했다. 문제이해를 잘못했었는데, 제대로 이해해도 못풀어서 해설을 보고 코드를 짰다ㅎ... 

 여기서의 visited는 각 컴퓨터별로 연결된거 모두 탐색해봤는지를 저장하는 배열이다. 이 visited를 계속 DFS함수 매개변수로 넣어주고, 한 컴퓨터당 탐색이 끝나면 answer++해준다. 

어려운 문젠 아닌거같은데 아직 부족하군...허허 

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        int answer = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }
            DFS(i, computers, visited);
            answer++;
        }
        return answer;
    }
    
    void DFS(int now, int[][] computers, boolean[] visited) {
        Stack<Integer> stack = new Stack<>(); 
        stack.push(now);
        
        while (!stack.isEmpty()) {
            int temp = stack.pop();
            if (visited[temp]) {
                continue;
            }
            visited[temp] = true;
            for (int i = 0; i < computers[temp].length; i++) {
                if (computers[temp][i] == 0) {
                    continue;
                }
                if (temp != i) {
                    stack.push(i);
                }
            }
        }
    }
}

 

---

BFS 

🌷특징 및 언제 사용? 

- 초기 상태에서 가까운 상태부터 탐색

- 최단 거리나 최단 시간 등 목표 상태에서 도달할 수 있는 가장 빠른 경로 탐색 

- 탐색 공간의 깊이 제약이 없는 편이나 공간복잡도가 크다 

- 큐를 사용, 큐가 탐색 공간을 나타내고 큐에 다음 탐색할 것들을 추가하는 방식으로 진행 .. 

 

🌷DFS와 차이점? 

- 스택 대신 큐를 사용 

- 큐에 넣어줄 때 방문 처리를 한다는 점

boolean[] isVisited = new boolean[n];
Queue<Integer>() queue = new LinkedList<>();
queue.add(0); //초기 상태 저장
isVisited[0] = true;

while (!queue.isEmpty()) {
	int now = queue.poll();
    for (int next : getNextStates(now)) {
    	// 방문 여부 외에 추가할만한 검사 조건들 추가하기 
    	if (isVisted[next]) {
        	continue;
        }
    }
    isVisited[next] = true;
    queue.add(next);
}

 static void BFS(int num) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(num);
        isVisited[num] = true;

        while(!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");
            for (int i : graph[now]) {
                if (!isVisited[i]) {
                    isVisited[i] = true;
                    queue.add(i);
                }
            }
        }
    }

 

 

🌷프로그래머스 level3 단어변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

🌷로직 

- 하나의 문자만 다른지 검사(word1 -> word2 바꿀 수 있는지 여부 검사하는 함수)

     -> boolean canChange(String word1, String word2) 

- 바꿀 수 있는 단어들을 다 큐에 넣어두고 탐색 수행 (BFS)

- 큐에서 꺼낼 때마다 target과 같은 문자열인지 확인, 맞다면 답 리턴

- 큐가 다 비었는데도 리턴되지 않았다 => 전환이 불가능하다는 뜻이므로 0 리턴 

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<Word> queue = new LinkedList<>(); 
        boolean[] visited = new boolean[words.length];
        queue.add(new Word(begin, 0));
    
        while (!queue.isEmpty()) {
            Word w = queue.poll();
            if (w.st.equals(target)) {
                return w.count; // 꺼냈는데 target과 같다면 답 리턴
            }
            for (int i = 0; i < words.length; i++) {
                if (!visited[i]) {
                    if (canChange(w.st, words[i])) {
                        visited[i] = true;
                        queue.add(new Word(words[i], w.count+1));
                    }
                }
            }
        }
        return 0; // 다 돌아도 답 안나오는 경우 
    }
    
    public boolean canChange(String word1, String word2) {
        int count = 0;
        char[] first = word1.toCharArray();
        char[] second = word2.toCharArray();
        for (int i = 0; i < word1.length(); i++) {
            if (first[i] != second[i]) {
                count++;
            }
            if (count > 1) {
                return false;
            }
        }
        return true;
    }
    
    class Word {
        String st;
        int count;
        public Word(String s, int c) {
            this.st = s;
            this.count = c;
        }
    }
}