백준 13023: ABCDE

문제 요약

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

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

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.
  위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS
• 백트래킹

문제 풀이

조건에 따라 A~E의 정점이 DFS로 연결되어있는지 확인하는 문제이다. 프로그램의 골격은 기본적인 DFS와 같으나, 방문한 정점이 5개가 되면 1, 그렇지 않으면 0이다.

간선은 multimap<>으로 구현하였고, 방문 여부는 visited[]로 체크하였다.
현재 정점에서 다음 정점으로 탐색 가능하다면 탐색하며, 되돌아올때는 다시 방문 여부를 false로 바꿔주었다.

방문을 0~n-1의 정점까지 반복해주면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int n, m;
multimap<int, int> g;
bool visited[2000];

bool dfs(int idx, int cnt)
{
    if (cnt == 4) return true;
    auto rg = g.equal_range(idx);

    for (auto& it = rg.first; it != rg.second; it++) {
        if (!visited[it->second]) {
            visited[it->second] = true;
            if (dfs(it->second, cnt + 1)) return true;
            visited[it->second] = false;
        }
    }
    return false;
}

int main() {
    int in, in2, res = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &in, &in2);
        g.insert({ in ,in2 });
        g.insert({ in2 ,in });
    }
    for (int i = 0; i < n; i++) {
        visited[i] = true;
        if (dfs(i, 0)) {
            res = 1;
            break;
        }
        visited[i] = false;
    }
    cout << res;
    return 0;
}