๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Programmers

[C++/PGS] Lv.3 : ๋‹จ์–ด ๋ณ€ํ™˜ (DFS/BFS/๋ฐฑํŠธ๋ž˜ํ‚น) - ์ˆ˜์ •ํ•„์š”

728x90

๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(DFS/BFS) : ๋‹จ์–ด ๋ณ€ํ™˜

๋ฌธ์ œ ์ถœ์ฒ˜ - ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๊ณ ๋“์  Kit

 

๋ฌธ์ œ ์„ค๋ช…

๋‘ ๊ฐœ์˜ ๋‹จ์–ด begin, target๊ณผ ๋‹จ์–ด์˜ ์ง‘ํ•ฉ words๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์•„๋ž˜์™€ ๊ฐ™์€ ๊ทœ์น™์„ ์ด์šฉํ•˜์—ฌ begin์—์„œ target์œผ๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๊ฐ€์žฅ ์งง์€ ๋ณ€ํ™˜ ๊ณผ์ •์„ ์ฐพ์œผ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

1. ํ•œ ๋ฒˆ์— ํ•œ ๊ฐœ์˜ ์•ŒํŒŒ๋ฒณ๋งŒ ๋ฐ”๊ฟ€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
2. words์— ์žˆ๋Š” ๋‹จ์–ด๋กœ๋งŒ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด begin์ด "hit", target๊ฐ€ "cog", words๊ฐ€ ["hot","dot","dog","lot","log","cog"]๋ผ๋ฉด "hit" -> "hot" -> "dot" -> "dog" -> "cog"์™€ ๊ฐ™์ด 4๋‹จ๊ณ„๋ฅผ ๊ฑฐ์ณ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋‘ ๊ฐœ์˜ ๋‹จ์–ด begin, target๊ณผ ๋‹จ์–ด์˜ ์ง‘ํ•ฉ words๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ตœ์†Œ ๋ช‡ ๋‹จ๊ณ„์˜ ๊ณผ์ •์„ ๊ฑฐ์ณ begin์„ target์œผ๋กœ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

 

์ œํ•œ์‚ฌํ•ญ
  • ๊ฐ ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๊ฐ ๋‹จ์–ด์˜ ๊ธธ์ด๋Š” 3 ์ด์ƒ 10 ์ดํ•˜์ด๋ฉฐ ๋ชจ๋“  ๋‹จ์–ด์˜ ๊ธธ์ด๋Š” ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • words์—๋Š” 3๊ฐœ ์ด์ƒ 50๊ฐœ ์ดํ•˜์˜ ๋‹จ์–ด๊ฐ€ ์žˆ์œผ๋ฉฐ ์ค‘๋ณต๋˜๋Š” ๋‹จ์–ด๋Š” ์—†์Šต๋‹ˆ๋‹ค.
  • begin๊ณผ target์€ ๊ฐ™์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • ๋ณ€ํ™˜ํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” 0๋ฅผ return ํ•ฉ๋‹ˆ๋‹ค.

 

์ตœ์†Œ ๋ณ€ํ™˜ ๊ณผ์ •์„ ์ฐพ๋Š”๊ฑฐ๋ผ์„œ BFS๋กœ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค.

๊ทผ๋ฐ ์ด๊ฒŒ.. ์–ด์ฐŒ์–ด์ฐŒํ•˜๋‹ค๊ฐ€ ๊ธˆ๋ฐฉ ํ•ด๊ฒฐํ•˜๊ธด ํ–ˆ๋Š”๋ฐ ์™œ ๋งž์•˜๋Š”์ง€ ์ž˜ ๋ชจ๋ฅด๊ฒ ์Œ

๊ทธ๋ž˜์„œ ์ฝ”๋“œ ํ•˜๋‚˜ํ•˜๋‚˜ ๋œฏ์–ด๋ณผ ์˜ˆ์ •์ž…๋‹ˆ๋‹ค

์ผ๋‹จ ์ฝ”๋“œ ์ „์ฒด๋ถ€ํ„ฐ โฌ‡๏ธโฌ‡๏ธโฌ‡๏ธ (๋ฏฟ์ง€๋งˆ์„ธ์š”. ํ˜„์žฌ ํ…Œ์ผ€ ๊ธฐ์ค€์œผ๋กœ ํ†ต๊ณผ๋Š” ๋˜์ง€๋งŒ ์ •๋‹ต ์ฝ”๋“œ๊ฐ€ ์•„๋‹™๋‹ˆ๋‹ค...)

 

๋‚˜์˜ ํ’€์ด

(23๋…„ 5์›” ๊ธฐ์ค€ ์—…๋ฐ์ดํŠธ)

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int answer = 0;
int visited[52] = {0,};

bool canChange(string a, int idx, vector<string> words){
    if(visited[idx]==1) return false;
    string tmp = words[idx];
    int re = 0;
    for(int i=0; i<tmp.length(); ++i){
        if(a[i]!=tmp[i]) re++;
    }
    if(re!=1) {return false;}
    return true;
}

bool bfs(string begin, string target, vector<string> words){
    queue<string> q;
    q.push(begin);
    while(!q.empty()){
        string a = q.front();
        q.pop();
        for(int i=0; i<words.size(); ++i){
            if(canChange(a, i, words)){
                q.push(words[i]);
                visited[i]=1;
                answer++;
                cout << words[i]<<" / ";
                if(words[i]==target) return true;
                break;
            }
        }
    }
    return false;
}

