[고득점Kit][DFS][BFS] 단어 변환 ⭐⭐⭐

Date: 2020.10.23 Updated: 2020.10.23

카테고리: Programmers

[DFS][BFS] 단어 변환

난이도 ⭐⭐⭐

문제

BFS, DFS 두 풀이로 풀어본 문제다. 맞아서 기분 좋다. 🥰

BFS 로 푼 풀이 ⭕

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

using namespace std;

int differentCount(string str, string target) 
{
	int differentCount = 0;
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] != target[i])
			differentCount++;
	}
	return differentCount;
}

struct compare 
{
	bool operator() (pair<string, int> a, pair<string, int> b)
	{
		return a.second > b.second;  
	}
};

int solution(string begin, string target, vector<string> words) {
	int answer = 0;

	priority_queue<pair<string, int>, vector<pair<string, int>>, compare> waiting_queue;
	vector<bool> pushedStr(words.size());

	waiting_queue.push(make_pair(begin, differentCount(begin, target)));

	while (!waiting_queue.empty()) 
	{
		begin = waiting_queue.top().first;
		waiting_queue.pop();

		if (begin == target) break;

		for (int i = 0; i < words.size(); i++)
		{
			if (!pushedStr[i] && differentCount(begin, words[i]) == 1)
			{
				waiting_queue.push(make_pair(words[i], differentCount(words[i], target)));
				pushedStr[i] = true;
			}
		}
		answer++;
	}

	if (begin != target) answer = 0;

	return answer;
}

begin은 처음엔 “hit”으로 시작하지만 기존 begin에서 한 글자 수정하면 바꿀 수 있는 단어로 계속해서 업데이트</u> 된다.
- begin의 변화 과정 “hit” 👉 “hot” (1) 👉 “dot” (2) 👉 “dog” (3) 👉 “cog” (4)
  - 변화할 때마다 answer 1 증가.
- begin이 target과 같아질 때 위 작업을 종료한다.
새로운 begin을 결정하기 위하여
- 현재 begin 기준에서 한 글자 수정하면 바꿀 수 있는 단어들을 모조리 우선순위 큐에 넣는다. 👉 BFS 방식
- 우선순위 큐는 target과 다른 글자 수가 가장 적은 수가 우선적으로 나오게 되는 Min Heap 으로 만든다. 즉, target에 가장 가까운 단어가 나오도록 함.
  - 새로운 begin을 정할 때 우선순위큐에서 pop 시키면 현재 후보들 중 가장 target에 가까운 단어가 나오도록 한다.
    - 이렇게 우선순위큐를 사용하니 최소 횟수로 변화시키는게 가능해진다.

int differentCount(string str, string target) 
{
	int differentCount = 0;
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] != target[i])
			differentCount++;
	}
	return differentCount;
}

struct compare 
{
	bool operator() (pair<string, int> a, pair<string, int> b)
	{
		return a.second > b.second;  
	}
};

