문제 설명
당신은 소셜 네트워크의 사용자 관계를 파악하는 프로그램을 개발해야 합니다.
주어진 사용자들의 친구 관계를 토대로 다음 두 가지 요청에 대한 답을 제공하는 프로그램을 작성해야 합니다.
- 주어진 사용자 A의 친구 목록을 출력하라.
- 주어진 사용자 A와 B가 친구인지 여부를 확인하라.
입력 형식
첫 번째 줄에 사용자 수 N과 친구 관계의 수 M이 주어집니다. (1 ≤ N ≤ 100,000, 0 ≤ M ≤ 1,000,000)
다음 M줄에 걸쳐 각 줄마다 두 개의 정수 A와 B가 주어지며 이는 A가 B의 친구라는 것을 의미합니다.
출력 형식
첫 번째 줄에 사용자 A의 친구 목록을 오름차순으로 출력하라.
두 번째 줄에 ‘YES’ 또는 ‘NO’로 사용자 A와 B의 친구 여부를 출력하라.
예제
입력 예시:
5 4
1 2
1 3
2 4
3 5
1
2
출력 예시:
2 3
NO
접근 방식
이 문제를 풀기 위해서는 친구 관계를 효율적으로 저장하고 조회해야 합니다.
그래프 이론을 활용하여 인접 리스트 또는 집합(set) 자료구조를 사용할 수 있습니다.
먼저 사용자들과 친구 관계 정보를 저장하기 위해 빈 리스트를 초기화합니다.
그 후, 각 친구 관계를 입력받아 해당 정보를 저장합니다.
친구 목록을 정렬하여 출력하고, 친구 관계 확인 요청에 대한 응답도 제공합니다.
소스 코드
def manage_friendship(n, m, friendships, a, b):
friends = {i: set() for i in range(1, n + 1)}
for x, y in friendships:
friends[x].add(y)
friends[y].add(x)
friend_list = sorted(friends[a])
is_friend = "YES" if b in friends[a] else "NO"
return friend_list, is_friend
# 입력 처리
n, m = map(int, input().split())
friendships = [tuple(map(int, input().split())) for _ in range(m)]
a = int(input())
b = int(input())
# 친구 관계 관리
friend_list, is_friend = manage_friendship(n, m, friendships, a, b)
# 결과 출력
print(" ".join(map(str, friend_list)))
print(is_friend)
결론
이 알고리즘 문제는 데이터 구조와 알고리즘의 기본적인 이해를 바탕으로 친구 관계를 효율적으로 관리하고
조회하는 방법을 요구합니다.
실제 소프트웨어 개발에서도 이러한 형태의 데이터 관계를 처리하는 것이 주문제작 또는 소셜 네트워크와 같은
플랫폼 개발에 자주 등장하므로, 이러한 문제를 해결하는 방법을 익히는 것은 매우 유용합니다.
부록
친구 관계와 같은 많은 그래프 문제는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)와 같은 탐색 알고리즘을 통해
더 확장된 문제로 발전할 수 있습니다.
이 문제를 바탕으로 그러한 심화 문제에도 도전해 보길 바랍니다.