๊น์ด/๋๋น ์ฐ์ ํ์(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๊ฐ๋ฐ์ ์์ด์
๊ทธ๋ฅ ์ด์ด ์ข์๋ ๊ฒ ๊ฐ๋ค.
๋์ค์ ๋ค์ ํ์ด๋ดใ ใ ์ง
<<<<< ์ค๋ช ํด์ฃผ์ค ์๊ณ ๋ฆฌ์ฆ ์ฒ์ฌ ๊ตฌํฉ๋๋ค >>>>>
์ด์. ๋
'๐ ์๊ณ ๋ฆฌ์ฆ > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/PGS] Lv.2 : ํฐ ์ ๋ง๋ค๊ธฐ (GREEDY) (0) | 2023.03.02 |
---|---|
[C++/PGS] Lv.2 : ํ๋ฆฐํฐ (Queue) (0) | 2023.03.02 |
[C++/PGS] Lv.1 : ์ฒด์ก๋ณต (GREEDY) (0) | 2023.02.23 |
[C++/PGS] Lv.3 : ๋ฑ๊ตฃ๊ธธ (DP) (1) | 2023.02.23 |
[C++/PGS] Lv.3 : ๋คํธ์ํฌ (DFS/BFS) (0) | 2023.02.23 |