[C++] DFS/BFS 모음

43165 타겟 넘버 [문제 바로가기]

 

solution

1. 배열을 돌면서 배열의 원소를 더하거나 빼거나 두 가지 경우에 대해서 재귀를 실행한다.

2. 모든 배열을 탐색했을 때 만든 숫자가 target과 같다면 결과 +1 을 한다.

 

 

#include <string>
#include <vector>

using namespace std;
int result;

void dfs(int n, int target, vector<int> numbers, int idx) {
    if (idx == numbers.size() && n == target) {
        result++;
        return;
    }
    
    if (idx >= numbers.size())
        return;
    
    dfs(n + numbers[idx], target, numbers, idx + 1);
    dfs(n - numbers[idx], target, numbers, idx + 1);  
}

int solution(vector<int> numbers, int target) {
    dfs(0, target, numbers, 0);
    return result;
}

---

43162 네트워크 [문제 바로가기]

 

solution

1. computers 배열을 돌면서 방문하지 않은 노드에 대해서

2. 네트워크를 +1 하고 연결된 컴퓨터들을 탐색한다.

3. 이때 dfs 를 사용하여 노드와 연결된 컴퓨터들을 모두 탐색한다.

 

#include <string>
#include <vector>
#include <stack>
using namespace std;

int result;
void dfs(int start, int n, vector<int> &visited, vector<vector<int>> computers) {
    stack<int> st;
    st.push(start);
    
    while(!st.empty()) {
        int node = st.top();
        visited[node] = 1;
        st.pop();
        
        for(int i = 0;i < n;i++) {
            if (i == node)
                continue;
            
            if (computers[node][i] == 1 && visited[i] == 0)
                st.push(i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    vector<int> visited(n, 0);
    
    for(int i = 0;i < n;i++) {
        if (visited[i] == 1)
            continue;
        
        visited[i] = 1;
        result++;
        
        for(int j = 0;j < n;j++) {
            if (i == j)
                continue;
            
            if (computers[i][j] == 1 && visited[j] == 0)
                dfs(j, n, visited, computers);
        }
    }
    
    return result;
}

---

1844 게임 맵 최단거리 [문제 바로가기]

 

solution

BFS를 사용하여 (0, 0) 에서 (n, m) 까지 블럭 수를 +1 해서 탐색한다.

 

#include <vector>
#include <queue>
using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int solution(vector<vector<int>> maps)
{
    vector<vector<int>> bfs(100, vector<int>(100, -1));  
    int n = maps.size();
    int m = maps[0].size();
    
    bfs[0][0] = 1;
    queue<pair<int, int>> q;
    q.push({0, 0});
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int dir = 0;dir < 4;dir++) {
            int tempX = x + dx[dir];
            int tempY = y + dy[dir];
            
            if (tempX < 0 || tempY < 0 || tempX >= n || tempY >= m)
                continue;
            
            if (maps[tempX][tempY] == 0 || bfs[tempX][tempY] != -1)
                continue;
            
            bfs[tempX][tempY] = bfs[x][y] + 1;
            q.push({tempX, tempY});
        }
    }
    
    return bfs[n - 1][m - 1];
}

---

43163 단어 변환 [문제 바로가기]

 

solution

=> BFS로 진행

1. begin 단어를 queue에 넣고 BFS를 진행한다.

2. 시작 word에 대해서 가능한 word라면 queue에 넣고 visited 처리를 한다.

2-1. 이때 한 단어만 차이 난다면 가능한 word로 판단한다. 이를 위해서 isValid() 함수를 따로 만들었다.

3. target 단어를 만나거나 모든 words 배열을 볼때까지 이를 진행한다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

bool isValid(string str1, string str2) {
    int count = 0;
    
    for(int i = 0;i < str1.size();i++) {
        if (str1[i] != str2[i])
            count++;
    }
    
    if (count > 1)
        return false;
    
    return true;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 1e9;
    
    vector<bool> visited(50, false);
    queue<pair<string, int>> q;
    q.push({begin, 0});
    
    while (!q.empty()) {
        string str = q.front().first;
        int count = q.front().second;
        q.pop();
        
        if (str == target) {
            answer = min(answer, count);
            continue;
        }
        
        for(int i = 0;i < words.size();i++) {
            if (isValid(words[i], str) && !visited[i]) {
                visited[i] = true;
                q.push({words[i], count + 1});
            }
        }
    }
    
    if (answer == 1e9)
        answer = 0;
    
    return answer;
}

 

 

43164 여행 경로 [문제 바로가기]

 

solution

=> DFS

1. tickets 배열을 정렬하고 방문하지 않은 항공권에 대하여 모두 DFS 탐색을 한다

 

 

처음 풀이

문제에 알파벳 순서가 앞서는 경우를 return하라고 해서 그냥 단순하게

현재 도시에서 갈 수 있는 도시들을 배열에 담고 정렬을 하면서 가장 앞에 있는 도시를 먼저 방문하는 것으로 코드를 구현했다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> visited(tickets.size(), false);
    
    queue<string> q;
    q.push("ICN");
    
    while (!q.empty()) {
        string now = q.front();
        answer.push_back(now);
        q.pop();
        
        vector<pair<string, int>> city;
        for(int i = 0;i < tickets.size();i++) {
            if (tickets[i][0] == now && !visited[i]) {
                city.push_back({tickets[i][1], i});
            }
        }
        
        if (city.empty())
            continue;
        
        sort(city.begin(), city.end());
        visited[city[0].second] = true;
        q.push(city[0].first);
    }
    
    return answer;
}

 

그런데 이렇게 할 경우 가장 짧은 길이를 구하지 못한다. 그래서 테스트 케이스 1, 2는 계속 틀리게 된다.

예를 들어서 다음과 같은 경우를 생각해보자

ICN A

ICN B

B ICN

 

이 경우 나의 첫번째 코드를 사용하면 

[ICN A B ICN B] 가 나온다. 왜냐하면 가장 알파벳이 낮은 순서로 방문하기 때문이다.

하지만 이때의 정답은 길이가 더 짧은 [ICN B ICN A] 이다.

따라서 현재 도시에서 갈 수 있는 모든 경우의 수를 살펴보면서 결과 배열 사이즈가 티켓배열+1 이 될 때가 정답이 되도록 구현하면 된다

왜냐하면 문제에서 모든 도시를 방문하지 못하는 경우의 수는 없다고 되어있기 때문에 이때가 길이가 짧아 가장 베스트인 정답이 된다.

이때 정렬을 돌려서 알파벳이 낮은 순서에서부터 DFS를 탐색하고 가장 먼저 배열 사이즈가 티켓배열+1 이 되는 답을 찾으면 

그떄가 모든 조건을 만족하는 답이 된다.

 

 

두번쨰 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void DFS(vector<string> &temp, vector<vector<string>> tickets, vector<string> &answer, vector<bool> &visited) { 
    if (!answer.empty())
        return;
    
    if(temp.size() == tickets.size() + 1) {
        if(answer.empty())
            answer = temp;
    }
    
    string now = temp[temp.size() - 1];
    for(int i = 0;i < tickets.size();i++) {
        if (tickets[i][0] == now && !visited[i]) {
            visited[i] = true;
            temp.push_back(tickets[i][1]);
            DFS(temp, tickets, answer, visited);
            visited[i] = false;
            temp.pop_back();
        }
    } 
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<string> temp;
    vector<bool> visited(tickets.size(), false);
    
    temp.push_back("ICN");
    sort(tickets.begin(), tickets.end());
    DFS(temp, tickets, answer, visited);
    
    return answer;
}