프로그래머스 43163 - 단어 변환 (c++)

프로그래머스 43163 - 단어 변환

문제 링크

생각 및 접근

• BFS는 최단거리를 보장한다. 이 문제는 begin에서 target으로 변환 가능한 최소 경로를 구하는 것이므로, BFS로 접근하려고 했다.
• BFS는 코드로 구현할 때 다음과 같은 요소를 고려하여야 한다.
  • queue의 데이터 타입
  • queue의 초깃값
  • q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동
  • 읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

queue의 데이터 타입

• BFS를 하면서 탐색한 횟수 int, 현재 변환된 상태 string을 pair로 선언하였다.

    queue< pair<string, int> > q;

  queue의 초깃값

  q.push(make_pair(begin, 0));

q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동

• string temp = q.front().first가 target과 같다면, 최소 경로를 찾은 것이므로 return q.front().second;

읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

• words를 모두 순회하여 아래 조건에 해당하는 원소를 push하고, visit를 체크.
  • 아직 방문하지 않았고, visit\[i\]
  • temp와 words[i]를 비교해서 변환이 가능하다면 chk1diff(temp, words[i])

      bool chk1diff(string a, string b){
          int cnt = 0;
          for(int i = 0; i < a.length(); i++){
              if(a[i] != b[i]) cnt++;
          }
          if(cnt == 1)    return true;
          return false;
      }

코드

#include <bits/stdc++.h>
using namespace std;

bool chk1diff(string a, string b){
    int cnt = 0;
    for(int i = 0; i < a.length(); i++){
        if(a[i] != b[i]) cnt++;
    }
    if(cnt == 1)    return true;
    return false;
}

int answer = 0, visit[50];
queue< pair<string, int> > q;

int solution(string begin, string target, vector<string> words) {
    q.push(make_pair(begin, 0));
    while(!q.empty()){
        string temp = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if(temp == target){
            return cnt;
        }

        for(int i = 0; i < words.size(); i++){
            if(visit[i] != 0) continue;
            else{
                if(chk1diff(temp, words[i])){
                    visit[i] = 1;
                    q.push(make_pair(words[i], cnt + 1));
                }
            }
        }
    }
    return 0;
}

채점 결과