본문 바로가기

Problem Solving/Baekjoon1321

[백준] 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.
[백준] 17089 세 친구 - Brute Force / Java • 문제 링크 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net • 풀이 과정 각각의 인원을 노드로 정의하고 각 노드간 무향 그래프 정보를 boolean 배열 map 에 저장하고, 각 노드의 연결 노드의 수, 즉 친구의 수를 저장할 int 배열 cnt 에 입력받은 노드를 인덱스로써 해당 위치에 +1 을 수행한다. 인원 중 세 사람을 선택하므로 3중 for 문으로 조합을 구할 수 있으며, 선택된 세 사람이 모두 친구일 경우, 해당 인원의 친구 수를 모두 더하고 선택된 나머.. 2022. 8. 11.

티스토리툴바