int solution(string begin, string target, vector<string> words) {
    if(find(words.begin(), words.end(), target)==words.end()){
        return 0;
    }
    sort(words.begin(), words.end());
    bool can = bfs(begin, target, words);
    if(!can) answer = 0;
    return answer;
}

๋ถ„์„ ์Šคํƒ€ํŠธ

int solution(string begin, string target, vector<string> words) {
    if(find(words.begin(), words.end(), target)==words.end()){
        return 0;
    }
    sort(words.begin(), words.end());
    bfs(begin, target, words);
    return answer;
}

 

์ผ๋‹จ main ๋ถ€๋ถ„์ž…๋‹ˆ๋‹ค.

์ฒ˜์Œ์— target์ด words๋ฒกํ„ฐ์— ์•„์˜ˆ ์—†์œผ๋ฉด ๊ฑธ๋Ÿฌ๋ฒ„๋ฆฌ๊ณ 

์žˆ๋‹ค๋ฉด bfs ํ•จ์ˆ˜๋กœ ์ง„์ž…ํ•ฉ๋‹ˆ๋‹ค.

 

๊ทผ๋ฐ ์—ฌ๊ธฐ์„œ words๋ฅผ ์ •๋ ฌํ•ด์ฃผ๋ฉด ํ’€๋ฆฌ๊ณ  ์ •๋ ฌ ์•ˆํ•˜๋ฉด ํ…Œ์ผ€์—์„œ ํ‹€๋ฆผ. why..?

( -> ์ •๋ ฌํ•ด์ค˜์•ผ ์ˆœ์ฐจ์ ์œผ๋กœ ๋ณ€๊ฒฝ๋˜๋ฉด์„œ ๋‹ต์— ๊ทผ์ ‘ํ•˜๋Š” ๊ฒƒ ๊ฐ™์Œ)

 

void bfs(string begin, string target, vector<string> words){
    queue<string> q;
    q.push(begin);
    while(!q.empty()){
        string a = q.front();
        q.pop();
        for(int i=0; i<words.size(); ++i){
            if(canChange(a, i, words)){
                q.push(words[i]);
                visited[i]=1;
                answer++;
                if(words[i]==target) return;
                break; //?
            }
        }
    }
}

 

๋Œ€๋ง์˜ bfs์ž…๋‹ˆ๋‹ค. ์ผ๋‹จ queue ๋งŒ๋“ค๊ณ  ๋ชจ๋“  ์›์†Œ๋ฅผ ์ˆœํšŒํ•˜๋Š” ๋™์•ˆ, ๋ฒกํ„ฐ ๋ฐ˜๋ณต๋ฌธ ๋Œ๋ฆฌ๋Š”๊ฑฐ๊นŒ์ง„ ๊ทธ๋ƒฅ ํ‰๋ฒ”ํ•œ bfs๋„ค์š”

๊ทธ๋ฆฌ๊ณ  canChange ํ•จ์ˆ˜๋กœ

๋ฐฉ๋ฌธํ–ˆ๋˜ ์ŠคํŠธ๋ง์ธ์ง€ , words[i] ์™€ a ๊ฐ€ ๋ฌธ์ž ํ•˜๋‚˜ ์ฐจ์ด์ธ์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋ฆฌ๊ณ  ์กฐ๊ฑด๋ฌธ์„ ํ†ต๊ณผํ•œ๋‹ค๋ฉด q.push๋ฅผ ํ•ด์ฃผ๊ฒ ์ฃ 

ํ•œ ๊ณผ์ •์„ ๊ฑฐ์น˜๋ฏ€๋กœ answer++๋ฅผ ํ•ด์ค๋‹ˆ๋‹ค

 

๊ทธ๋ฆฌ๊ณ  ๊ทธ๋ƒฅ words[i]๊ฐ€ target๊ณผ ๊ฐ™๋‹ค๋ฉด ๊ทธ๋Œ€๋กœ return ํ•ด์ค๋‹ˆ๋‹ค.

๊ทธ๋ฆ๊ณ  ์—ฌ๊ธฐ์„œ ํ•œ ๊ณผ์ •์„ ๊ฑฐ์น˜๋ฉด break๋ฅผ ํ•ด์ค๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ๋ถ€ํ„ฐ ์ด๊ฒŒ ๋งž๋‚˜?์‹ถ์€๋ฐ ํ˜น์‹œ ์ด๊ฒŒ ์™œ ๋˜๋Š”์ง€ ์•„์‹œ๋Š” ๋ถ„์€ ๋Œ“๊ธ€ ๋ถ€ํƒ๋“œ๋ฆฝ๋‹ˆ๋‹ค....

break๋ฅผ ๋นผ๋ฉด ํ‹€๋ฆฌ๋”๋ผ๊ณ ์š”. ;

(์ผ๋‹จ ๋ชจ๋ฒ”๋‹ต์•ˆ์€ dfs์ธ ๊ฒƒ ๊ฐ™์Œ)

 

๋‚˜๋ฆ„ ๋ฐฑํŠธ๋ž˜ํ‚น,,,์ด๋ผ๊ณ  ์ƒ๊ฐํ•˜๋Š”๋ฐ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๊ฐ€ 5๊ฐœ๋ฐ–์— ์—†์–ด์„œ

๊ทธ๋ƒฅ ์šด์ด ์ข‹์•˜๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

๋‚˜์ค‘์— ๋‹ค์‹œ ํ’€์–ด๋ดใ…‡ใ…‘์ง€

 

<<<<< ์„ค๋ช…ํ•ด์ฃผ์‹ค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ฒœ์žฌ ๊ตฌํ•ฉ๋‹ˆ๋‹ค >>>>>

 

์ด์ƒ. ๋

 

728x90