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

-inn·2022년 5월 17일
0

프로그래머스

목록 보기
2/4

단어 변환 바로가기

문제 분석

문제 풀이 과정

  1. 알고리즘 선택

    ✅ 가장 중요한 키워드 가장 짧은 변환 과정 → BFS 쓰자 !

  1. 제한사항 확인
  • 한 번에 한 개의 알파벳만 바꿀 수 있다.

    한 개의 알파벳만 다른 경우를 Bool로 리턴하는 함수 만들자.
    bool canSwitch(string s1, string s2) { }

  • 변환할 수 없는 경우에는 0을 리턴한다.

    맨 처음에 words에 target이 포함되어 있는지 확인하자.
    [처음에 answer를 크게 선언하는 방법도 존재]

  1. 코드 짜자

    // bfs(begin, target, words)
    void bfs(string begin, string target, vector<string> words) {
        queue<info> q;
    		// q({비교할 문자열, 변환 개수})
    		q.push({begin, 0});
        
        while(!q.empty()) {
            string cur = q.front().word;
            answer = q.front().cnt;
            q.pop();
            
            for (int i = 0; i < words.size(); i++) {
                if (canSwitch(cur, words[i])) { // 한 알파벳만 다를 경우, 수행
                    if (words[i] == target) { // target과 같을 경우, answer+1 하고 return
                        answer++;
                        break;
                    }
                    if (!check[i]) { // 아직 방문하지 않은 경우, q에 넣어줌
                        q.push({words[i], answer + 1});
                        check[i] = true;
                    }
                }
            }
        }
    }

전체 코드

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

bool check[51];
int answer;

struct info {
    string word;
    int cnt;
};

bool canSwitch(string s1, string s2) {
    int cnt = 0;
    for (int i = 0; i < s1.size(); i++) {
        if (s1[i] != s2[i]) {
            cnt++;
        }
    }
    if (cnt == 1) {
        return true;
    } else {
        return false;
    }
}

void bfs(string begin, string target, vector<string> words) {
    queue<info> q;
    q.push({begin, 0});
    
    while(!q.empty()) {
        string cur = q.front().word;
        answer = q.front().cnt;
        q.pop();
        
        for (int i = 0; i < words.size(); i++) {
            if (canSwitch(cur, words[i])) {
                if (words[i] == target) {
                    answer++;
                    break;
                }
                if (!check[i]) {
                    q.push({words[i], answer + 1});
                    check[i] = true;
                }
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    bool isPossible = false;
    
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == target) {
            isPossible = true;
        }
    } 
    if (!isPossible) {
        return 0;
    }
    
    bfs(begin, target, words);
    
    return answer;
}
profile
☁️

0개의 댓글