프로그래머스/고득점키트/BFS/DFS/단어변환

오늘 날씨가 좋다.

문제 풀기 좋은 날씨다.

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

알고리즘 연습 - 단어 변환 | 프로그래머스

해당 문제는 DFS, or BFS를 활용하는 문제다. 

Words 의 각 원소 Node 들을 서로 변형이 가능한(간선으로 연결이 가능한) Node끼리 이어 붙여서, 시작 단어를 기점으로 DFS or BFS탐색을 해준 뒤, 찾고자하는 타겟 단어를 먼저 탐색하였는지 판별하고, 타겟 단어가 탐색되었으면  시작점으로부터 떨어진 거리를 반환해준다. 

말은 쉬운데, Node가 string형태로 와있는게 참 생소해서 구현에 어려움을 겪을 수 있다. 이해한다. 

아래와 같이 좀 더 컴퓨터 관점에서의 알고리즘을 설계하였다.

1. BFS를 택하자. BFS를 선택한 이유로는 시작점을 기준으로 인접한 노드순으로 탐색하기 때문에 기준점과 각 노드간의 떨어진 거리를 구하기에 적합하다 생각하였다.

2. 굳이 기존의 Graph 구현 자체에 신경쓰지 않고 접근했다. 핵심은 a. 현재 시작점에서 인접 노드가 연결되어있는지, b. 시작점으로부터의 거리 계산 , 이 두가지다. 여기서, unordered_map dist<string, int>를 통해 기준노드로부터의 거리 map을 잡았고, 방문했는지 유무만을 체크하기 위해 unordered_map visited<string, bool> 로 queue에 넣을지 유무를 확인사살했다.

---

[구현코드]

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

using namespace std;
unordered_map<string, int> dist;
unordered_map<string, bool> visit;

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<string> q;

    for(int i = 0; i < words.size(); i++){
        visit[words[i]] = false;
        dist[words[i]] = 0;
    }
    //각 단어 길이는 테스트 케이스에 따라 다르므로 단어 길이를 받아주도록 한다.
    int word_length = begin.size();
    q.push(begin);
    dist[begin] = 0; //시작점의 위치는 0이다.
    visit[begin] = true; // 시작점은 우선 방문 체크
    while(!q.empty()){ //BFS Start!
        string here = q.front();
        q.pop();
        
        for(int j = 0; j < words.size(); j++){
            int cnt = 0;
            for(int k = 0; k < word_length; k++){
                    if(here[k] == words[j][k]){
                        cnt++;
                    }
                    if(cnt == word_length-1){ // 1개 철자만 다르면 노드로 연결된다.
                        string there = words[j];
                        if(visit[there] == false && dist[there] == 0){
                            dist[there] = dist[here]+1; // 기존 노드에서 거리 1만큼 증가
                            visit[there] = true; // 방문으로 체크하자.
                            q.push(there);
                        }
                        break;
                    }
            }
        }
    }
    if(visit[target] == false){ // 타겟을 방문하지 못했으면, visit[target]이 마킹되지 않으므로
        answer = 0;
    }
    else{
        answer = dist[target];
    }
    return answer;
}