Coding Test/Graph

[11403] 경로 찾기 (플로이드-워셜)

11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 최단거리를 구하는 문제가 아니기 때문에 플로이드-워셜 알고리즘에서 업데이트 부분 수정 S와 E가 모든 중간 경로(K) 중 1개라도 연결되어 있다면 S와 E는 연결 노드로 저장 풀이 """ 모든 정점 (i,j) i에서 j로 가는 경로가 있는지 없는지 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력 """ import sys # 인접행렬 크기 n = int(input()) # 인접행렬 d = array = [[sys.maxsize for j in range(n)] f..

[1389] 케빈 베이컨의 6단계 법칙 (플로이드-워셜)

1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 분석 2023.03.21 - [Algorithm/Graph] - [11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드) 풀이 """ 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산 케빈 베이컨의 수가 가장 작은 사람 구하기 유저수 N(2~100), 친구관계수 M(1~5,000) 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다 """ import sys ..

[17472] 다리 만들기2 (BFS, MST)

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 분석 주어진 지도에서 섬으로 표현된 값을 각각의 섬마다 다르게 표현 지도의 정보를 2차원 리스트에 저장하고 섬으로 표시된 모든 점에서 BFS를 실행해 섬을 구분 섬의 모든 위치에서 다른섬으로 연결할 수 있는 에지가 있는지 확인해 에지 리스트 만들기 다리를 지어 다른 섬으로 연결 할 수 있는지 확인 연결할 곳이 현재 섬이면 탐색 중단, 바다라면 계속 수행 다른 섬을 만났을 때 다리의 길이가 2 이상이면 에지 리스트에 추가 MST 에지를 오름차순..

[1219] 오민식의 고민(변형 벨만-포드)

1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 벨만-포드 알고리즘 특정 출발 노드에서 다른 모든 노드까지의 최단경로 검색 음수 가중치 존재 음수 싸이클 존재 여부 판단 2023.03.20 - [Algorithm/Graph] - [11657번] 타임머신 (그래프, 최단거리, 벨만 포드 알고리즘) 수행과정 모든 에지와 관련된 정보를 가져와 다음 조건에 따라 거리 리스트의 값 업데이트 출발 노드가 방문한 적이 없는 노드(출발 노드 거리 == INF) 일 때 업데이트 X 출발 노드의 거리 리스트 값 + 에지 가..

[1948] 임계경로(위상정렬, 에지 뒤집기)

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] 줄 세우기(위상정렬)

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] 최소비용구하기 (다익스트라)

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

[1043] 거짓말 (유니온파인드)

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

[1976] 여행 가자(여행 계획, 유니온 파인드)

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] 물의 양 구하기 (물통, BFS)

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일 때가 있으면 ..