DHistory

문제 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 기존 topology_sort에서 현재 지을 수 있는 건물의 cost만 넣어주면 된다. 단, 가장 큰 값을 넣어줘야하므로 이전값과 비교하여 큰 값을 넣어준다. import sys from collections import deque t = int(sys.stdin.readline().rstrip()) for _ in range(t): n, m = map(int, sys.stdin.readline().rstrip().split()) cost = [..

문제 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net 풀이 n단 논법이므로, 시작 단계에서 중단 단계를 거쳐 마지막 단계로 지나가는 길을 찾으면 된다. (= floyd warshall) (주의사항) 각 전제는 단방향이다. import sys INF = 1e9 n = int(sys.stdin.readline().rstrip()) distance = [[INF] * 26 for _ in range(26)] for _ in range(n): x, y = sys.stdin.readline().rstrip().split(' is ') # ..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 풀이 기본적인 dijkstra 골격에 추가적인 부분을 신경써주면 된다. 1. 모든 길은 연결되어있다. (모든 정점은 길이가 1인 단방향 간선으로 연결되어 있다.) 2. 지름길의 길이가 주어질 때, 내가 가야할 길이보다 큰 값으로 주어질 수 있다. (list out of index range Error) import sys import heapq INF = 1e9 n, d = map(int, sys.stdin.readline().rstrip().s..

문제 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 import sys INF = 1e9 n, m = map(int, sys.stdin.readline().rstrip().split()) graph = [[INF] * (n + 1) for _ in range(n + 1)] for _ in range(m): a, b = map(int, sys.stdin.readline().rstrip().split()) graph[a][b] = 1 graph[b][a] =..

문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 import sys INF = 1e9 n = int(sys.stdin.readline().rstrip()) graph = [[INF] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): numbers = list(map(int, sys.stdin.readline().rstrip().split())) for index, value in enumerate(numbers): if value: graph[i][index + 1] = 1..