알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 10. 그래프 이론 - 팀 결성

  • 0
  • 0
0
0

1. 팀 결성

  • 난이도
  • 풀이 시간
    • 20분
  • 시간 제한
    • 2초
  • 메모리 제한
    • 128MB
  • 기출
    • 핵심 유형

A. 문제

학생에게 0부터 N번까지 번호를 부여했다.
모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다.
팀 합치기 연산과 같은 팀 여부 확인 연산을 사용할 수 있다.

  • 팁 합치기
    • 두 팀을 합치는 연산
  • 같은 팀 여부 확인
    • 특정 두 학생이 같은 팀에 속하는지 확인
a. 입력 조건
  • 첫째줄에 N, M
    • 1 <= N, M <= 100,000
  • 다음 M개 줄에 각각 연산이 주어진다.
    • 팀 합치기는 0 a b (a 학생 팀과 b 학생 팀을 합친다)
    • 같은 팀 여부 확인 1 a b (a학생과 b학생이 같은 팀이지 확인)
      • a, b는 N 이하의 양의 정수
b. 출력 조건

같은 팀 여부 확인 연산에 대해 YES, NO를 한줄씩 출력

c. 테스트 케이스
  • 입력 예시

    
    7 8
    0 1 3
    1 1 7
    0 7 6
    1 7 1
    0 3 7
    0 4 2
    0 1 1
    1 1 1
    
    
  • 출력 예시

    
    NO
    NO
    YES
    
    

B. 내 답안


def find_team(team, x):  
    if team[x] != x:  
        team[x] = find_team(team, team[x])  
    return team[x]  
  
  
def union_team(team, a, b):  
    a = find_team(team, a)  
    b = find_team(team, b)  
  
    if a < b:  
        team[b] = a  
    else:  
        team[a] = b  
  
  
n, m = map(int, input().split())  
  
array = []  
team = [0] * (n + 1)  
  
for i in range(1, n + 1):  
    team[i] = i  
  
for i in range(m):  
    c, a, b = list(map(int, input().split()))  
    array.append([c, a, b])  
  
for i in range(m):  
    c, a, b = array[i]  
  
    if c == 0:  
        union_team(team, a, b)  
    elif c == 1:  
        if find_team(team, a) == find_team(team, b):  
            print("YES")  
        else:  
            print("NO")  
  
# 20분 4초 / Pass / Time out

a. 회고

풀이

  • 팀 합치기와 같은 팀 여부 확인을 보자마자 서로소 집합 알고리즘이 떠올랐다.

반성

  • 구현이 처음이라 시간이 좀 걸렸다.

C. 문제 해설

서로소 집합 알고리즘 문제로 N과 M의 범위가 모두 최대 100,000이다. 따라서 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간 복잡도를 개선해야 한다.

a. 책 답안

python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.