[백준] 13023번 : ABCDE

---

🔗 문제 링크

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

---

반응형

728x90

👩‍💻 코드

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

static bool isArrive = false;

void DFS(int node, vector<bool> &visited, vector<vector<int>> &graph, int count) {
    if (count == 4 || isArrive) {
        isArrive = true;
        return;
    }

    visited[node] = true;

    for (int i : graph[node]) {
        if (!visited[i]) {
            DFS(i, visited, graph, count+1);
        }
    }

    visited[node] = false;
}

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

    int N;
    int M;
    cin >> N >> M;

    vector<vector<int>> graph(N);
    vector<bool> visited(N, false);

    for (int i = 0; i < M; i++) {
        int a;
        int b;

        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 0; i < N; i++) {
        DFS(i, visited, graph, 0);

        if (isArrive) {
            break;
        }
    }

    if (isArrive) {
        cout << 1 << "\n";
    }else{
        cout << 0 << "\n";
    }

    return 0;
}

---

📝 풀이

Do it! 알고리즘 코딩테스트 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

 

DFS 알고리즘을 사용하여 구현했습니다.

모든 노드에서 DFS를 수행합니다.

수행할 때마다 count를 더하여 수행합니다.

count가 4가 됐을 때 조건을 만족하는 경우이므로 1을 출력합니다.

도달하지 못 한 경우 조건을 만족하지 못 한 경우이므로 0을 출력합니다.