백준 파이선 python 1717번 / 1976번 / 11675번 타임머신

백준 파이선 python 1717번 집합의 표현

입력
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

Python

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int,input().split())

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


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


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

    if a == b: 
        return
    if a < b: 
        parent[b] = a
    else:
        parent[a] = b

for _ in range(M):
    o, a, b = map(int,input().split()) 
    if o == 0: 
        union(a,b)
    elif o == 1: 
        if find(a) == find(b):
            print('YES')
        else:
            print('NO')

반응형

백준 python 1976번 여행가자

입력
첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력
첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

Python

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
M = int(input()) 
parent = [0] * (N+1) 


for i in range(1, N+1):
    parent[i] = i

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

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

    if a == b:  
        return

    if a < b:  
        parent[b] = a  
    else:  
        parent[a] = b 

for y in range(1, N+1): 
    maps = list(map(int, input().split()))  
    for x in range(1, len(maps)+1):  
        if maps[x-1] == 1:  
            union(y, x)  

tour = list(map(int, input().split())) 
result = set([find(i) for i in tour])  
if len(result) != 1:  
    print('NO')
else:
    print('YES')

 

백준 python 11675번 타임머신

 

입력
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력
만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

Python

import sys
import collections
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())  
edges = []  
dist = [INF] * (n+1) 


for _ in range(m):
    u, v, w = map(int, input().split())  
    edges.append((u, v, w))


def bf(start):
    dist[start] = 0  
    for i in range(n):  
        for j in range(m):  
            node = edges[j][0] 
            next_node = edges[j][1] 
            cost = edges[j][2]  
            
            if dist[node] != INF and dist[next_node] > dist[node] + cost:
                dist[next_node] = dist[node] + cost
                 
                if i == n-1:  
                    return True
    return False


negative_cycle = bf(1)

if negative_cycle:
    print('-1')
else:
    
    for i in range(2, n+1):
        if dist[i] == INF: 
            print('-1')
        else: 
            print(dist[i])