알고리즘
[프로그래머스] 단어 변환
택시짱
2020. 3. 20. 16:05
링크
https://programmers.co.kr/learn/courses/30/lessons/43163
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 구하는 문제이다.
BFS탐색을 이용하여 최소 값을 구하도록 하였고
이전 문자와 다음 문자를 서로 비교하여 다른 부분이 한 개만 있을 때 BFS의 queue에 추가되도록 하여
target 문자열을 만나게 되면 바로 return을 하도록 하였습니다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>
#define SIZE 55
const int INF = 2000000000;
using namespace std;
typedef long long int ll;
map<char, int> _map[SIZE];
bool word_cmp(string here, string next, int index) {
int cnt = 0;
for (int i = 0; i < here.size(); i++) {
if (here.at(i) == next.at(i))
cnt++;
}
if (cnt == here.size() -1)
return true;
else
return false;
}
queue < pair<string, int> >q;
map<pair<string, string>, bool> visited;
int solution(string begin, string target, vector<string> words) {
pair<string, int> start(begin, 0);
int answer = 0;
q.push(start);
while (!q.empty()) {
pair<string, int> h = q.front(); q.pop();
for (int i = 0; i < words.size(); i++) {
pair<string, int > n(words[i], h.second + 1);
if (!word_cmp(h.first, n.first, i)) {
continue;
}
if (visited[make_pair(h.first, n.first)] == true)
continue;
if (words[i] == target)
return n.second;
q.push(n);
visited[make_pair(h.first, n.first)] = true;
}
}
return answer;
}
반응형