[C++] 13023번 - ABCDE (DFS) (exit(0) 사용)

문제 링크 : www.acmicpc.net/problem/13023

13023번: ABCDE

 

 

문제

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

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

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

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

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

 

 

 

---

접근 방법

문제에서 아래의 조건이 주어졌다.

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

이는 N명에게 연결된 친구를 각각 dfs 로 타고 가봤을 때, 그 깊이가 4가 되는게 있는지를 확인해서 풀 수 있다. 

벡터 배열을 이용해 양방향으로 친구 관계를 연결해주고 벡터 배열 크기만큼 dfs를 돌린다.

첫번째와 두번째 방법은 같으나

첫번째는 flag 변수와 return; 으로 dfs를 중단해보았고

두번째는 exit(0); 으로 즉시 종료를 해보았다.

 

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int visited[2000] = {0};
vector<int> vecArr[2000];
bool flag = false;
 
void dfs(int start, int depth){
    
    visited[start] = 1;
    
    if(depth==4){
        flag = true;				//더 이상 dfs 실행 안 되게 함. 
        cout << 1 << "\n";
        return;
    }
    
    for(int i = 0; i<vecArr[start].size(); i++){
        if(visited[vecArr[start][i]]==0 && !flag){		//위에서 flag=true 됐으면 조건문 실행 x
            dfs(vecArr[start][i], depth+1);				//타고 들어갈 때마다 depth 증가
        }
    }
 
    visited[start] = 0;
    
}
 
 
 
 
int main(){
 
    queue<int> que;
    
    int N,M;
    cin >> N >> M;
    
    int a, b;
    for(int i = 0; i<M; i++){			//관계 양 방향 연결 (벡터 배열 사용)
        cin >> a >> b;
        
        vecArr[a].push_back(b);
        vecArr[b].push_back(a);
        
    }
    
    
    for(int i = 0; i<N; i++){
        dfs(i,0);
    }
    
    if(!flag) cout << 0;				//다 탐색 했는데 깊이가 4 된 경우 없으면 0 출력.
    
    return 0;
}

 

 

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int visited[2000] = {0};
vector<int> vecArr[2000];
 
void dfs(int start, int depth){
    
    visited[start] = 1;
    
    if(depth==4){
        cout << 1 << "\n";
        exit(0);						//즉시 종료. 
    }
    
    
    for(int i = 0; i<vecArr[start].size(); i++){
        if(visited[vecArr[start][i]]==0){
            dfs(vecArr[start][i], depth+1);
        }
    }
    
    visited[start] = 0;
    
}
 
 
 
 
int main(){
 
    queue<int> que;
    
    int N,M;
    cin >> N >> M;
    
    int a, b;
    for(int i = 0; i<M; i++){
        cin >> a >> b;
        
        vecArr[a].push_back(b);
        vecArr[b].push_back(a);
        
    }
    
    
    for(int i = 0; i<N; i++){
        dfs(i,0);
    }
    
    cout << 0; 				//dfs()에서 즉시 종료 했으므로 depth==4가 있는 경우 해당 코드 실행 x.
    
    return 0;
}