[BOJ](Python) 백준 5567번: 결혼식

문제

https://acmicpc.net/problem/5567

5567번: 결혼식

주제	그래프 구현/순회
시간 / 메모리 제한	1초 / 128MB
정답 비율	44.052%

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다.

상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다.

상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 갖고 있다.

이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 상근이의 동기의 수 n(2 ≤ n ≤ 500)이 주어진다.

둘째 줄에는 리스트의 길이 m(1 ≤ m ≤ 10000)이 주어진다.

다음 줄부터 m개의 줄에는 친구 관계 a_i, b_i(1 ≤ ai < bi ≤ n)이 주어진다. 

• a_i와 b_i가 친구라는 뜻이며, b_i와 a_i도 친구관계이다.

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

- 예제 입력 1

6
5
1 2
1 3
3 4
2 3
4 5

- 예제 출력 1

3

힌트

예제 1의 경우 2와 3은 상근이의 친구이다.

또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다.

5와 6은 친구도 아니고, 친구의 친구도 아니다.

따라서 2, 3, 4 3명의 친구를 결혼식에 초대한다.

- 예제 입력 2

6
5
2 3
3 4
4 5
5 6
2 5

- 예제 출력 2

0

풀이

그래프에 대한 자세한 개념은 작성해둔 아래의 포스트에서 학습하면 된다.

https://classic-griver.tistory.com/192

[알고리즘](Python) 그래프 개념과 파이썬 코드 구현

필요한 메서드는 위의 링크에서 가져와 사용하였다.

 

이 문제는 그래프의 너비 우선 탐색 즉, BFS를 수행하는 문제이다.

본인에 해당하는 1번 vertex를 기준으로 하여, L1으로 지정하고

인접 vertex로 퍼져나가 L2, L3에 해당하는 vertex의 총 개수를 세어주면 된다.

위 그림을 참고하여 아래에 사용한 명칭은 다음을 나타낸다.

• L1: 상근이
• L2: 상근이의 친구
  • L1의 인접리스트
• L3: 상근이의 친구의 친구
  • L2의 인접리스트

 

문제를 풀며 BOJ에서 '틀렸습니다.'라는 결과를 두 번 마주하였는데 그 풀이 중 하나가 아래의 풀이다.

 

오답 1 - L1의 인접 리스트만 순회, L2의 인접 리스트 비순회

import sys

class Graph:

    def __init__(self, vertex_num=None):
        self.adj_list = []
        self.vtx_num = 0
        self.vtx_arr = []
        if vertex_num:
            self.vtx_num = vertex_num
        self.vtx_arr = [True for _ in range(self.vtx_num)]
        self.adj_list = [[] for _ in range(self.vtx_num)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

g = Graph(n)
for _ in range(m):
    l = list(map(int, sys.stdin.readline().strip().split()))
    g.add_edge(l[0] - 1, l[1] - 1)

res = 0
for i in g.adj_list[0]:
    res += len(g.adj_list[i]) - 1

print(res)

주의해야 할 점은, 코드 상 vertex의 인덱스는 실제 친구의 이름에다가 1을 빼주어야 한다.

• 친구 2에 해당하는 vertex는 1

첫 번째 오답은 초대 인원을 세는 방법으로 L1에 해당하는 상근이(vertex 0)의 인접리스트만 직접 순회하였다.

그리고 L2에 해당하는 상근이 친구의 인접리스트는 직접 순회하지 않고 길이만 가져와 사용하였다.

이 방법의 문제점은 아래와 같은 상황에서 발생한다.

### 그래프 연결 상태
num of vertices : 6
vertices : {0, 1, 2, 3, 4, 5, }
[0] : {1,  2,  }
[1] : {0,  2,  3,  }
[2] : {0,  3,  1,  }
[3] : {2,  4,  1,  }
[4] : {3,  }
[5] : {}

만약 상근이의 친구의 친구가 겹친다면 이 겹치는 사람을 하나로 세지 못 하고 두 번 세게 된다는 것이다.

4번 친구의 경우 상근이의 친구인 2, 3번과 모두 친구인데

위 코드로 세게 될 경우 4번 친구가 2번이나 세어지게 된다.

 

따라서 단순히 상근이의 인접리스트인 L1만 순회하는 것이 아니라,

L1의 인접리스트인 L2까지 직접 순회하여

초대 리스트에 들어간 사람 간 겹치는지를 일일히 체크해주어야 된다는 것이다.

 

이러한 이유로 초대 리스트에 해당하는 guest 리스트를 추가하고

for 반복문을 추가하여 L1과 L2의 인접리스트를 직접 방문하는 코드로 수정하였다.

오답 2 - L1, L2의 인접 리스트 순회

import sys

class Graph:

    def __init__(self, vertex_num=None):
        self.adj_list = []
        self.vtx_num = 0
        self.vtx_arr = []
        if vertex_num:
            self.vtx_num = vertex_num
        self.vtx_arr = [True for _ in range(self.vtx_num)]
        self.adj_list = [[] for _ in range(self.vtx_num)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

g = Graph(n)
for _ in range(m):
    l = list(map(int, sys.stdin.readline().strip().split()))
    g.add_edge(l[0] - 1, l[1] - 1)

guest = [0]
for i in g.adj_list[0]:
    for j in g.adj_list[i]:
        if j not in guest:
            guest.append(j)

print(len(guest) - 1)

L1, L2의 인접리스트를 순회하며 guest 리스트에 초대할 친구들을 추가하는 방식으로 코드를 작성하였다.

재귀를 수행할 수도 있지만 반복문을 사용하는 것이 더 쉽고 직관적이라 반복문을 사용했다.

(시간 초과 시 재귀를 하려 했지만 문제가 없어 수정하지 않았다.)

 

하지만 위와 같은 코드에도 '틀렸습니다'라는 답변을 받았다.

정답 - 발생하는 예외 수정

예외를 찾을 수 있었는데, 위 코드 같은 경우에는 상근이의 친구가 또 다른 친구를 가지지 않는 경우에는 세어주지 않았다.

즉, 아래의 친구 7과 같이 L2만 있고 L3가 없는 경우에 L2의 수를 세어주지 않았다.

 

이를 수정한 코드를 아래와 같이 작성하였다.

import sys

class Graph:

    def __init__(self, vertex_num=None):
        self.adj_list = []
        self.vtx_num = 0
        self.vtx_arr = []
        if vertex_num:
            self.vtx_num = vertex_num
        self.vtx_arr = [True for _ in range(self.vtx_num)]
        self.adj_list = [[] for _ in range(self.vtx_num)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)


n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

g = Graph(n)
for _ in range(m):
    l = list(map(int, sys.stdin.readline().strip().split()))
    g.add_edge(l[0] - 1, l[1] - 1)

guest = [0]
for i in g.adj_list[0]:
    if i not in guest:
        guest.append(i)
    for j in g.adj_list[i]:
        if j not in guest:
            guest.append(j)

print(len(guest) - 1)

num of vertices : 7
vertices : {0, 1, 2, 3, 4, 5, 6, }
[0] : {1,  2,  6,  }
[1] : {0,  2,  }
[2] : {0,  3,  1,  }
[3] : {2,  4,  }
[4] : {3,  }
[5] : {}
[6] : {0,  }

guest: [0, 1, 2, 3, 6]

기존에는 2중 for문에서만 친구의 인접리스트를 guest에 추가해주었지만

1중 for문에서도 상근이의 인접리스트를 guest에 추가하도록 하여 발생했던 누락을 수정했다.

 

위 코드로 제출하여 아래와 같이 정답을 얻을 수 있었다.