[프로그래머스][DFS/BFS][C++] 단어 변환

문제

프로그래머스 DFS/BFS - 단어 변환

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

문제 설명

두 개의 단어 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 합니다.

입출력 예

begin	target	words	return
hit	cog	[hot, dot, dog, lot, log, cog]	4
hit	cog	[hot, dot, dog, lot, log]

 

---

문제 풀이

접근 방식

최소 변환 과정을 찾기 위해 BFS로 구현하였다.

BFS 방식으로 큐에 시작할 단어와 현재 변환 횟수를 담아 while문을 수행하였다.

while문 내에서는 시작 단어와 한 글자가 차이나는 단어를 찾기 위해 for문을 수행하였다.

찾은 단어가 target이면 변환 횟수 + 1을 바로 리턴하였고,

tartget이 아니면 visit를 1로 바꿔주고 큐에 해당 단어와 변환 횟수 + 1을 넣어주었다.

 

---

풀이 코드 - C++

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

using namespace std;

int solution(string begin, string target, vector<string> words) {
	int N = words.size();
	int M = begin.size();
	vector<int> visit(N, 0);
	queue<pair<string, int>> q;
	q.push({ begin, 0 });
	int i, j, diff;
	int answer = 0;
	while (!q.empty()) {
		string start = q.front().first;
		int count = q.front().second;
		q.pop();
		for (i = 0; i < N; i++) {
			diff = 0;
			if (visit[i] != 0) continue;
			for (j = 0; j < M; j++) {
				if (start[j] != words[i][j])
					diff++;
			}
			if (diff == 1) {
				if (words[i] == target) {
					return count + 1;
				}
				visit[i] = 1;
				q.push({ words[i], count + 1 });
			}
		}
	}
	return answer;
}

실행 결과