공부공간

www.acmicpc.net/problem/10282 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 www.acmicpc.net 해킹당하는 컴퓨터의 개수와 시간을 구하기위해 다익스트라 알고리즘을 사용한다. 컴퓨터의 개수는 다익스트라알고리즘을 돌면서 만나는 노드의 개수이고, 시간은 다익스트라로 구한 최단경로중 길이가 가장 큰 것이다. 반례로, 아무컴퓨터와 연결되어있지 않은경우, 1대만 감염되어야 한다. 시간은 0초 import java.io.BufferedReader; import java.io.Input..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름을 구하는 알고리즘(?)은 특정점 ( 아무점 ) 에서 가장 먼 하나의 노드를 선택하고 그 노드에서 가장 먼점을 선택하면 된다. ( 증명은 생략 ) 최장거리계산을 위해, 다익스트라 알고리즘을 사용하여서 각 노드까지의 최단거리 중 큰값을 찾고, 그 노드부터 다시 최단거리중 최장거리를 찾는다. import java.io.BufferedReader; import java.io.InputStream..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존� www.acmicpc.net 특정한 노드 V1,V2를 꼭 지나야하기때문에 1->V1->V2->N의 경우의 수와 1->V2->V1->N의 경우의 수를 모두 구해서 비교한다음 정답을 구해야한다. 다익스트라 알고리즘만 알고있다면, 쉽게 풀리는 문제입니다. import java.io.BufferedReader; import java.io.InputStreamReader; import j..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 1,1에서 N,M으로 벽을 최단개수로 부수면서 진행할 때에 몇개의 벽을 부수어야하는지 체크해주는 문제이다. 우선순위큐에 현재좌표와 몇개의 벽을 부수고 왔는지 체크해주면서 벽의 개수가 적은 순으로 정렬시킨다. 방문체크를 해주면서 1,1에서 N,M까지 진행시킨다. 4분탐색시에 갈곳이 1 이면 한개의 벽을 부수어야하므로 현재의 BR..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net Dijkstra알고리즘의 기본적인 형태이다. 특정 A번째에서 B번째까지의 최단 경로를 구하기위해서 정수배열에 A번째에서 각 인덱스..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicpc.net 한 노드에서 모든 노드까지의 최단거리를 구할때 벨만포드 알고리즘O(간선개수 * 노드개수 ) 이나 간선이 모두 양수인경우 다익스트라O((간선..