백준 5567번 결혼식 [그래프] :: 마이구미

이번 글은 백준 알고리즘 5567번 "결혼식" 을 다뤄본다.

그래프를 통해 문제를 해결할 수 있다.

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

문제는 상근이의 친구와 상근이의 친구의 친구를 초대할 수 있다.

1. 상근이의 친구
2. 상근이의 친구의 친구

위의 2가지의 조건에 성립되는 친구를 초대할 수 있다.

상근이의 친구의 친구의 친구는 초대할 수 없다.

그림을 통해 표현하는 것이 가장 이해가 빠를 것이다.

그림의 친구 관계는 주어지는 예제로 표현한다.

1 2
1 3
3 4
2 3
4 5

빨간색은 상근이(1), 파란색은 상근이의 친구, 초록색은 상근이의 친구의 친구를 나타낸 것이다.

5는 상근이의 친구의 친구의 친구로 표현할 수 있다.

6은 표현하자면, 상근이와 아예 관련이 없는 친구이다.

위와 같이 정점과 간선으로 표현할 수 있다.

그래프의 이론은 본인의 그래프 관련 글을 읽길 바란다. (그래프 DFS, BFS)

우선 인접행렬을 구현해보자.

for (int i = 0; i < m; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();

    array[a][b] = true;
    array[b][a] = true;
}

구현한 인접행렬은 주어지는 정점들간의 간선이 표현되어있다.

여기서 문제에서는, 2가지의 조건을 바탕으로 인접행렬을 활용하면 된다.

일반적으로 인접행렬은 DFS, BFS을 구현하기 위해 사용된다.

정점들간의 연결되어 있는 모든 간선들을 통해 문제를 해결한다.

그렇기에, 일반적인 방법으로는 위에서 표현한 (1, 2, 3, 4, 5) 을 찾을 수 있다.

하지만 우리는 알다시피 5는 조건에 맞지 않기 때문에 초대를 할 수 없다.

우리는 상근이와 연결된 정점과 상근이와 연결된 정점에 연결되어 있는 정점들을 찾아야한다.

계속해서 상근이와 연결된 정점과 상근이와 연결된 정점에 연결되어 있는 정점 언급되고 있다.

상근이와 연결된 정점들을 저장한다. 저장된 정점들은 상근이의 친구를 나타낸다.

저장된 각 정점들에게 연결된 정점들은 상근이의 친구의 친구이다.

for (int i = 0; i < m; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();

    if (a == 1) {
        list.add(b);
        ans++;
        visited[b] = true;
    }

    array[a][b] = true;
    array[b][a] = true;
}

for (int v : list) {

    for (int i = 2; i <= n; i++) {
        if (array[v][i] && !visited[i]) {

            ans++;
            visited[i] = true;

        }
    }

}

단순히 인접행렬을 활용하는 문제이다.

문제가 원하는 것이 무엇인지 파악한다면 쉽게 해결할 수 있다.

물론 다른 방법으로 풀 수 있겠지만, 가장 적합한 풀이 방식이 아닐까 생각한다.

다른 그래프 문제들도 본인의 블로그 카테고리를 통해 참고하길 바란다.

전체 소스는 아래 Github 링크를 참고하길 바란다.

백준 알고리즘 5567번 결혼식 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/5567.java