백준 13023 ABCDE

문제 설명

13023 ABCDE 문제 링크

일단 문제를 이해하는 것도 어려웠다.😥 (설명이 너무 부족한 거 아닌가...)

문제를 정리하자면 n명의 사람이 있고, m개의 관계가 주어진다. 이것을 n개의 노드와 m개의 간선 형태로 그렸을 때 쭈루룩 5명이 이어지는 경우가 있는가?이다.
정리하자면 ⇒ 한 번 지난 노드를 다시 거치지 않고, 5명 한붓그리기

문제 풀이

문제만 해석했다면 DFS로 풀어야 한다는 것은 쉽게 파악할 수 있다. 하지만 단순히 DFS로 작성하면 시간초과가 뜬다.

💡 전부 탐색하면 안된다

2중 벡터에 연결 지점을 저장해두고 for문을 돌면서 모든 노드 탐색하며 연결된 것 찾기? (X)
각 노드에 연결된 노드들만 벡터나 큐에 담아둬서 연결된 노드만 탐색하기! (O)

💡 DFS() 이후 visit에 false 처리 까먹지말기

visit[vec[i][j]] = false; 그래야 다시 돌아가서 탐색할 수 있다.

💡 정답이 나왔다면 exit(0)

flag에 기록하면서 다 돌면 시간초과 뜬다.
단순히 return하면 함수 밖으로만 나가기 때문에 문제대로 cout << 1 출력하고 exit(0)으로 끝내버린다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<vector<int>> vec;
vector<bool> visit;

void DFS(int i, int cnt) {
    if (cnt == 5) {
        cout << 1;
        exit(0);
    }
    for (int j = 0; j < vec[i].size(); j++) {
        if (!visit[vec[i][j]]) {
            visit[vec[i][j]] = true;
            DFS(vec[i][j], cnt + 1);
            visit[vec[i][j]] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin >> n >> m;
    vec.clear();
    vec.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    for (int i = 0; i < n; i++) {
        visit.assign(n, false);
        visit[i] = true;
        DFS(i, 1);
    }
    cout << 0;
    return 0;
}