dfs, bfs 개념

dfs(깊이 우선 탐색)

DFS란 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프를 탐색할 때 특정한 경로로 쭉 타고 밑바닥까지 내려간 후 막다른 길에 도착하면 다시 돌아와 다른 경로로 탐색하는 것이다.

• 스택이나 재귀함수로 구현한다.

  • 스택을 활용한 DFS
    1. 시작 정점을 스택에 삽입한다.
    2. 스택에서 하나의 정점을 꺼낸다.
    3. 스택에서 꺼낸 정점이 아직 방문하지 않은 정점이라면, 방문 표시 후 이웃 정점들을 스택에 삽입한다.
    4. 스택에 담긴 정점이 없을 때까지 2-3번 과정을 반복한다.

bfs(너비 우선 탐색)

BFS란 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 알고리즘이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 탐색하는 것이다.

• 큐를 사용하여 구현한다.

  • 큐를 활용한 BFS
    1. 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에 방문하지 않은 노드들을 모두 큐에 삽입하고, 방문 처리 해준다.
    3. 큐에 남은 요소가 없을 때까지 반복해준다.

알고리즘 문제 생각 흐름

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43163

생각 흐름
일단 bfs랑 dfs 문제라는 것을 알고 풀어서 그런지 어떻게든 그쪽 방향으로 생각하려고 노력한 것 같다. 접근 방식 생각만 꽤 오래 걸린것 같다. 문제에서 최소 몇 단계를 거쳐서 begin을 target으로 변환할 수 있는지를 물어서 bfs로 접근해보았다.

먼저 두 단어에서 다른 알파벳이 몇 개인지 알기 위해 compareAlphabet이라는 함수를 만들어 주었다. 그리고 방문 여부를 알기 위해 check배열을 만들어 주었다.

solution 함수에서는 words벡터 안에 target이 없다면 변환될 수 없으므로 먼저 find로 있는지 확인하고 없으면 0을 리턴해주었다.

만약 있다면, 큐에 begin과 0을 삽입하고 큐가 빌 때까지 반복해주었다.
current과 target이 같다면 그때 count의 값을 리턴해주었다.
같지 않다면 compareAlphabet으로 방문하지 않고 current와 words의 다른 단어들과 반복문으로 비교하여 다른 알파벳이 1이라면 큐에 넣어주는 방식으로 구현하였다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

bool check[51] = {false,};

bool compareAlphabet(string s1, string s2){
    int different = 0;
    for(int i=0;i<s1.length();i++){
        if(s1[i] != s2[i])different++;
    }
    if(different == 1)return 1;
    else return 0;
}

int solution(string begin, string target, vector<string> words){
    int answer = 0;
    if(find(words.begin(),words.end(),target) == words.end()){
        return 0;
    }
    queue<pair<string,int> > q;
    q.push({begin,0});

    while(!q.empty()){
        string current = q.front().first;
        int count = q.front().second;
        q.pop();
        if(current == target){
            answer = count;
            return answer;
        }

        for(int i=0;i<words.size();i++){
            if(!check[i] && compareAlphabet(current,words[i])){
                check[i] = true;
                q.push({words[i],count+1});
            }
        }
    }
    return answer;
}

int main(void){
    string begin = "hit";
    string target = "cog";
    vector<string> words = {"hot","dot","dog","lot","log","cog"};
    cout<< solution(begin,target,words)<<'\n';
}