[C++] 백준 16168 - 퍼레이드 ( 직관적인 DFS 풀이 )

문제 이해 단계

---

https://www.acmicpc.net/problem/16168

16168번: 퍼레이드

 

노드(지점)의 개수 V와
간선(연결 구간) E가 입력으로 들어온다.


이후, 다음 줄에 V1과 V2가 M개가 들어온다.

해당 입력이 들어올 때,
노드는 중복해서 지나갈 수 있고,
간선은 한 번밖에 지나가지 못한다.

모든 간선을 지날 수 있을지 없을지에 판단하고,
가능하면 "YES" 없으면 "NO"를 출력해라

 

 

 

 

 

문제 접근 단계

---

문제 자체는 굉장히 심플하다.


그냥 흔한 노드와 간선을 가지고 그래프를 탐색하는 문제이다.

다른 점이라면 보통 노드 방문을 하는 것인데,
이건 간선을 방문하는 탐색이라는 것이다.


그리고 노드를 중복해서 반복할 수 있다는 것이 특징이다.

위에서 구하라는 것을 요약해 보자면,
그냥 한붓그리기가 가능하냐고 묻는 문제이다.


보통 한붓그리기를 하면 오일러 공식(알고리즘)을
이용해서 푼다고 하는데, 나는 사용할 줄 모른다(...)


오일러 공식에 대해서는 따로 공부해서
블로그에 개념을 올리도록 하겠다...


역시 아직 갈길이 멀다..

그래서 나는 해당 문제를 좀 직관적으로 풀어보도록 하겠다.

 

 

 

 

시뮬레이션 돌려보기

직관적으로 풀어보기 위해서,
일단 예제케이스를 통해 어떻게 답이 나오나 한번 보자.

 

가능한 경로의 일부를 나타낸 그림

이거 이외에도 가능한 경로는 더 있겠지만
이 정도만 살펴보자.

 

 

이 경로들의 공통점은
모두 1번 또는 2번 노드에서 시작한다는 것이다.


그럼 1번과 2번 노드의 공통점은 무엇일까?
바로 간선의 개수가 제일 많다는 것이다.

그럼 간선의 개수가 가장 많은 곳에서 시작하면
해당 그래프가 한붓그리기가 되는지 확인할 수 있는 걸까?



바로 두 번째 예제를 통해 알아보자.

해당 경로가 불가능한 이유

 

결과는 "No"로 나와있지만,
그래도 한번 시뮬레이션 돌려봤다.

위의 규칙대로 간선이 가장 많은 1번 노드에서
가능한 모든 순서를 돌려봤다.

최대한 많이 지나갈 수 있도록 했는데도,
어쩔 수 없이 실패했다.


간선을 제일 많이 가진 노드 1에서 실패했기 때문에
다른 노드에서도 실패할 수밖에 없다.

즉, 간선의 개수가 많은 노드에서 시작해야 하고,


1번 예제케이스 그림에서처럼
간선이 가장 많은 노드라면 어디서 어떻게 가든,
모든 간선을 순회할 수 있다.

 

 

 

 

그래프 탐색

이제 우리가 할 것은 노드를 옮겨가며
그래프를 탐색시켜 주는 것뿐이다.


여기서 중요한 것은 사용했던 간선이
다시는 사용되지 않도록 하는 것.

여기서 그래프 탐색은 BFS와 DFS 중 뭘로 하는 게 좋을까?


경로를 찾는 것이기 때문에
아무래도 DFS가 더 유리할 것이다.


간선이 다시 사용되지 않도록 하기 위해,
그냥 사용했던 간선은 없애기로 했다.

왜 사용했던 간선을 없애도 될까?
다른 케이스를 볼 때 필요하지 않나?


그렇지 않다.
왜냐하면 간선이 가장 많은 노드에서 시작하기만 하면
다른 케이스를 볼 필요가 없다.

위에서 언급했듯이,
간선이 가장 많은 노드이고 해당 그래프가 전체 노드를 순회하는 그래프라면,
어떤 간선을 선택하든 간에 간선을 순회할 수 있기 때문에
DFS를 한 번만 돌려도 된다.

그래서 그냥 한번 이동 후
사용한 간선을 없애주는 방법을 선택했다.

이제 문제 구현단계에서 코드를 보자.

 

문제 구현 단계

---

vector<int> v[3001]; // 지점(노드)를 담아줄 벡터

