[프로그래머스/C++] 단어 변환

(6/27 - O)

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

코딩테스트 연습 - 단어 변환

 

 

구현

dfs 방식으로 풀었다.

 

1. begin의 각 자릿수의 알파벳을 a~z로 변환한다. (예를 들면, hit을 (a~z)it, h(a~z)t, hi(a~z)으로)

2. 변환할 때마다 words 내에 있는 단어와 일치한지 검사한다.

3. 일치하지 않으면 다시 2를 반복, 일치하면 count를 증가시킨 뒤 그 단어를 begin으로 두어 dfs를 호출하여 1,2를 반복한다.

4. begin이 target과 같으면 min_cnt = min(min_cnt, cnt)로 갱신한다. 그리고 함수를 반환한다.

 

 

코드

int visited[51];
int begin_len;
int words_size;
int min_cnt;

void dfs(string begin, string target, vector<string>& words, int& cnt) {
    if (begin == target) {
        min_cnt = min(min_cnt, cnt);
        for (int i = 0; i < words_size; i++) {
            if (words[i] == begin) {
                visited[i] = false;
            }
        }
        cnt--;
        return;
    }
    for (int i = 0; i < begin_len; i++) { // 앞 글자부터 하나씩 바꿔보기
        int convert_cnt = 0;
        char ori = begin[i];
        while (true) {
            begin[i] = 'a' + (convert_cnt++);
            if (begin[i] == ori) {
                continue;
            }
            if (begin[i] > 'z') {
                begin[i] = ori;
                break;
            }
            for (int j = 0; j < words_size; j++) {
                if (words[j] == begin && visited[j] == false) {
                    begin = words[j];
                    visited[j] = true;
                    cnt++;
                    dfs(begin, target, words, cnt);
                }
            }
        }
    }
    for (int i = 0; i < words_size; i++) { // 들어갔다 나왓으면 다시 visted false 처리
        if (words[i] == begin) {
            visited[i] = false;
            cnt--;
        }
    }
}


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

	// words 안에 target이 있는지 확인
	bool isin = false;
	for (auto& i : words) {
		if (i == target) isin = true;
	}
	// 있으면
	if (isin) {
		// begin=hit
		// target=cog
		begin_len = begin.length();
		words_size = words.size();
		string b = begin;
		min_cnt = 1e9;
		int cnt = 0;
		dfs(b, target, words, cnt);
		answer = min_cnt;
	}
	// 없으면
	else {
		answer = 0;
	}
	return answer;
}

 

(같이 푼 친구는 bfs를 이용했는데 테스트케이스3에서 내 코드보다 5배 빠른 속도였다. 나처럼 일일이 변환하지 않아서 코드가 더 간결했다)