JArchive 프로그래밍 일기

문제

ABCDE 백준 13023번

리뷰

N명이 캠프를 가는데, 친구관계가 ABCDE 가 존재하는지 확인하는 문제다.

N명이 모두 친구인건지 확인하는 건줄 착각하고 처음에 틀리게 풀었다.

그러니까 DFS로 풀면, depth가 4인지만 확인하면 되는 것이다.

인접리스트로 간선을 구현하고, DFS에서 노드 방문 여부를 표시하기 위해 check 배열을 만들었다.

DFS로 탐색 하되, 여기서는 0,1,2,3,4 의 depth 4 를 만족하면 바로 종료시킨다.

코드

#include <iostream> 
#include <vector>
#include <cstring> // memset()
#include <algorithm>
#define MAX 2000
using namespace std;

int N, M;
int answer = 0;
vector<int> V[MAX];
int visited[MAX+1];

void DFS(int idx, int depth){

    if(depth == 4){ //  0,1,2,3,4 로 이어진 depth 4 라면 answer 1 로 갱신 
        answer = 1;
        return;
    }

    visited[idx] = 1; // 현재 노드 방문 표시 

    for(int i = 0; i < V[idx].size(); i ++){

        int next = V[idx][i]; // 다음 노드 

        if(!visited[next]){ // 다음 노드가 안가본 노드라면, 가본다. 
            visited[next] = 1;
            DFS(next, depth+1);
            visited[next] = 0;
        }
    }
}

int main(void){

    cin >> N >> M; // 노드, 간선 개수  

     int start=0, end=0;

     for(int i = 0; i < M; i++){ // 간선 개수 만큼 입력
        cin >> start >> end;
        V[start].push_back(end);
        V[end].push_back(start); 
    } // 입력받기 끝  

    // 시작 노드를 바꿔가며 0,1,2,3,4 로 이어진 depth 있는지 확인  
    for(int i = 0; i < N; i++){

        memset(visited, 0, sizeof(visited)); // 방문 배열 초기화  
        visited[i] = 1;
        DFS(i, 0); 

        if(answer == 1) break; 
    }

     cout << answer;

    return 0;    
}