https://programmers.co.kr/learn/courses/30/lessons/43163
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
처음에는 dfs로 풀려 했는데 제대로 풀지도 못한 것 같고 우선 간단한 테스트 만으로도 시간 초과가 나서 bfs로 풀었다.
이번에도 시간초과가 나는 것을 막기 위해 한 번 탐색한 문자열은 큐에 넣지 않고 탐색했다.
레벨3인데 혼자 고민해서 어떻게든 풀 것 만으로도 너무 감사하다...
소스코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
int ch[52];
int bfs(string begin, string target, vector<string> words) {
//현재 문자열과 과정 횟수를 담는 큐 선언
queue<pair<string,int>> q;
q.push(make_pair(begin,0));
int diff;
while(!q.empty()) {
pair<string,int> p = q.front();
//현재 문자열과 타겟이 같다면 횟수 반환
if(p.first == target) return p.second;
q.pop();
//words 문자열들과 비교해 한글자만 다르다면 큐에 삽입
for(int i = 0; i < words.size(); i++) {
diff = 0;
for(int k = 0 ; k < target.length(); k++) {
if(p.first[k] != words[i][k]) diff++;
}
if(diff == 1 && ch[i] == 0) {
ch[i] = 1;
q.push(make_pair(words[i], p.second+1));
}
}
}
return 0;
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
answer = bfs(begin, target, words);
return answer;
}
'CodingTest Practice > Programmers' 카테고리의 다른 글
프로그래머스 : 프린터 (C++, Lv.2, 큐) (0) | 2022.05.31 |
---|---|
프로그래머스 : 여행경로 (C++, Lv.3, DFS) (1) | 2022.05.27 |
프로그래머스 : 카펫 (C++, Lv.2, 완전탐색) (0) | 2022.05.25 |
프로그래머스 : 체육복 (C++, Lv.1, 탐욕법) (0) | 2022.05.22 |
프로그래머스 : 가장 큰 수 (C++, Lv.2,정렬) (0) | 2022.05.21 |