1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 분석 임계경로 : 그래프에서 임계경로란 어떤 시작지점으로부터 끝지점까지의 최장경로를 의미 풀이 """ 임계경로 구하기 1분도 쉬지않고 달려야 하는 사람들이 지나는 도로의 수 : 가장 오랜 시간이 걸리는 사람 → 임계경로, 그에 속한 정점구하기 에지 뒤집기 """ import sys from collections import deque input=sys.stdin.readline n=int(input()) # 도시 수 m=int(inpu..

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 """ 위상정렬 학생수 n, 키비교횟수 m 키 비교한 두 학생 번호(1~n) A,B : A가 B 앞에 서야함 """ from collections import deque # 노드(학생수) n, 엣지(키비교횟수) m n,m=map(int,input().split()) # 진입차수리스트 d = [0] * (n+1) # 인접 리스트 a = [[] for _ in range(n+1)] for _ in range(m): s..

1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 분석 [1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙) 다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 karla.tistory.com 그래프 최단거리 알고리즘 정리 및 비교 (다익스트라, 벨만-포드, 플로이드-워셜) 다익스트라 벨만-포드 플로이드-워셜 시작 노드 (시작점) O ..

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 분석 https://www.acmicpc.net/board/view/112226 2가 1에 의해 진실을 알게 되었기 때문에.가 아니라 1번 파티에 지민이가 참석하였을 때, 1번 사람이 있기 때문에 지민이는 진실을 이야기 할 수 밖에 없고, 1번 파티에 참석한 2번 사람은 해당 사실에 대해 알게 되었기 때문에, 다음 파티인 2번에 지민이가 참석 하였기 때문에, 1번 파티에서 진실을 들은 2번이 있기 때문에 지민이는 또 진실을 이야기할 수 밖에 없고, 마지막 파티에 가서도 2..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 분석 [1717번] 집합의 표현 (유니온 파인드) 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현 karla.tistory.com 풀이 """ 유니온파인드 도시 N개 경로 M개 N개의 정수 도시의 연결 정보 마지막 줄 여행 계획 A-B, B-C, A-D, B-D, E-A 여행..

2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 분석 (BFS 과정) 1. 노드에서 갈 수 있는 6개의 경우(A→B, A→C, B→A, B→C, C→A, C→B)에 관해 다음 노드로 정해 큐에 추가 A,B,C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않음 2. 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장 단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남김 3. 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 ..