BOJ(백준) 5567[결혼식]

이번 글에서는 백준 5567번 문제인 “결혼식”을 함께 해결해 보겠습니다. 이 문제는 상근이의 결혼식에 초대할 친구와 친구의 친구를 찾는 문제입니다.

 

문제 URL : https://www.acmicpc.net/problem/5567

 

1. 문제 설명

1) 문제 개요

• 상근이의 결혼식에 초대할 사람들을 찾는 문제입니다.

• 상근이의 친구와 친구의 친구를 결혼식에 초대해야 합니다.

 

2) 입력

• 첫 번째 줄에 사람의 수 n이 주어집니다. (1 ≤ n ≤ 500)

• 두 번째 줄에 친구 관계의 수 m이 주어집니다. (0 ≤ m ≤ 10000)

• 다음 m개의 줄에 친구 관계를 나타내는 두 정수 a와 b가 주어집니다. (1 ≤ a, b ≤ n, a ≠ b)

 

3) 출력

• 상근이의 결혼식에 초대할 사람의 수를 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 사람의 수 n을 입력받습니다.

• 두 번째 줄에서 친구 관계의 수 m을 입력받습니다.

• 다음 m개의 줄에서 친구 관계를 나타내는 두 정수 a와 b를 입력받습니다.

 

2) 친구 관계 저장

• 인접 리스트를 사용하여 각 사람마다 친구 목록을 저장합니다.

 

3) 상근이의 친구와 친구의 친구 찾기

• 상근이의 친구 목록을 배열 f1에 저장합니다.

• 상근이 친구의 친구 목록을 배열 f2에 저장합니다.

• 상근이의 친구와 친구의 친구의 수를 더하여 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력받기
n = int(input())  # n: 사람의 수 (상근이 포함)
m = int(input())  # m: 친구 관계의 수
adj = [[] for _ in range(n)]  # 인접 리스트 생성 (각 사람마다 친구 목록)

f1 = [0] * n  # 상근이의 친구 목록
f2 = [0] * n  # 상근이 친구의 친구 목록

# 친구 관계 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    adj[a-1].append(b-1)  # 인접 리스트에 친구 추가 (0-indexed)
    adj[b-1].append(a-1)  # 양방향 관계이므로 양쪽에 추가

# 상근이의 친구 찾기
for i in adj[0]:  # 상근이의 친구들을 순회
    f1[i] = 1  # 친구로 표시

# 상근이 친구의 친구 찾기
for i in range(n):
    if f1[i] != 1:  # 상근이의 친구가 아니면 무시
        continue
    
    for j in adj[i]:  # 상근이 친구의 친구들을 순회
        if j != 0 and f1[j] == 0:  # 상근이 본인이 아니고, 이미 친구로 표시된 적이 없으면
            f2[j] = 1  # 친구의 친구로 표시

# 상근이의 친구와 친구의 친구의 수를 더하여 출력
print(sum(f1) + sum(f2))

 

4. 코드 설명

1) 입력 받기

• 첫째 줄에서 사람의 수 n을 입력받습니다.

• 둘째 줄에서 친구 관계의 수 m을 입력받습니다.

• 다음 m개의 줄에서 친구 관계를 나타내는 두 정수 a와 b를 입력받습니다.

 

2) 친구 관계 저장

• 인접 리스트를 사용하여 각 사람마다 친구 목록을 저장합니다.

 

3) 예시와 시각적 설명

예시

예를 들어, 입력이 다음과 같다고 가정하겠습니다.

 

n = 6

m = 5

친구 관계:

1 2

1 3

2 3

2 4

3 5

 

친구 관계를 시각적으로 표현하면 다음과 같습니다

1 - 2

|  \

3  4

|  

5  

 

풀이 과정

1] 상근이의 친구 찾기

• 1번 사람의 친구는 2번과 3번입니다. 따라서 f1 배열은 [0, 1, 1, 0, 0, 0]가 됩니다.

 

2] 상근이 친구의 친구 찾기

• 2번 사람의 친구: 1, 3, 4

• 3번 사람의 친구: 1, 2, 5

• 이미 상근이의 친구인 1번, 2번, 3번을 제외하고 친구의 친구 목록은 4번과 5번이 됩니다. 따라서 f2 배열은 [0, 0, 0, 1, 1, 0]가 됩니다.

 

3] 결과 출력

• 상근이의 친구와 친구의 친구의 수는 sum(f1) + sum(f2)입니다.

• 이 경우 2 + 2 = 4이므로, 결혼식에 초대할 사람의 수는 4명입니다.

 

시간 복잡도

이 문제의 시간 복잡도는 주어진 입력에 따라 다음과 같이 계산할 수 있습니다

 

1. 입력받기 및 인접 리스트 생성

• 사람의 수 n과 친구 관계의 수 m에 대해, 인접 리스트를 생성하고 관계를 추가하는 데 걸리는 시간은 O(m)입니다.

 

2. 상근이의 친구 찾기

• 상근이의 친구를 찾기 위해 상근이의 친구 목록을 순회하는 데 걸리는 시간은 O(n)입니다.

 

3. 상근이 친구의 친구 찾기

• 각 상근이의 친구에 대해 친구의 친구를 찾는 과정에서 각 친구 목록을 순회합니다. 이때 최악의 경우 모든 친구를 순회하게 되므로 O(n)입니다.

 

따라서, 전체 시간 복잡도는 O(m + n)입니다. 이는 사람의 수와 친구 관계의 수에 비례하여 선형적으로 증가합니다.

5. Github으로 확인

 

coTest/BOJ/BOJ01_07_05_5567.py at main · pcy4196/coTest