김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1043 거짓말 파이썬(Python)

문제 링크

상당히 재미있는 문제였다.
처음에 문제를 봤을 때는 어떻게 풀까 생각하다가, 사람을 노드, 같은 파티에 참여했는지를 엣지로 하는 그래프를 그린 후에, 같은 연결 요소에 속한 노드들은 참, 거짓에 대한 진리값을 공유해야 한다는 걸 생각해서 풀어냈다.
DFS에 기반한 풀이인데, 정해(正解)는 유니온 파인드 알고리즘을 활용하는 것으로 보인다.

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
t, *knows = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
parties = []
ans = 0
for _ in range(m):
    p, *party = map(int, input().split())
    
    # 추후에 사용하기 위해 파티들의 집합에 보관
    parties.append(party)
    
    # 그래프의 엣지를 긋는 과정
    for i in range(p-1):
        graph[party[i]].append(party[i+1])
        graph[party[i+1]].append(party[i])

# 평범한 DFS 구현
def dfs(node):
    if not visited[node]:
        visited[node] = 1
        for e in graph[node]:
            dfs(e)

# 진실을 아는 사람들로부터 DFS를 실행한다.
# visited가 1이라면 진실을 아는 사람이라는 뜻
for know in knows:
    dfs(know)

# 각 파티에서, 파티의 사람들이 모두 진실을 모른다면 거짓말을 해도 된다.
# 사실 모든 사람들을 확인할 필요 없이 아무나 한 명만 뽑아서 확인해도 되긴 한다.
for party in parties:
    if all(not visited[man] for man in party):
        ans += 1
print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