[백준]13023번 ABCDE - C++

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

13023번: ABCDE

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

---

 한 사람이 노드이며 친구관계가 엣지인 그래프라고 생각할 수 있다.

이때, 4개의 노드가 연결되어 있으면 조건을 충족한다.

따라서 깊이 우선 탐색을 하면서 깊이가 4번 들어가게 되었다면 flag를 활성화시킨다.

flag의 활성화 여부에 따라 출력 값을 정할 수 있다.

#include <iostream>
#include <vector>

using namespace std;
int N,M,a,b;
vector <int> adj[2001];
bool vis[2001],flag;
void dfs(int cur, int n){
    if(!flag){
        if(n == 5){
            flag = true;
            return;
        }
        vis[cur] = true;
        for(int i = 0 ; i < adj[cur].size();i++){
            if(!vis[adj[cur][i]])
                dfs(adj[cur][i],n+1);
        }
        vis[cur] = false;
    }
}

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    for(int i = 0 ; i < M ;i++){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 0 ; i < N ;i++){
        for(int j = 0 ; j < adj[i].size();j++){
            if(!flag && !vis[adj[i][j]])
                dfs(adj[i][j],1);
        }
        if(flag) break;
    }
    if(flag) cout << 1;
    else cout << 0;
}

---

 문제를 보자마자 깊이 우선 탐색으로 짤 수 있을 것 같다는 생각을 하였고 바로 코드를 작성하였다. 모든 예제가 한 번에 잘 되어서 제출까지 했으나 45%에서 틀렸습니다가 나왔다. 아무리 봐도 알고리즘 적으로 문제가 없지만 여러 생각을 하게 되었고 30분 정도 고민한 결과 알고리즘과 예외처리는 문제가 없고 오타일 가능성이 있을 것 같아 코드를 한 줄 한줄 읽어본 결과 main 함수에서 dfs를 호출하는 이중 for문 의 inner loop의 증감문이 i++ 로 되어있던 것이었다. 예제의 경우 모두 첫 번째 관계가 포함된 친구관계가 정답에 포함되었나보다. 심지어 채점 환경조차 45%까지는 첫번째 친구관계가 포함된 것이 정답이었나 보다. 

 도저히 모르겠어서 구글에 문제 번호까지 치고는 한 번만 더 보자고 한 게 발견이 되었다. 내가 종종 증감문을 잘 못쓰거나 하는 경우가 있어 확인해봤는데 맞았다. 앞으로도 이런 실수가 있다면 더 빨리 잡아낼 수 있을 것 같다!