[프로그래머스] 단어변환

문제  : 단어 변환

[ 문제 출처 ]   https://programmers.co.kr/learn/courses/30/lessons/43163

 

 

[문제 풀이] 

 

이 문제의 경우 주어진 문제를 그래프로 표현할 수 있어야 한다 즉 "그래프 모델링"을 해주어야 한다

어떤 것을 그래프의 정점으로 사용할 것이고 정점과 정점을 잇는 간선의 연결은 어떻게 정할 것인지 등이 있다

 

이 문제의 그래프 모델링 과정을 살펴보자!

정점은 어떤 것으로 사용해야 할 까?  words에 있는 단어로 하면 좋지 않을까? 

정점과 정점을 잇는 간선은 어떻게 연결시켜야 할까? 알파벳을 단 한 개만 바꾸어 해당 단어로 표현할 수 있다면

이는 연결 되었다고 볼 수 있다 즉 

"hot" -->  "hit" , "hot" --> "dot"  알파벳 차이가 단 1개인 경우이므로 이는 서로 연결되었다고 볼 수 있다 그래야

문제에서 요구하는 최소 단계의 과정을 찾을 수 있다 당연히 가중치는 1이 되겠다!

 

가중치가 1이 아닌 값이 존재했다면 이는 BFS가 아닌 다른 최단 경로 문제로서 풀어야겠지만

그래프를 모델링 해보면 가중치가 1인 값만 존재하게 되므로 단순하게 BFS로 접근해 답을 구 할 수 있다

 

여기서 words에 있는 단어들을 정점으로 표현한다고 했는데 그러지 말고 숫자로 바꿔도 상관없다!

words에 있는 순서들은 변하지 않고 각 단어들의 index 들을 정점의 번호로 쓰도록 하자!

 

 

[소스 코드]

 

#include <string>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int MAX = 50;
int dist[MAX];
vector<int> adj[MAX];        // 인접리스트로 그래프를 표현// 정점을 연결 시킬 수 있는지 각단어의 알파벳 차이가 1개인지 확인하는 함수
bool isAdj(vector<string> words, int from, int to, int ss) {
    int diff = 0;
    for (int i = 0; i < ss; i++) {
        if (words[from][i] != words[to][i]) diff++;
    }
    return diff == 1;
}
int solution(string begin, string target, vector<string> words) {
    words.push_back(begin);
    int ss = begin.size(), n = words.size(), answer = 0;
    // 그래프 모델링 과정
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (isAdj(words, i, j, ss)) adj[i].push_back(j);    // 각 단어의 차이가 알파벳 1개차이라면 연결 시킨다!
        }
    }
    // 출발점과 도착점의 인덱스를 찾는다
    int start = -1, end = -1;
    for (int i = 0; i < n; i++) {
        if (words[i] == begin) start = i;
        if (words[i] == target) end = i;
    }
    memset(dist, -1, sizeof(dist));
    // 목적지가 존재 하지 않다면 정답을 구할 수 없다..
    if (end == -1) {
        answer = 0;
    }
    else {
        queue<int> q;
        q.push(start);
        dist[start] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = 0; i < adj[x].size(); i++) {
                int y = adj[x][i];
                if (dist[y] != -1) continue;
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
        cout << dist[end] << '\n';
        if (dist[end] == -1) answer = 0;
        else answer = dist[end];
    }
    return answer;
}