본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/벨만포드,다익스트라,MST

 (27)
[백준 / BOJ] 20010 악덕 영주 혜유 (Java) 문제 출처 : https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net N개의 마을과 마을을 연결하는 K개의 간선이 주어진다. 이때, K개의 간선을 이용해서 모든 마을을 연결하는 최소비용과 이때 마을사이를 연결하는 거리의 최댓값을 구하는 문제이다. 풀이 최소스패닝트리 알고리즘과 트리의 지름을 구하는 알고리즘을 각각 사용해서 푸는 문제다. 두 알고리즘을 섞어서 사용할 필요는 없고, "모든 마을을 연결하는 최소비용"을 MST를 이용해서 구한후, MST를 ..
[백준 / BOJ] 20183 골목 대장 호석 - 효율성 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/20183 20183번: 골목 대장 호석 - 효율성 2 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 교차로 N개 교차로를 잇는 골목 M개(단, 골목에는 통행료가 존재한다.)가 주어진다. A교차로에서 B교차로로 갈때, 이 경로의 통행료 합을 C 이하로 만드는 경로중 통행료의 최댓값을 최소로 하는 경로를 구하는 문제다 풀이 전형적인 다익스트라 알고리즘으로 풀리는 문제였다. 알고리즘은 다익스트라를 사용하면 풀리기때문에 따로 설명할게 없고, 최소힙에 ..
[백준 / BOJ] 19538 루머 문제 출처 : https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net N명이 사람이 있다. 이 N명의 사람은 어떠한 루머를 자신과 연관된 주변인중 절반이상이 믿는다면 자신또한 그 루머 믿는다. 이때, 모든 사람이 루머를 믿기위해서 걸리는 시간을 구하는 프로그램을 구하는 문제다. 충분히 많은 시간이 지나도 루머를 믿지 않을 경우 -1을 출력하면된다. 소스코드 기본적인 다익스트라 문제였다. 각 사람이 루머를 믿기시작..
[백준 / BOJ] 17182 우주 탐사선 (완전탐색) 문제 출처 : https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 우주탐사선 ans호가 있다. ans호는 N개의 행성을 모두 탐사하는데 걸리는 최소시간을 계산하려한다. N개의 행성끼리 이동하는데 걸리는 시간이 주어질때 모든 행성을 탐사하기 위한 최소 시간을 출력하는 문제다. 풀이 플로이드 와샬로 최단경로를 만들어주고, 비트마스킹을 이용한 완전탐색으로 답을 찾은 문제다. (거의 3달만의 플로이드 와샬이라 알고리즘조차 가물 가물했다..) N이 최..
[백준 / BOJ] 16137 견우와 직녀 문제 출처 : https://www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 견우와 직녀는 여러 섬과 절벽으로 이루어진 크기 N*N 지역에 살고있다. 견우는 0,0에, 직녀는 N,N에 살고있다. 까치들은 견우와 직녀를 만나게해주기위해서, 오작교를 만드는데, 오작교는 T주기마다 생성되며, 1분동안 유지된다. 견우는 오작교를 2번이상 연속적으로 건널수없으며, 추가적으로 임의의 절벽에 다리를 하나 생성해서 건널수있다. 단, 다리를 생성할때, 교차로에는 짓지못하..
[백준 / BOJ] 1854 K번째 최단경로 찾기 문제 출처 : https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net n개의 도시, m개의 길, k가 주어진다. 김 조교가 1번째 도시에서 출발한다 했을때, 1번부터 n번도시까지 k번째 최단경로를 구하는 문제다. 풀이 다익스트라로 푸는 문제다. k가 100으로 크지않아서, n번째 도시에 k번째 도착하는 모든 경로를 찾아서 구해주면된다. 로직 1. 1번도시에서 다익스트라를 시작한다. 2. 최단경로..
[백준 / BOJ] 5719 거의 최단 경로 (Java) 문제 출처 : https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net N개의 장소와 M개의 도로가 주어진다. (각 도로는 가중치를 갖고있다.) 시작도시 S에서 도착도시 D로 가는 최단경로를 포함하지않는 경로중 가장 빠른 경로를 출력하는 문제다. 풀이 쉬운 문제이해와 그렇지 않은 최적화 과정.. 다익스트라로 푸는 문제였다. 문제가 특이한게, 플래티넘 난이도 임에도 푸는 방법이 굉장히 직관적으로 보인다. 최적화와 경로 추적이..
[백준 / BOJ] 1414 불우이웃돕기 Prim (Java) 문제 출처 : https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net N개의 컴퓨터가 있고, 각 컴퓨터를 연결하는 랜선이 N*N개 주어진다. 다솜이는 자신의 컴퓨터를 최소한의 랜선을 사용해서 연결하고 나머지 랜선을 기부할려고한다. 이때, 다솜이가 기부할수있는 최대 랜선 길이를 구하는 문제다. 풀이 MST문제다. 다솜이가 컴퓨터를 연결하는 과정에서, 연결 순서, 방법등 아무것도 고려하지않고 "최소한의 랜선길이"만 유지하면 되므로 MST로 풀리는 문..

티스토리툴바