[BOJ/백준] 13023 ABCDE

● [문제번호 13023] ABCDE

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

13023번: ABCDE

 

● 알아야 할 것

: 그래프

: DFS

: 재귀

 

● 풀이 과정

: 앞서 풀었던 DFS와 비슷하지만, 그래프에 적용하여 구현된 DFS이다.

 

: 문제를 이해하기 조금 헷갈릴 수 있는데 이해한 바로는

주어진 친구 관계도에서 5명을 한번에 이어질 수 있는가 를 확인하면 된다.

 

: BFS보다 DFS를 이용하여 구현해야겠다는 생각이 들었다.

DFS는 재귀와 반복문을 이용하여 구현할 수 있는데

반복문으로 계속 시도하려다 친구 관계 5명을 확인하는 부분이 복잡하게 구현될 것 같아서

DFS 재귀 를 이용하여 구현했다. (구글링)

 

: Base Case는 친구 관계가 5명이 된 경우이고,

 

1. 정점 체크인

 

2. 해당 정점과 연결된 정점 중 방문하지 않은 정점을 방문

(재귀 → 1번으로 되돌아감)

 

3. 정점 체크아웃

 

이 과정을 구현하면 된다.

 

● 주의 할 것

: 출발하는 정점이 달라질 때마다

정점의 방문기록을 초기화해야한다.

 

● 참고 할 것

: 풀이과정 참고

https://jdselectron.tistory.com/34

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// V : 각 index 정점의 연결된 정점집합
// visited : 정점의 방문기록
vector<int> V[2000];
vector<bool> visited;
int N, M;

// DFS_재귀 (from : 간선의 출발정점 / cnt : 친구 관계수)
int dfs(int from, int cnt)
{
    // 친구 관계가 5명이 된 경우
    if(cnt == 4)
        return 1;

    // 정점 체크인
    visited[from] = true;
    
    // 방문한 정점의 이어진 모든 정점 탐색
    for(int i = 0; i < V[from].size(); i++)
    {
        int to = V[from][i];
        
        // 연결된 정점 중 방문하지 않은 정점이라면
        if(!visited[to])
        {
            // 재귀 (반환값이 1 : 친구 관계가 5명이 된 경우)
            if(dfs(to, cnt + 1))
                return 1;
        }
    }
    
    // 정점 체크아웃
    visited[from] = false;
    
    // 아직 친구 관계 5명 못 찾은 경우
    return 0;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 간선 입력
    for(int m = 0; m < M; m++)
    {
        int a, b;
        cin >> a >> b;
        
        V[a].push_back(b);
        V[b].push_back(a);
    }
    
    // 각 정점에서 출발하는 모든 경우 탐색
    for(int i = 0; i < N; i++)
    {
        // 방문기록 배열 만들기
        visited.assign(N, false);
        
        // 친구 관계 5명 된 경우 탐색 중지
        if(dfs(i, 0))
        {
            cout << 1;
            break;
        }
        // 모든 정점을 탐색할 동안
        // 친구 관계 5명이 되지 않은 경우
        else if(i == N - 1)
            cout << 0;
        
        // 방문기록 배열 삭제
        visited.clear();
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277