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

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begintargetwordsreturn

hit	cog	[hot, dot, dog, lot, log, cog]	4
hit	cog	[hot, dot, dog, lot, log]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

---

bfs 문제이다. 단어가 마구 나온 걸 보고 map을 써야 하나 싶었지만 쓸 필요는 없었다.

begin 단어에서 target 단어까지 최소한의 이동으로 글자를 바꾸면 된다.

단 바꿀 때에는 두 단어간의 글자가 한 개만 차이가 나야 한다.

 

큐에 begin 단어와 이동 횟수 0을 넣은 후, 조사를 시작한다.

입력으로 들어온 모든 단어와 대조하며 글자가 한 개만 차이나고 방문한 적 없는 단어는 큐에 넣고, 방문 여부를 체크한 후 이동 횟수를 1 증가한다.

이런 식으로 모든 조합을 검사하다가 target과 같은 단어를 방문하면 answer에 방문 횟수를 기록하고 break하면 된다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EB%8B%A8%EC%96%B4%20%EB%B3%80%ED%99%98.cpp

chosh95/STUDY

C++ 코드

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

using namespace std;
int visit[51];
int solution(string begin, string target, vector<string> words) {
	int answer = 0;
	queue<pair<string, int>> q;
	q.push({ begin, 0 });
	int len = begin.length(); //글자 길이

	while (!q.empty()) {
		string cur = q.front().first; //현재 검사할 단어
		int num = q.front().second; //현재까지 방문 횟수
		q.pop();
		if (cur == target) {
			answer = num;
			break;
		}
		for (int i = 0; i < words.size(); i++) {
			int cnt = 0;
			string next = words[i]; //다음 단어

			if (visit[i]==1) continue; 
			for (int j = 0; j < len; j++) {
				if (cur[j] == next[j]) cnt++;
			}
			if (cnt != len - 1) continue;

			q.push({ next, num + 1 }); //방문 가능시 다음 단어를 q에 추가
			visit[i] = 1;
		}
	}

	return answer;
}

int main()
{
	cout << solution("hit", "cog", {"hot", "dot", "dog", "lot", "log", "cog" });
}