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

문제 링크

• 프로그래머스

요약

• 그래프가 주어져있지 않은 상황에서도 그래프 문제인지를 생각해볼 수 있어야 한다.

최종 §

결과

• BFS로 분류되어있긴 한데, 보니까 BFS 사용하는 그래프 문제여서 그래프에 넣어놓았음.
• 각 word에 대해, 한문자 차이면 connected 된걸로 해서 몇번의 step 만에 다음 node에 도달할 수 있는지 BFS로 찾으면 된다.

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
#define PACK(step, idx) (((step) << 16) | ((idx) & 0xFFFF))
#define UNPACK_STEP(pack) (((pack) >> 16) & 0xFFFF)
#define UNPACK_IDX(pack) ((pack) & 0xFFFF)
 
#define bms unsigned long long
 
int solution(string begin, string target, vector<string> words) {
	int target_idx = -1;
	vector<vector<int>> conn(words.size());
	queue<int> q;
	bms visited = 0;
 
	for (int i = 0; i < words.size(); i++) {
		if (target == words[i]) {
			target_idx = i;
		}
 
		for (int j = i + 1; j < words.size(); j++) {
			int distance = 0;
 
			for (int n = 0; n < begin.size(); n++) {
				distance += (words[i][n] != words[j][n]);
			}
 
			if (distance == 1) {
				conn[i].push_back(j);
				conn[j].push_back(i);
			}
		}
	}
 
	if (target_idx == -1) {
		return 0;
	}
 
	for (int i = 0; i < words.size(); i++) {
		int distance = 0;
 
		for (int n = 0; n < begin.size(); n++) {
			distance += (words[i][n] != begin[n]);
		}
 
		if (distance == 1) {
			
			q.push(PACK(1, i));
			visited |= (1 << i);
		}
	}
 
	while (!q.empty()) {
		int pack = q.front();
		int step = UNPACK_STEP(pack);
		int idx = UNPACK_IDX(pack);
		q.pop();
 
		if (idx == target_idx) {
			return step;
		}
 
		for (auto next : conn[idx]) {
			if (!((visited >> next) & 0x1)) {
				q.push(PACK(step + 1, next));
				visited |= (1 << next);
			}
		}
	}
 
	return 0;
}