[백준] 13023번 : ABCDE - C/C++

문제에서 말하는 친구 관계에 대해 다시 살펴보자.

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

간단하지만 문제에서 말하고 있는 문장을 도식화하면 위와 같다.

 

사람의 수를 node라고 볼 수 있고, 친구 관계의 수는 edge라고 볼 수 있다.

각각 2,000이 MAX 임을 문제에서 이야기하고 있다.

그래프를 보고 위의 그림과 같은 관계가 있는지 파악하는 문제이다.

 

예제 입력4를 그림으로 그려서 확인해 보자.

그림은 이렇게 그릴 수가 있다.

이제 친구 관계가 위에서 본 것과 같이 일자로 된 것이 있는지 확인해보자.

0번 노드에서 출발하여 2번 노드까지 도착하는 것을 도식화하면 아래와 같다.

ABCDE 순서로 일자로 나열되기 때문에 해당 예시는 1을 출력하게 되는 것이다.

 

13023번은 아래와 같이 해결할 수 있다.

노드와 엣지가 존재하기 때문에 DFS 로 해결 가능하다.

BFS로 풀어도 가능은 하다.

 

문제 풀이 순서는 아래와 같다.

 

1. 그래프 데이터는 인접 리스트로 저장한다. (1 → 7을 저장했다면, 7 → 1도 저장하자.)

2. 모든 노드에서 DFS 수행
깊이가 5가 되면 1 출력 후 프로그램 종료
(ABCDE는 총 5개의 노드이기 때문)

3. 모든 노드를 돌았는데 1이 출력되지 않을 때 0 출력

 

static으로 vector를 설정해주자.

static vector<vector<int>> a;
static vector<bool> visited;
static bool arrive;

방문한 배열도 vector로 만들고, 해당 노드에 도착했는지 판단할 수 있는 bool 형태를 선언한다.

 

초기값으로 arrive는 false로 설정한다.

또한 n과 m을 입력받은 후 vector의 사이즈를 n으로 수정해주어야 한다.

int n, m;
arrive = false;
cin >> n >> m;
a.resize(n);
visited = vector<bool>(n, false);

 

그리고 데이터를 저장해주어야하는데,

여기서 주의할 점은 위에서 언급했던 '양방향'이다.

1 → 7와 7 → 1을 고려하여 부분 코드를 작성하면 아래와 같다.

for(int i = 0; i < m; i++){
   int start, end;
   cin >> start >> end;
   a[start].push_back(end);
   a[end].push_back(start);
}

 

작성했다면 각 노드마다 DFS를 실행해주면 된다.

for(int i = 0; i < n; i++){
   DFS(i, 1);
   if(arrive){
     break;
   }
}

 

이상태로만 작성하면 DFS 부분에 에러가 난다.

당연함. DFS 함수를 아직 안 만들었음.

 

DFS 함수를 main() 함수 위에 선언해주자.

아래에 작성해도 상관은 없는데, 아래에 쓰게 되면 아래에 DFS 함수가 있다는 것을 코드로 한 줄 더 작성해야하니까 필자는 위에다가 그냥 작성할 것이다.

 

DFS 함수로 넘겨주는 값은 현재 노드와 깊이이다.

depth가 5일 때 arrive를 true로 바꿔주면서 return 해준다.

if(depth == 5 || arrive){
  arrive = true;
  return;
}
visited[now] = true;

if문 안에 있는 arrive는 왜 조건식에 같이 넣었는지 궁금할 수 있다.

return으로 빠져나가면서 이미 도착한 노드가 arrive로 빠져나갈 수도 있어서 arrive도 조건식에 추가해야한다.

 

그리고 현재 노드에 연결되어 있는 모든 노드를 for문을 통해 한 번씩 방문하는 코드를 작성하자.

for(int i : a[now]){
   if(!visited[i]){
   DFS(i, depth + 1);
   }
}

 

 

 

 

 

전체 코드

#include <iostream>
#include <vector>

//ABCDE
using namespace std;

static vector<vector<int>> a;
//방문 배열을 vector로 만들기
static vector<bool> visited;
//도착을 했는지 판단
static bool arrive;

void DFS(int now, int depth){
    //return으로 빠져나가면서 이미 도착한 노드가 arrive로 빠져나갈 수도 있기 때문에 다음과 같이 코드 작성
    if(depth == 5 || arrive){
        arrive = true;
        return;
    }
    visited[now] = true;
    
    //현재 노드(a[now])에 연결되어 있는 모든 노드를 for문을 통해서 한 번씩 방문하는 코드
    for(int i : a[now]){
        if(!visited[i]){
            DFS(i, depth + 1);
        }
    }
    visited[now] = false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    arrive = false;
    cin >> n >> m;
    //노드의 개수가 n개니까 사이즈 수정
    a.resize(n);
    visited = vector<bool>(n, false);

    //그래프의 데이터 저장하기
    for(int i = 0; i < m; i++){
        int start, end;
        cin >> start >> end;
        //양방향으로 저장해주어야함.
        a[start].push_back(end);
        a[end].push_back(start);
    }
    //노드마다 DFS 실행
    for(int i = 0; i < n; i++){
        DFS(i, 1);
        if(arrive){
            break;
        }
    }
    if(arrive){
        cout << 1 << '\n';
    } else {
        cout << 0 <<'\n';
    }
}

 

 

 

 

골드5의 난이도였다. 이번 문제는 유튜브 영상 강의의 도움을 받았다. DFS도 BFS도 개념은 알고 있는데 코드로 구현하는 것이 항상 어려웠다. 그래도 이번 문제를 해결하면서 코드로 구현하는 방법에 대해서 많이 익숙해진 것 같다. 백준 13023번 문제의 알고리즘 분류는 '그래프 이론', '그래프 탐색', '깊이 우선 탐색', '백트래킹' 이었다. 어렵다.. 더 많은 문제를 풀고 익숙해져야겠다.

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️