Programmers - 깊이/너비 우선 탐색(DFS/BFS)
나의 풀이
BFS : 현 위치와 계산값을 큐에 저장하여 마지막 위치에 목표값과 같으면 답의 수를 증가시켰다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> numbers, int target) {
int answer = 0;
deque<pair<int, int>> que; // value, position
que.push_back(make_pair(0, 0));
while (!que.empty())
{
pair<int, int> e = que.front();
que.pop_front();
if (e.second == numbers.size()) {
if (e.first == target)
answer++;
continue;
}
que.push_back(make_pair(e.first + numbers[e.second], e.second + 1));
que.push_back(make_pair(e.first - numbers[e.second], e.second + 1));
}
return answer;
}
다른사람 풀이
#include <string>
#include <vector>
using namespace std;
int total;
void DFS(vector<int> &numbers, int &target,int sum,int n) {
if(n >= numbers.size()){
if(sum == target) total++;
return;
}
DFS(numbers, target, sum + numbers[n], n+1);
DFS(numbers, target, sum - numbers[n], n+1);}
int solution(vector<int> numbers, int target) {
int answer = 0;
DFS(numbers, target, numbers[0] , 1);
DFS(numbers, target, -numbers[0], 1);
answer = total;
return answer;
}
문제를 풀다가 흥분하여 구현이 꼬여버렸다. 손코딩을 연습해야겠다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
vector<bool> visit(n, false);
deque<int> que;
for (int i = 0; i < n; i++)
{
if (!visit[i])
{
answer++;
que.push_back(i);
while(!que.empty())
{
visit[que.front()] = true;
for (int j = 0; j < n; j++)
{
if (computers[que.front()][j] && !visit[j])
{
que.push_back(j);
}
}
que.pop_front();
}
}
}
return answer;
}
쉽다고 생각하여 대충 접근하였다가 큰코 다쳤다. 천천히 진정하고 문제에 접근하여 풀어야 한다.
먼저 큐에 begin을 시작으로 변환가능한 단어를 큐에 단어의 인덱스와 1증가한 카운터 넣는다. 넣은 단어는 사용된 단어로 체크한다.
가장 먼저 target과 접한 단어의 카운터는 답이 된다.
int compare(string a, string b) {
int ret = 0;
for (int i = 0; i < a.length(); i++)
{
if (a[i] != b[i])
{
ret++;
if (ret > 1)
return ret;
}
}
return ret;
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
words.push_back(begin);
deque<pair<int, int>> que; // idx, cnt
vector<int> used(words.size());
que.push_back(make_pair(words.size() - 1, 0));
while (!que.empty())
{
pair<int, int> a = que.front();
que.pop_front();
for (int i = 0; i < used.size() - 1; i++)
{
if (!used[i])
{
if (compare(words[i], words[a.first]) == 1)
{
if (words[i] == target)
return a.second + 1;
que.push_back(make_pair(i, a.second + 1));
used[i] = 1;
}
}
}
}
return answer;
}
나의 풀이
unordered_map을 이용하여 출발지를 키로 도착지들을 큐에 저장하고 도착지를 알파벳 순으로 정렬하였다. ICN을 시작으로 탐색하며 도착지가 비어있을 때까지 탐색하였다. 도착지가 비어있는 경우는 모든 탐색을 마쳤거나 전부 탐색하지 못했지만 티켓이 없어 더 이상 다른 도시로 갈 수 없는 경우다. 후자의 경우에는 이전 도시로 돌아가 먼저 방문한 도시를 제일 나중에 방문하도록 하여 모든 도시를 순회하며 동시에 알파벳 순으로 앞설 수 있도록 하였다.
vector<string> dfs(unordered_map<string, deque<string>>& tickets, string start) {
vector<string> answer, tmp;
if (tickets[start].empty())
{
for (unordered_map<string, deque<string>>::iterator t = tickets.begin(); t != tickets.end(); t++)
{
if (t->second.size() != 0) {
return tmp;
}
}
return vector<string> {start};
}
answer.push_back(start);
int lim = tickets[start].size();
for (int i = 0; i < lim; i++)
{
string next = tickets[start].front();
tickets[start].pop_front();
tmp = dfs(tickets, next);
if (tmp.size() != 0)
break;
tickets[start].push_back(next);
}
if (tmp.size() == 0)
{
return tmp;
}
answer.reserve(answer.size() + tmp.size());
answer.insert(answer.end(), tmp.begin(), tmp.end());
return answer;
}
vector<string> solution(vector<vector<string>> tickets) {
vector<string> answer;
unordered_map<string, deque<string>> TK;
for (vector<string> t : tickets)
{
TK[t[0]].push_back(t[1]);
}
for (unordered_map<string, deque<string>>::iterator t = TK.begin(); t != TK.end(); t++)
{
sort(t->second.begin(), t->second.end());
}
answer = dfs(TK, "ICN");
return answer;
}
다름 사람 풀이
모든 티켓을 순회하며 depth가 티켓의 수와 같을 때 가장 짧은 답안을 return하여 답을 찾는 방법이다. 모든 티켓의 경우의 수를 순회하는 방법
#include <string>
#include <vector>
using namespace std;
int visited[1000000];
string ans_string = "a";
void dfs(vector<vector<string>>& tickets, string cur, string path, int depth) {
if (depth == tickets.size()) {
if (path < ans_string) {
ans_string = path;
}
return;
}
for (int i = 0; i < tickets.size(); i++) {
if (cur == tickets[i][0] && !visited[i]) {
visited[i] = 1;
dfs(tickets, tickets[i][1], path + tickets[i][1], depth + 1);
visited[i] = 0;
}
}
}
vector<string> solution(vector<vector<string>> tickets) {
vector<string> answer;
dfs(tickets, "ICN", "ICN", 0);
for (int i = 0; i < ans_string.size(); i += 3) {
answer.push_back(ans_string.substr(i, 3));
}
return answer;
}
댓글남기기