[알고리즘] 백준 1043 - 거짓말

문제

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

풀이

보자마자 그래프 탐색이라는 생각이 들었지만 인덱스를 무엇으로 두고, 어떻게 연결해야할지에 대한 고민이 생겼다. 아무래도 배열 하나로는 안 될 것 같다는 생각이 들었고, 최종적으로는 두 개의 배열을 만들어서 해결했다.

 

내가 사용한 배열은 2가지이다.

1. 인덱스 번호에 해당하는 번호를 가진 사람이 참여한 파티 번호들을 담아두고 있는 배열 ex) [[],[1],[2,3]] 이라고 돼있다면 1번 사람은 1번 파티에 참여한 것이다.

2. 인덱스 번호에 해당하는 번호의 파티에 참여한 사람들 번호를 담아두고 있는 배열 ex) [[],[1,4],[5]] 이라고 돼있다면 1번 파티에 1번,4번의 사람들이 참여한 것이다.

 

결국 이 두 배열은 인덱스와 값의 의미가 서로 바뀐(?) 배열이라고 볼 수 있다. 

 

진실을 알고 있는 사람들을 처음 q에 넣은 후, 1번 배열을 활용해서 해당 사람들이 참여한 파티 번호를 찾고, 해당 파티 번호에 참여한 사람들 번호(이 사람들이 참여하는 다른 파티에서도 지민이는 거짓말을 할 수 없다고 판단하기 위해서)를 찾아서 q에 해당 사람들의 번호를 넣는다. 그 이후에 또 그 사람들이 참여한 파티와 해당 파티에 참여한 사람들 번호를 찾는 방식으로... ~ 문제를 해결했다.

 

진실을 알고 있는 사람들이 참여한 파티는 visited를 1로 바꾸어 주었다.

 

 

정답 코드

pypy로 돌렸다.

from collections import deque
n, m = map(int,input().split())
know_p = list(map(int,input().split()))

# 인덱스 번호 사람이 참여한 파티 번호 배열
party = [[] for _ in range(n+1)]

# 인덱스 파티 번호에 참여한 사람들
party_p = [[] for _ in range(m)]

# 진실을 알고 있는 사람이 참여한 파티는 1로 표시
visited = [0 for _ in range(m)]

for i in range(m):
    p = list(map(int,input().split()))
    for j in p[1:]:
        party[j].append(i)
        party_p[i].append(j)

if know_p[0] == 0:
    print(m)
    exit(0)

q = deque(know_p[1:])

while q:
    c = q.pop()
    for a in party[c]:
        for p in party_p[a]:
            if p!=c and visited[a] == 0:
                q.append(p)

        visited[a] = 1


print(visited.count(0))

 

 

그 외

https://ku-hug.tistory.com/148

[Python/파이썬] 백준 1043번: 거짓말

이런 풀이가 있던데 훨씬 간단해보이고 논리가 명확하게 보여서 좋았다... 내 풀이는 너무 구구절절이라서 흠