052 거짓말

첫번째 코드

 

유니온 파인드는 이해가 되고, 코드로 함수를 어떻게 작성해야 할지는 익숙해지지만

문제 해결 능력이나 루프의 원리가 아직 헷갈린다.

 

그래서 코드는 책을 참고했다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

true = list(map(int, input().split()))
T = true.pop(0)

party = [[] for _ in range(m)]
for i in range(m):
    party[i] = list(map(int, input().split()))
    del party[i][0]

parent = [0] * (n+1)
for i in range(n+1):
    parent[i] = i

answer = 0

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(a)
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[b] = a

def checksame(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return True
    else:
        return False

for i in range(m):
    firstperson = party[i][0]
    for j in range(1, len(party[i])):
        union(firstperson, party[i][j])

for i in range(m):
    firstperson = party[i][0]
    talk = True
    for j in range(T):
        if find(firstperson) == find(true[j]):
            talk = False
            break
    if talk:
        answer += 1

print(answer)

 

오류 해결중

---

두번째 코드

 

다음에 다시 풀어본 코드로 책의 코드를 거의 참고하지 않고 풀어나갔다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

true = list(map(int, input().split()))
T = true.pop(0)

party = [[] for _ in range(m)]
for i in range(m):
    party[i] = list(map(int, input().split()))
    del party[i][0]

parent = [0] * (n+1)
for i in range(n+1):
    parent[i] = i

answer = 0

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[b] = a

def checksame(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return True
    else:
        return False

for i in range(m):
    firstperson = party[i][0]
    for j in range(1, len(party[i])):
        union(firstperson, party[i][j])

for i in range(m):
    firstperson = party[i][0]
    talk = True
    for j in range(T):
        if find(firstperson) == find(true[j]):
            talk = False
            break
    if talk:
        answer += 1

print(answer)

 

통과!

이전에 있었던 오류는 find 함수에서 잘못 작성했다.

이해가 된 부분은 공통된 부분을 계속 찾아나가는 것이다.

 

간단히는 아니지만... 생각해보면 아래와 같다.

1. 각 파티에 그룹을 지은 다음

2. true와의 그룹을 확인하여

3. 같은 경우 말을 하면 안되고 같지 않은 경우 말해도 된다.

 

이를 확인하기 위해 union-find를 이용하여 2개를 비교한다고 생각하면 된다.

1. 각 파티 내 union-find

2. 1에서 만든 union-find와 true값 비교

 

그리고 셀 수 있는 파티의 수를 센 후 정답을 구한다.

 

어렵다고 생각했는데, 생각보다 가벼운 원리였다.

유니온 파인드는 union-find 관련된 코드를 암기하고 있으면 좋을 것 같고,

유니온 파인드 문제구나! 라는 아이디어가 생각나면 풀어나갈 수 있을 것 같다는 자신감이...

한창 유니온 파인드 문제를  푸는 지금은 든다 ^^ㅋㅋㅋㅋ

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1043.%E2%80%85%EA%B1%B0%EC%A7%93%EB%A7%90

programmers/백준/Gold/1043. 거짓말 at main · ornni/programmers