본문 바로가기

Problem Solving1486

[백준] 1916 최소비용 구하기 - Graph Theory / Java • 문제 링크 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net • 풀이 과정 한 노드에서 다른 모든 노드까지의 최단 거리를 구하고, 음의 가중치가 없는 그래프이므로 Dijkstra 알고리즘을 활용한다. 모든 노드까지의 최단 거리를 저장할 dist 배열을 최대값으로 초기화하고, 각각의 간선의 시작점이 인접 리스트의 인덱스로써, 도착점과 가중치를 저장한다. 입력받은 시작점 source를 dijskstra 함수의 매개 변수로 전달하여 실행하고, 우선 순위 큐를 람다식을 통해 가중치.. 2022. 8. 19.
[백준] 1865 웜홀 - Graph Theory / Java • 문제 링크 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net • 풀이 과정 [백준] 11657 타임머신 - Graph Theory / Java • 문제 링크 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000.. graycode.tistory.com 위의 문제와 유사한 벨만 포드 알고리즘 문제이다. 다만 이 문.. 2022. 8. 18.
[백준] 11657 타임머신 - Graph Theory / Java • 문제 링크 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net • 풀이 과정 한 노드(1번 도시)에서 다른 모든 노드(나머지 도시)까지의 최단 거리(최단 시간)를 구하고 타임머신이라는 간선의 가중치가 음수인 경우가 존재하므로 Bellman-Ford 알고리즘을 활용한다. 각 노드의 최단 거리를 dist 배열에 무한대 값(inf) 으로 초기화하고, 각 간선의 출발, 도착점, 가중치의 정보를 Edge 객체로 저장한다. 1번 노드를 출발 노드로 나머지 노드들.. 2022. 8. 17.
[백준] 1197 최소 스패닝 트리 - Graph Theory / Java • 문제 링크 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net • 풀이 과정 [백준] 1922 네트워크 연결 - Graph Theory / Java • 문제 링크 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net • 풀이 과정 그래프(네트워크) 내의 모든 정점(컴퓨터)을 가장 적은 비용 graycode.tistory.com 위 문제와 입력 형식 외에 동일한 문.. 2022. 8. 16.
[백준] 1922 네트워크 연결 - Graph Theory / Java • 문제 링크 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net • 풀이 과정 그래프(네트워크) 내의 모든 정점(컴퓨터)을 가장 적은 비용으로 연결하기 위해 최소 신장 트리(Minimum Spanning Tree) 를 구현해야하며 크루스칼 알고리즘으로 풀이한다. 각 간선의 출발 노드(src), 도착 노드(dest), 가중치(weight) 정보를 포함하는 Edge 클래스를 생성하고, 비용을 최소로 하기 위하여 compareTo 메소드를 오버라이딩하여 간선의 가중치를 오름차순 정렬 기준으로 지정한다. 또한 간선의 각 정점의 부모 노드를 기록하기위하여 parent 배열을 생성, 각 노드 자기 자신을 초기값.. 2022. 8. 15.
[백준] 2056 작업 - Graph Theory / Java • 문제 링크 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net • 풀이 과정 각각의 작업이 수행되기 전에 선행되어야 할 작업의 수를 진입 차수로써 inDegree 배열에, 해당 작업의 소요 시간을 cost 배열에 저장한다. 작업 i 에 대하여 inDegree[i] == 0 인 작업을 큐에 삽입하고 해당 작업 소요 시간을 res 배열에 저장하여 위상 정렬을 수행한다. 현재 작업의 후행 작업들의 inDegree 값을 1씩 감소시키면서 inDegree 가 0 일 경우 큐에 삽입한다. 이때 2개 이상의 선행.. 2022. 8. 14.

티스토리툴바