백준 13023: ABCDE(친구 관계 파악)

📃 문제: 백준 2023(신기한 소수)

13023번: ABCDE

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

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

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

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

 

🥇 난이도: 골드 5

 

 

😲 사용한 개념: DFS(깊이우선탐색)

 ☝️ DFS란?

1️⃣ 탐색 시작 노드 정보를 스택에 삽입하고  pop연산과 동시에 방문처리 한다.
2️⃣ 스택 내 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드 정보를 스택에 삽입하고

pop연산과 동시에 방문 처리한다.
만일 방문하지 않은 인접 노드가 없다면 스택 내 최상단 노드를 꺼낸다.(빈 스택 상태)
3️⃣ 아직 방문처리되지 않은 수 중 가장 작은 수를 push하여, 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

 

📖 풀이 사고 과정

 

👩‍💻 구현 코드(c++ 사용)

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

bool isFind = false;
vector<vector<int>> A;
vector<bool>visited(2000, false);
int N, M;
void DFS(int num, int digit) {
    //5명이상이 연결되어있으면 조건을 만족
    if (digit == 5) {
        isFind = true;
        return;
    }
    if (visited[num]) return;

    visited[num] = true;
    for (int next : A[num]) {
        if (!visited[next]) {
            DFS(next, digit + 1);
        }
    }
    visited[num] = false;
    
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int start, end;
    cin >> N >> M;
    A.resize(N);
    //문제 입력
    for (int j = 0; j < M; j++) {
        cin >> start >> end;
        A[start].push_back(end);
        A[end].push_back(start);
    }
    //
    for (int i = 0; i < N && !isFind; i++) {
        //한 시작점이 갱신될 때마다 visited 배열 초기화
        fill(visited.begin(), visited.end(), false);
        DFS(i, 1);
    }
    if (isFind == true) cout << 1;
    else cout << 0;
    
    return 0;
}