[백준] 13023번 : ABCDE

문제

 

---

풀이

 

먼저 모든 친구 관계를 저장한다. 메모리를 아끼기 위해

myunji.tistory.com/291?category=1154147

[백준] 1707번 : 이분 그래프

이때 썼던 방법으로 저장했다.

 

i번째 사람을 시작점으로 하는 dfs를 N번 돌리면서 문제의 조건에 맞는 친구 5명을 찾으면 리턴한다.

문제를 풀고 다른 사람들의 코드를 보니 친구 관계 4개를 찾는걸 종료 조건으로 한 사람들이 많았다.

근데 그거나 이거나 같은 말이니까 상관없다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
bool isExist;

void dfs(int cur, int num) {
    if (num == 5) { //친구 5명을 찾음
        cout << 1;
        isExist = true;
        return;
    }
    for (int i = 0; i < graph[cur].size(); i++) {
        if (!visited[graph[cur][i]] && !isExist) {
            visited[graph[cur][i]] = true; //visited 처리
            dfs(graph[cur][i], num + 1);
            visited[graph[cur][i]] = false; //unvisited 처리
        }
    }
}

int main() {
    int N, M, first, second;

    cin >> N >> M;
    graph.assign(N, vector<int>(0));
    visited.assign(N, false);
    for (int i = 0; i < M; i++) { //리스트 형태로 저장
        cin >> first >> second;
        graph[first].push_back(second);
        graph[second].push_back(first);
    }
    for (int i = 0; i < N; i++) { //i를 시작점으로
        visited[i] = true;
        dfs(i, 1);
        visited[i] = false;
    }
    if (!isExist) //친구 관계 못찾음
        cout << 0;
}