[백준] 5567 결혼식

너비 우선 탐색을 살짝 응용하면 되는 문제이다. 문제를 보면 노드의 수 (동기의 수), 주어지는 노드간 연결관계의 수 (리스트의 길이), 노드간 연결관계 (친구 관계) 가 주어진다. 이를 이용하여 문제를 풀 수 있다.

 

너비 우선 탐색

---

문제를 풀기 위해서는 너비 우선 탐색에 관한 알고리즘의 이해가 필요하다. 2중 반복문을 이용해서 풀 수도 있으나, 너비 우선 탐색을 사용하는 것이 다른 문제에 응용하기 좋다.

 

너비 우선 탐색은 그래프 탐색에 사용된다. 목표 지점에 도달하기 위해서 경로를 탐색하되, 출발점에서 같은 거리의 노드를 탐색한다. 여기에는 큐가 필이 사용된다.

 

bfs의 기본 원리는 다음과 같다.

1. 시작 노드를 queue에 저장한 후 bfs 탐색을 실행한다.
2. 큐에 있는 노드를 pop 한 후 해당 노드에 대한 연결되어 있는 노드가 방문하지 않았다면, queue에 저장한다.
3. pop한 노드는 방문했다는 기록을 남긴다.
4. 이 과정을 q에 모든 원소가 사라질 때까지, 2번으로 돌아가서 반복한다.
5. 방문이 모두 완료되었다. 문제에서 원하는 답에 대하여 알고리즘을 조정한다.

 

말만 들으면 이해가 잘 안될 수도 있다. 그림으로 천천히 알아보자.

 

 

위와 같은 그래프(지도) 가 있다. 시작점에서 목표지점까지 bfs로 탐색하는 과정을 알아보자.

 

 

시작점을  queue에 저장한다.

 

 

pop을 실행한 후 시작노드와 연결되어 있고 방문하지 않은 지점들은 queue에 push 한다.

 

 

queue 에서 pop을 실행한 후, 1번 노드에 대해서 같은 작업을 실행한다. 이와 같은 작업을 계속 반복한다.

 

 

모든 탐색이 완료 되었다. 5567 문제에서는 이전 방문한 기록 + 1 = 현재 방문한 기록 을 해주어서 방문 횟수를 1씩 증가시켜서, 방문한 곳의 값이 3이 될 경우 (시작점 : 1) 프로그램을 종료하고 방문한 노드의 개수를 출력하는 코드를 작성하였다 결과 코드는 다음과 같다.

 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
 
/*
간단한 bfs 문제이다.
2차원 배열을 이용해 풀어도 되지만, 벡터에 push_back을 해주면 크기가 훨씬 작아진다.
탐색할 때마다 친구의 수를 늘려주고, 방문한 배열은 시작 지점부터의 거리를 입력해 준다.
방문한 배열의 거리가 3이 되는 지점을 탐색하는순간, while문을 종료한다.
*/
 
vector<int> v[501];
queue<int> q;
int visited[501];
int n, m, ans = 0;
 
void bfs()
{
    visited[1] = 1;
    q.push(1);
 
    /* 큐에 원소가 없을 때까지 실행 */
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        /* 친구의 친구를 넘어서는 경우, 종료 */
        if (visited[x] == 3)
            break;
        /* 현재 탐색 노드와 연결된 모든 노드에 대하여 탐식 */
        for (auto start = v[x].begin(); start != v[x].end(); start++)
        {
            int next = *start;
            if (!visited[next])
            {
                ans++;
                visited[next] = visited[x] + 1;
                q.push(next);
            }
        }
    }
}
 
int main()
{
    memset(visited, 0, sizeof(visited));
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        /* 양방향 그래프이므로 두 군데 정보를 입력한다. */
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs();
    printf("%d", ans);
}