[프로그래머스]43163- 단어 변환 (C/C++)

.프로그래머스 43163번 단어변환 문제. 코테 고득점 KIT DFS/BFS에 위치해 있다.

원트원클 해버렸는데 인증할 방법이 없네..

다시금 코테를 준비하면서 풀어본 프로그래머스의 3단계급 문제 되시겠다.

뭐 엄청 오랜만에 풀어본 것 같지만, 한번에 통과하다니...역시 머슬 메모리가 남아있는 것일까?

하지만 문제를 풀어보면서 생각해보니 낭비되는 메모리도 좀 있던 것 같아 이부분이 아쉽다고 생각했다.

 

나의 경우, BFS를 통해서 문제를 해결하였다.

다른 사람들을 보니, DFS를 통해 해결하는 사람도 많았고, 백트래킹으로 푸는 사람도 있었지만, 아무래도 BFS가 낫지 않을까? 라고 생각해 풀게 되었다.

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

using namespace std;

int *visited;
int cnt;
string begins;
string targets;
queue<int> Queue;

bool littleSame(string a, string b)
{
	int num{0};
	for (int i = 0; i < a.size(); ++i)
	{
		if (num == 2) return false;
		if (a[i] != b[i]) num++;

	}
	if(num == 1)
		return true;
	return false;
}

void bfs(vector<string> t)
{
	
	for (int i = 0; i < t.size(); ++i)
	{

		if (littleSame(begins, t[i]) && !visited[i])
		{
			visited[i] = 1;
			Queue.push(i);
			break;
		}

	}

	while (!Queue.empty())
	{
		int u = Queue.front();
		Queue.pop();
		if (targets.compare(t[u]) == 0) {
			cnt = visited[u];
			return;
		}

		for (int i = 0; i < t.size(); ++i)
		{
			
			if (littleSame(t[u], t[i]) && !visited[i])
			{
				visited[i] = visited[u]+1;
				Queue.push(i);
			}

		}
	}
	cnt = 0;
}

int solution(string begin, string target, vector<string> words) {
    begins = begin;
    targets = target;
    visited = new int[words.size()]{0};
    bfs(words);
    
    return cnt;
}

코드는 이러한데, 우선 단어에서 한 문자만 다르고, 나머지는 같은 LittleSame이라는 함수를 만들어줬다.

이걸 통해서 조건을 걸어주어 문자가 비슷한 단어들을 Queue에 넣어주고, 각각 다음 LittleSame한 단어를 찾아 Queue에 Push할 수 있게 하였다.

그다음 여기서 BFS에서 사용할 VIsited라는 배열을 만들었는데, 이는 bool이 아닌 int로 만들어, 해당 문자가 몇 번째로 불렸는지를 넣어, 최종적으로 타겟 단어가 됐을 경우, 해당 값을 호출하는 형식으로 문제를 해결하였다.

 

 

여담으로 3단계라서 많이 어렵지 않을까.. 라고 생각했는데, 막상 문제를 풀어보니 간단하다고 느끼게 된 문제였다.

아님 내가 1년동안 공부안하고 놀기만했는데 실력이 늘어버린건가? 라고 생각해야할수도...는 아니겠죠 ㅎㅎㅋㅋㅈㅅ;

 

백준만이 아니라 프로그래머스에서도 문제를 풀곤 있는데, 프로그래머스가 더욱 까다로운 느낌이다.

아무래도 백준은 처음부터 끝까지 복붙해서 전부 올리면 되지만, 프로그래머스는 해당하는 함수만을 올리게 되어있기 때문에 이를 바꿔주는 과정이 힘들다고 생각햇다.

또한, 코테를 봐보면서 IDE사용이 제한되는 회사가 많은데, 이 경우 내가 문제를 푸는데에 있어서 엄청 제약이 많이 걸린다고 생각했다..진짜 자동완성도 제공 안해주고 디버깅도 제공 안해주고 계속 Segmentation fault뜨고 넘 힘들엇슴..

그래서 앞으로는 최대한 IDE도움을 받지 않고 해당 사이트에서만 문제를 해결해보는건 어떨까 라고 생각했는데, 이건 뇌버깅으로만 해야하니까 시간이랑 오답률이 엄청 늘어나려나? 그래도 해야지 어쩌겠냐

 

다음 문제는 같은 프로그래머스에서 DFS를 활용해 문제를 해결한 43165 타겟넘버 문제나, 골아프게 풀고있는 백준의 숨바꼭질 문제를 가져오지 않을까 싶다