본문 바로가기

다익스트라

 (20)
[백준 / 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] 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] 1800 인터넷 설치 (Java) 문제 출처 : https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 원장선생님이 세미나 실에 인터넷을 설치해주기로 마음을 먹었다. 목표는 N번 컴퓨터가 인터넷에 연결되는것이다. 나머지 컴퓨터는 연결이 안되어있어도 된다. 인터넷을 설치하는데 일정 비용이들며, P개의 인터넷 선이 있고, 이중 K개를 무료로 설치할수있을때, 인터넷을 설치하는 최소 비용을 구하는 문제다. (설치비용은 설치된 인터넷선중 가장 비싼 것에..
[백준 / BOJ] 1445 일요일 아침의 데이트 (Java) 문제 출처 : https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 형택이는 여자친구와 데이트를 하려고한다. 자신의 여자친구는 쓰레기를 지나가는것과, 쓰레기 주위를 지나가는것을 굉장히 싫어하기 때문에, 형택이는 이러한 상황을 최대한 피하고자한다. 숲의 크기 n,m 쓰레기의 위치(g), 형택이의 위치(S), 도착위치(F)가 주어진다. 이때, 위와 같은 상황을 최소화 하여 움직였을때 쓰레기를 지나간 횟수와 쓰레기 주위를 지나..
[백준 / BOJ] 9376 탈옥 문제 출처 : https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 상근이는 감옥에서 죄수 두명을 탈옥시킬려고한다. N*M크기의 감옥이있고, 감옥은 # : 문 . : 빈 공간 $ : 죄수 로 구성되어있으며, 죄수는 항상 2명이다 (문이 있는곳은 지나가기위해 문을 열어야한다.) 모든 죄수를 탈출시키기 위해서 열어야 하는 문의 최솟값을 출력하는 문제였다. 풀이 다익스트라로 풀은 문제다. 처음 문제를보고 그냥 BFS를 돌리면 될것같다고 생각했는데, 한 죄수가 밖으로 ..

티스토리툴바