본문 바로가기

전체 글1321

[백준] 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.
[백준] 1766 문제집 - Graph Theory / Java • 문제 링크 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net • 풀이 과정 [백준] 2252 줄 세우기 - Graph Theory / Java • 문제 링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A graycode.tistory.com 위의 문제와 같은 구조로 어떤 문제를 풀기 위하여 선행되어야.. 2022. 8. 13.
[백준] 2252 줄 세우기 - Graph Theory / Java • 문제 링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net • 풀이 과정 어떤 학생보다 키가 크므로 먼저 줄을 서야하는 학생의 수, 즉 외부 노드에서 들어오는 간선의 개수(진입 차수) 를 inDegree 배열에 저장하여 위상 정렬로 풀이한다. 예시로 학생 2 보다 큰 키의 학생 3, 4가 주어질 경우, (4, 2), (3, 2) 의 입력이 주어지고 inDegree[2]++ 가 총 두번 수행되어 inDegree[2] = 2 로 초기화된다. 이 후 학생 i 에 대하여.. 2022. 8. 12.

티스토리툴바