Coding Test/Graph

1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 풀이 """ N개의 컴퓨터를 모두 서로 연결, 각각의 컴퓨터는 랜선으로 연결 기부할 수 있는 랜선의 길이의 최댓값 컴퓨터의 개수 N(1~50) 랜선의 길이 a~z: 1~26, A~Z: 27~52, (i,j)=0: 랜선이 없음 """ import sys input = sys.stdin.readline from queue import PriorityQueue n=int(input()) #컴퓨터개수 total=0 # 총 랜선 길이 pq = PriorityQueu..

정리 다익스트라 크루스칼 용도 일대다 정점 간의 최소 거리 파악 최소 신장 트리(MST) 파악 중심 정점(Node) 간선(Edge) 모든 정점 방문 X O 구현 방법 우선 순위 큐 + dist[점화식] 우선 순위 큐 + Union-Find 시작점 출발점이 정해져 있는 경우 간선 가중치가 작은 것부터 큐에 넣는 시점 dist가 갱신 될 때 그 점에서 출발하는 간선을 큐에 넣음 모든 정점을 우선순위 큐에 넣고 시작 끝 점과 점 사이의 최단 거리를 찾고 나면 더이상 탐색하지 않음 최소신장 트리가 만들어 질 때까지 탐색 최소 임의의 두 점 간의 최소 거리를 구할 때 사용 최소 비용으로 모든 점을 다 이을 때 사용 임의의 두 점 간의거리 최소 보장 X 최단거리 알고리즘 그래프 최단거리 알고리즘 정리 및 비교 (다..

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

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