[BOJ / C++] 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을 출력한다.

Solved.ac 레벨

골드 V

풀이

문제에서 나온  A > B > C > D > E 관계, 즉 DFS의 Depth가 4인 경우가 있는지를 판단하는 백트래킹 문제였다.

예제 1과 3을 그래프로 나타낸다면 위와 같다.

예제 1의 경우에는 문제에서 설명한 A > B > C > D > E 구조 그대로이며, 0 (A)에서 시작해서 Depth가 4. 예제 출력은 1이다.

예제 3의 경우에는 0과 각각의 노드는 연결이 되어있지만 최대 Depth가 1밖에 되지 않으므로 A > B > C > D > E 구조가 성립되지 않으며 예제 출력은 0이다.

 

따라서 DFS를 재귀로 구현하며, 시작 노드와 현재 Depth를 함께 넘겨 재귀 호출하여 Depth가 4인지 아닌지 판별해야 한다.

Code

#include<bits/stdc++.h>

using namespace std;

int n, m;
bool visited[2001];
vector<int> v[2001];
bool chk;

void DFS(int start, int depth) {
    if(depth == 4) {
    	//depth가 4 달성시 플래그를 true로 바꾸고 함수 종료.
        chk = true;
        return;
    }

    for(int i = 0; i < v[start].size(); i++) {
        int nxt = v[start][i];

        if(!visited[nxt]) {
            visited[nxt] = true;
            DFS(nxt, depth + 1);
            visited[nxt] = false;
            //이후 노드의 탐색을 위해 방문 여부 초기화
        }
    }
}

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

    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i = 0; i < n; i++) {
        visited[i] = true;
        DFS(i, 0);
        visited[i] = false;

        if(chk) break;
    }

    cout << chk << "\n";

    return 0;
}

 

13023번: ABCDE