문제풀이)프로그래머스)단어 변환

단어 변환

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

프로그래머스

	using System.Collections.Generic;
	using System.Linq;
	using System;
	public class Solution {
	public class Node
	{
	public string[] words;
	public string current = string.Empty;
	public string target = string.Empty;
	public List<string> history = new List<string>();
	}
	Queue<Node> queue = new Queue<Node> ();
	public int solution(string begin, string target, string[] words) {
	int answer = 0;
	Node root = new Node();
	root.current = begin;
	root.target = target;
	root.words=words;
	Node result = Recursion(root);
	if(result == null)
	answer = 0;
	else
	answer = result.history.Count;
	return answer;
	}
	private Node Recursion(Node _rootNode)
	{
	queue.Enqueue(_rootNode);
	while(queue.Count != 0)
	{
	Node node = queue.Dequeue();
	if (node.current.Equals(_rootNode.target))
	return node;
	foreach (string word in node.words)
	{
	if (IsMatch(node.current, word))
	{
	Node newNode = new Node();
	newNode.words = node.words.Where(w => w.Contains(word) == false).ToArray();
	newNode.target = node.target;
	//기존 history + 현재
	newNode.history.AddRange(node.history);
	newNode.history.Add(node.current);
	newNode.current = word;
	queue.Enqueue(newNode);
	}
	}
	}
	return null;
	}
	public bool IsMatch(string _word1 , string _word2)
	{
	int length = _word1.Length;
	int otherWordCount = length;
	for (int i = 0; i < length; i++)
	{
	//같은 index 의 char 비교
	var word1 = _word1.Substring(i, 1);
	var word2 = _word2.Substring(i, 1);
	if (word1.Equals(word2))
	otherWordCount--;
	}
	return (otherWordCount == 1); //1개만 차이가 있는지 여부
	}
	}

view raw 단어변환.cs hosted with ❤ by GitHub

<문제풀이>

begin (시작 단어)에서 target (찾는 단어)까지의 하나의 char를 변경해가면서 가장 최단으로 찾는 문제이다.

처음의 문제를 잘 파악하는게 중요한것 같다. 처음에는 단순히 순서대로 비교해서 테스크 케이스는 통과했는데 알고보니

경우의수를 다 계산해서 가장 최단을 찾아야하는 문제였다.

 

BFS를 기반으로 문제 해결하니 금방 해결했다.

IsMatch 를 통해서 단어의 차이가 1개만 있는 경우를 판단했고

Node의 history 를 쌓아가면서 그전의 변환 과정을 저장했다.

 

 ★☆☆☆☆