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

문제

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

코딩테스트 연습 - 단어 변환

주안점

 

 

 

구조

단어를 BFS로 모두 지나며 확인해 본다.

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int cnt, x;
int goal = -1;
queue<int> q;
bool flag = false;
int visited[54];

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    for(int i=0; i<words.size(); i++){
        if(words[i] == target) goal = i;
        cnt = 0;
        for(int j=0; j<begin.size(); j++){
            if(begin[j]!=words[i][j]) cnt++;
            if(cnt>1) break;
        }
        if(cnt==1) {
            if(words[i]==target) answer = 1;
            q.push(i);
            visited[i] = 1;
        }
    }
    if(answer) return answer;
    if(goal==-1) {
        answer = 0;
        return answer;
    }
    while(q.size()){
        x = q.front(); q.pop();
        for(int i=0; i<words.size(); i++){
            if(i==x) continue;
            if(visited[i]) continue;
            cnt = 0;
            for(int j=0; j<begin.size(); j++){
                if(words[x][j]!=words[i][j]) cnt++;
                if(cnt>1) break;
            }
            if(cnt==1) {
                visited[i] = visited[x]+1;
                if(i==goal) flag = true;
                q.push(i);
            }
        }
        if(flag) break;
    }
    answer = visited[goal];
    return answer;
}