[백준] 1043번 : 거짓말 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1043번: 거짓말

 

1. 문제 설명

2. 풀이과정

해당 문제의 핵심은 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결하는 것이다.

해당 과정을 수행하게 되면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 가리키게 된다.

이후 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인하여 과장된 이야기를 할 수 있는지 판별한다.

 

우선 진실을 아는 사람의 데이터, 파티 데이터, 유니온 파인드 연산을 위한 대표 노드 자료구조를 생성 및 초기화한다.

진실을 아는 사람의 데이터와 대표 노드 자료구조는 1차원 리스트로 생성하고, 파티 데이터는 2차원 리스트로 생성하여 각 파티별 정보를 행마다 저장한다.

각 파티별 사람의 정보를 이용해 union 연산을 수행하여 파티에 참여한 사람들을 1개의 그룹으로 만든다.

이후 find 연산을 수행하여 각 파티의 대표 노드와 진실을 아는 사람들이 같은 그룹에 있는지 확인한다.

해당 과정은 각 파티별 진실을 아는 사람 수만큼 수행해야 하며, 진실을 아는 모든 사람이 해당 파티와 다른 그룹에 있다면 해당 파티에서는 과장된 이야기를 할 수 있다.

 

슈도코드

1. N(사람 수), M(파티 수) 입력받기
2. True_person(진실을 아는 사람의 데이터) 입력받기
3. num(대표 노드 자료구조) 생성 및 초기화
4. union 연산 union(i, j):
   1. if (i와 j의 대표 노드가 다르면): 두 원소의 대표 노드끼리 연결
5. find 연산 find(i):
   1. if (i가 대표 노드이면): i 반환
   2. else:
      1. i의 대표 노드 값을 find(num[i]) 값으로 저장 (재귀 함수 형태)
      2. i의 대표 노드 값 반환
6. party_info(파티 데이터 저장) 생성
7. for M만큼 반복:
   1. party_person(각 파티의 사람 정보) 입력받기
   2. party_person[0] 정보는 사람의 수이므로 제거
   3. party_info에 party_person 정보 추가
8. for M만큼 반복:
   1. first(각 파티의 첫 번째 사람, 기준)
   2. for j를 i번째 파티의 사람 수만큼 반복: union(first, 해당 파티의 사람) 수행
9. result(결괏값 변수) 초기화
10. for M만큼 반복:
    1. possible(과장된 이야기를 할 수 있는지 판별할 변수)
    2. first(각 파티의 첫 번째 사람, 기준)
    3. for j는 진실을 아는 사람들의 수만큼 반복:
       1. if (각 파티의 대표 노드와 진실을 아는 사람의 대표 노드가 같으면):
          1. possible = False(과장할 수 없음)
          2. break(판별 종료)
    4. if (과장할 수 있는 경우): 결괏값 1 증가
11. 결괏값 출력

반응형

3. 소스코드

import sys

N, M = map(int, sys.stdin.readline().split())
True_person = list(map(int, sys.stdin.readline().split()))

num = list(i for i in range(N + 1))

def union(i, j):
    if (find(i) != find(j)):
        num[find(j)] = find(i)

def find(i):
    if (i == num[i]):
        return i
    else:
        num[i] = find(num[i])
        return num[i]

party_info = []
for _ in range(M):
    party_person = list(map(int, sys.stdin.readline().split()))
    del party_person[0]
    party_info.append(party_person)

for i in range(M):
    first = party_info[i][0]
    for j in range(1, len(party_info[i])):
        union(first, party_info[i][j])

result = 0
for i in range(M):
    possible = True
    first = party_info[i][0]

    for j in range(1, len(True_person)):
        if (find(first) == find(True_person[j])):
            possible = False
            break

    if (possible):
        result += 1

print(result)