// DFS(노드,간선의 수)
bool dfs(int x, int count){
    // 간선의 수가 E와 같아진다면 
    if(count >= E) {
        // 노드 벡터 안에 남아있는 것이 하나라도 있으면 false
        for(int i = 1; i <= V; i++)
            if(!v[i].empty()) return false;
        return true;
    }
    bool ans = false;
    // 노드 x에 연결되어 있는 노드의 리스트를 하나씩 호출
    for(int i = 0; i < v[x].size(); i++){
        int next = v[x][i]; // 노드 x의 연결되어 있는 다음 노드
        v[x].erase(v[x].begin()+i); // 제거
        
        // 그 노드에서도 상호 연결이 되어있기 때문에 인덱스를 찾아 연결을 끊어줌
        auto it = find(v[next].begin(),v[next].end(),x);
        v[next].erase(it);
        // or 연산을 통해 하나라도 true면 true
        ans = ans | dfs(next,count+1);
        i--; // i가 하나 줄었으므로 i--
    }
    return ans;
}

그래프 탐색을 통해 순회가 가능한지 체크하는 dfs 함수이다.


매개변수로 노드 x와
현재까지 사용한 간선의 수 count가 들어간다.

당연히 리턴할 때는 간선의 수를
E만큼 모두 사용했을 때이다.


우리는 해당 간선을 이용할 때마다 삭제해 줄 것이기 때문에,
모든 간선을 사용한다면 남아있는 간선이 더 이상 없어야 한다.


그래서 남아있는 간선이 있다면 false를 반환해 준다.

여기서 v [k] = {1,2,3}이라고 하면,
노드 k와 노드 1, 노드 2, 노드 3과 통하는 간선이 있다는 뜻이다.

기본적으로 dfs는 아래의 로직으로 진행된다.

1.
해당 노드와 연결되어 있는 간선들을 호출한다.


2.
그 간선을 임시변수에 저장해 두고,
그 간선을 제거한다.


3.
그 간선을 통해 이동하여
연결되어 있는 노드로 도착한다(재귀함수 호출)


4.
그 노드로 다시 1~3번 행위를 반복한다.
(재귀함수 반복)

이를 count가 E에 다다를 때까지 반복한다.


결국 반환화는 것은
v배열 안에 간선이 남아있는지 없는지에 대한 것이다.

여기까지가 핵심함수에 대한 설명의 끝이다.


이제 아래에 전체 코드를 올려두고 끝내겠다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[3001]; // 지점(노드)를 담아줄 벡터
int V,E;
int sIdx; // 시작할 노드(간선이 제일 많은 노드)

// DFS(노드,간선의 수)
bool dfs(int x, int count){
    // 간선의 수가 E와 같아진다면 
    if(count >= E) {
        // 노드 벡터 안에 남아있는 것이 하나라도 있으면 false
        for(int i = 1; i <= V; i++)
            if(!v[i].empty()) return false;
        return true;
    }
    bool ans = false;
    // 노드 x에 연결되어 있는 노드의 리스트를 하나씩 호출
    for(int i = 0; i < v[x].size(); i++){
        int next = v[x][i]; // 노드 x의 연결되어 있는 다음 노드
        v[x].erase(v[x].begin()+i); // 제거
        
        // 그 노드에서도 상호 연결이 되어있기 때문에 인덱스를 찾아 연결을 끊어줌
        auto it = find(v[next].begin(),v[next].end(),x);
        v[next].erase(it);
        // or 연산을 통해 하나라도 true면 true
        ans = ans | dfs(next,count+1);
        i--; // i가 하나 줄었으므로 i--
    }
    return ans;
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> V >> E;
    for(int i = 0; i < E; i++){
        int v1,v2;
        cin >> v1 >> v2;
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }
    sIdx = 1;
    int max_size = 0;

    // 노드 중 간선이 가장 많은 노드를 찾아 sIdx로 저장
    for(int i = 1; i <= V; i++) {
        int size = v[i].size();
        if(size > max_size){
            max_size = size;
            sIdx = i;
        }
    }
    
    bool ans = dfs(sIdx,0);

    if(ans) cout << "YES";
    else cout << "NO";
}

 

 

 

 

 

시행착오

---

1시간 30분 정도 걸린 문제.
그래도 2시간 안에 푼 게 잘한 것 같다.


오일러 공식으로 많이들 풀던데,
풀이를 봐도 무슨 소리인지 잘 모르겠다.
따로 공부해서 블로그에 올려야겠다.

 

 

이런 식으로 증명되지 않은 가정을 세워두고 푸는 것은
위험한 짓이지만,  코딩테스트를 할 때는
찬밥 더운밥 가릴 때가 아닌 것 같다.


파이팅