프로그래머스(C++) - 단어 변환

●문제

●입출력

 

문제해석 : 현재 begin의 단어가 words 안에서 target단어로 가는데  한번에 한 단어씩만 바꿔서 

target으로 바뀌는 최소한의 변환절차를 카운팅 해서 return

bfs로 풀어도되고 dfs로 풀어도되는데 필자는 dfs로 풀었습니다

#include <vector>
#include <iostream>
#include <stdio.h>

using namespace std;
int answer = 0;
vector<bool> checked(51, 0); //방문여부
void DFS(int count, const string& current, const string& target, const vector<string>& words)
{
	//다른 글자수 찾기
	for (int i = 0; i < words.size(); ++i)
	{
		int diffCount = 0;

		for (int j = 0; j < words[i].size(); ++j)
		{
			//현재 글자가 words의 글자중에 다른게있다면 변수값 증가
			if (current[j] != words[i][j])
			{
				diffCount++;
			}
		}

		//다른 글자수가 한개고 방문하지않았을때
		if (diffCount == 1 && !checked[i])
		{
			//목표 단어를 찾은경우
			if (words[i] == target)
			{
				answer = count + 1;
				return;
			}
			else
			{
				checked[i] = true;
				DFS(count + 1, words[i], target, words);
			}
		}
		
	}
	
}
int solution(string begin, string target, vector<string> words)
{
	DFS(0, begin, target, words);
	return answer;
}

 

레벨 : 3

점수 : 1