int solution(string begin, string target, vector<string> words) {


	priority_queue<pair<string, int>, vector<pair<string, int>>, compare> waiting_queue;
	

	waiting_queue.push(make_pair(begin, differentCount(begin, target)));

	vector<bool> pushedStr(words.size());

int differentCount(string str, string target) 함수
- 인수로 넘긴 두 문자열의 서로 다른 문자 수를 리턴해준다.
  - “hit” 과 “hot” 을 넘기면 1 이 나올 것이다.
waiting_queue 우선순위 큐
- pair<string, int>타입을 원소로 한다.
  - string(first) 👉 단어. 우선순위 큐에 들어가 후보로 있는 단어.
  - int(second) 👉 target과 다른 글자 수. 이 수가 적을 수록 target과 가까운 수이다. first로 target을 가진 원소의 경우 second 를 0 의 값을 가질 것이다.
    - 우선순위 기준은 이 second이 가장 작은 값이 튀어나오게 한다. Min Heap. (오름차순 힙 정렬)
- 먼저 시작전, 처음 시작 단어 begin를 우선순위 큐에 넣어준다.
pushedStr 벡터로 이미 큐에 한번 들어갔던 경험이 있는 단어인지를 체크한다. 중복으로 큐에 또 넣지 않기 위하여.
```
	while (!waiting_queue.empty()) 
  {
      begin = waiting_queue.top().first;
      waiting_queue.pop();

      if (begin == target) break;

      for (int i = 0; i < words.size(); i++)
      {
          if (!pushedStr[i] && differentCount(begin, words[i]) == 1)
          {
              waiting_queue.push(make_pair(words[i], differentCount(words[i], target)));
              pushedStr[i] = true;
          }
      }
      answer++;
  }

  if (begin != target) answer = 0;

  return answer;
```
우선순위큐가 빌 때까지 진행한다.
- 우선순위 큐에 삽입되는 기준
  - 기존에 큐에 들어간적이 없어야 하며
    - 큐에서 하나 뽑아오는 반복마다 words를 처음부터 다시 살피기 때문에 방문 경력을 체크해두어야 한다.
  - begin에서 1 글자만 바꾸면 수정 가능한 단어여야 한다.
    - differentCount(begin, words[i]) == 1
- 우선순위 큐가 다 빌 때까지, 즉 더 이상 단어가 들어갈 수 없어서 작어빙 종료 되었을 때까지도 (begin != target)인 상태면 애초에 words에 없었던지 바꿀 수 없었던 단어였던지 한 단어이므로 0 을 리턴한다.
  1. 우선순위큐 [“hit”]
  2. “hit” 👉 우선순위큐 [“hot”]
  3. “hot” 👉 우선순위큐 [“dot”, “lot”] : 둘 다 cog 와 글자 수 2 차이나므로 우선순위는 같음
  4. “dot” 👉 우선순위큐 [“lot”, “dog”] : dog 가 lot 보다 cog 에 가까우니 다음엔 dog 가 나올 것이다.
  5. “dog” 👉 우선순위큐 [“lot”, “cog”, “log”] : 다음엔 당연히 cog 와 일치하는 “cog”가 나올 것이다.
  6. “cog” target과 같으니 종료.

DFS 로 푼 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

bool canChangeWord(string a, string b)
{
	int differentCount = 0;
	for (int i = 0; i < a.length(); i++)
	{
		if (a[i] != b[i])
			differentCount++;
	}
	if (differentCount == 1) return true;
	else return false;
}

void DFS(vector<string> words, vector<bool> visited, int& answer, string target, string begin, int depth)
{
	if (begin == target)
    {
        answer = min(answer, depth);
        return;
    }

	for (int i = 0; i < words.size(); i++)
	{
		if (!visited[i] && canChangeWord(begin, words[i]))
		{
			visited[i] = true;
			DFS(words, visited, answer, target, words[i], depth + 1);
		}
	}
}

int solution(string begin, string target, vector<string> words) {
	int answer = 100;

	vector<bool> visited(words.size());

	DFS(words, visited, answer, target, begin, 0);

    if(answer == 100) return 0;
    else return answer;
}

DFS 방식

1 글자 차이 밖에 안나서 바꿀 수 있는 단어라면 냅다 깊게 들어간다. 대신 이런식으로 끝까지 들어갔다 나오므로 매 순회 경로마다 depth 재귀 길이를 기록하고, 해당 재귀에서 begin == target 드디어 성공적으로 바뀌었을 때마다 그때의 depth와 현재까지 기록한 answer 中 더 작은 것을 저장하고 리턴하면 된다. 이러면 target과 일치하게 된 성공적인 결과에 도달하기까지 가장 짧았던 재귀 길이가 최종적으로 answer에 저장되게 된다.

bool canChangeWord(string a, string b)
{
	int differentCount = 0;
	for (int i = 0; i < a.length(); i++)
	{
		if (a[i] != b[i])
			differentCount++;
	}
	if (differentCount == 1) return true;
	else return false;
}

1 글자 차이라서 바꿀 수 있다면 true리턴. 아니라면 false 리턴 해주는 함수. 즉 a에서 b로 변경이 가능한지를 알려주는 함수다.

void DFS(vector<string> words, vector<bool> visited, int& answer, string target, string begin, int depth)
{
	if (begin == target)
    {
        answer = min(answer, depth);
        return;
    }

	for (int i = 0; i < words.size(); i++)
	{
		if (!visited[i] && canChangeWord(begin, words[i]))
		{
			visited[i] = true;
			DFS(words, visited, answer, target, words[i], depth + 1);
		}
	}
}

매개 변수
- answer는 & 참조 타입이어야 한다.
  - DFS 이기 때문에 함수가 여러개 호출이 된다. 참조가 아니라면 함수 마다 answer는 동일한 메모리가 아닌 별개의 메모리로서 그저 값만 복사했을 뿐인 것이다. (Call by Value)
  - 종료 조건마다 기존 answer와 depth 중 더 작은 것으로 answer를 업데이트 해야 하기 때문에 모든 재귀 호출 함수들에게 answer 메모리가 동일하게 공유될 수 있어야 한다. 따라서 참조로 선언.
- visited는 참조 타입이면 안된다.
  - 각 단어들의 방문 상태는 각 재귀 호출 함수(방문 경로)마다 다르기 때문이다.
  - 아무 생각없이 참조로 했다가 애먹었다.. & 하나 차이로 결과가 이리 달라지다니 ㅠ

int answer = 100;

성공적으로 target로 변경 완료한 재귀 호출 함수들에서 answer와 depth를 비교하고 그 중 작은 값을 넣을 것이기 때문에 answer의 시작값은 0 이면 안된다. 절대 업데이트 안될 것이다. 따라서 words의 최대 길이인, 이 경우의 재귀 최대 깊이인 100 으로 초기화 해주고 넘겨주었다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️

[고득점Kit][DFS][BFS] 단어 변환 ⭐⭐⭐

[DFS][BFS] 단어 변환

문제

BFS 로 푼 풀이 ⭕

DFS 로 푼 풀이 ⭕

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)