본문 바로가기

백준 PS일지/Dijkstra

 (6)
[백준/Swift] 14938: 서강그라운드 | PS일지 문제 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 간단한 문제 요약 여러 지역 중 한 지역에 떨여졌을 때 각 지역에 아이템이 몇 개 있는지 알려주는 프로그램을 개발했다. 하지만 어디로 떨어져야 수색 범위 내에서 많은 아이템을 얻어야 할지는 모른다. 낙하한 지역을 중심으로 수색 범위가 주어진다고 할 때 수색 범위 이내에서 가장 많이 얻을 수 있는 아이템 개수를 구하시오. 고려해야 할 사항 X 문제 풀이, 새로 알게된 것 수색범위는 문제에서 주어집니다. 예은이가 떨어졌을 때의 지점을 시작 정점으로 다익스트라 탐색을 ..
[백준/Swift] 11779: 최소비용 구하기 PS일지 문제 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 간단한 문제 요약 다익스트라 최단 경로 문제입니다! A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시켜야합니다. 이때 A->B까지 갈 때 최소로 드는 비용과 경로를 출력해야한다. 출 -> 도착 지점은 항상 지정되어있다. 고려해야 할 사항 문제를 구현하면서 답은 여러 개가 정답일 수 있습니다. 문제 풀이, 했갈렸던 점 PS 일지 문제를 풀면서 신기했던 점이 있습니다. 예제 입력에 대한 예제 출력의 도시 경로 출..
[백준/Swift] 1504: 특정한 최단 경로 문제 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 간단한 문제 요약 방향성 없는 그래프가 주어진다. 1->N 정점으로 최단 거리로 이동하려고 한다. 이때 문제에서 주어진 임의의 두가지 정점은 반드시 통과해야 한다. 물론 한번 이동했던 정점, 간선을 다시 이동할 수 있다.(최단 경로로 이동한다는 전제하에) 1 -> N까지 최단 경로를 갈 때 반드시 임의의 두 정점 v1, v2를 거쳐 최단 경로를 가는 경로 길이를 출력 해야한다. 고려해야 할 사항 v1 -> v2로..
[백준/Swift] 1261: 알고스팟 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 간단한 문제 요약 시작 (1,1) 탈출 칸 (N,M). 시작 칸에서부터 미로를 탈출해야 한다. 벽이 있는 경우 벽을 부수면서 탈출해야 하는데 벽을 최소한으로 부숴서 탈출 지점까지 도착해야 한다. 문제 풀이, 느낀 점 문제 선정은 다익스트라 파트에서 골랐다. 당연히 힙을 구현했고 힙을 이용해서 풀었다. 한 가지 낯설었던 것은 기존에 다익스트라 문제는 지점을 지날 때 가중치 값이 주어지는데 이 문제는 가중치가 없었다. 그래서 이전에 방문했던 칸..
[백준/Swift] 4482 : 녹색 옷 입은 애가 젤다지? 문제 (링크) 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 간단한 문제 요약 '도둑루피' 라는 검정색 루피를 획득하면 소지한 루피가 감소한다. N*N의 동굴에는 도둑 루피로 가득하다. 젤다는 [0][0]위치에 있고 출구는 맨 아래칸 [N-1][N-1]로 이동해야한다. 동굴의 각 칸은 도둑 루피가 있다. 잃는 금액을 최소로 해서 동굴의 출구로 이동해야 한다. 한번에 한 칸 이동할 수 있다. 고려해야 할 사항 도둑 루피 크기가 K인 특정 칸을 지나면 K루피를 잃는 다는 뜻 시작점 [0][0]..
[백준/Swift] 1238 : 파티/ 우선순위 큐 개념 정리, 최소 힙 개념 with 라이노님 Heap 정리 문제 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 간단한 문제 요약 각 마을에는 한명의 학생이 살고 있습니다. n명의 학생은 x번 마을에 모여 파티를 합니다. 이때 m개의 도로는 단 방향입니다. i 비용을 들여 도로를 지나갑니다. 고려해야 할 사항 N, M, X 입력은 1 부터입니다.. (X제약을 못봐서 계속 X위치를 다르게 구했다는..ㅠㅠ) 문제 풀이, 했갈렸던 점 x번을 제외한 마을 학생들은 각자가 갈 수있는 모든 마을에 대해 최단 경로를 구한 후 x일때의 최단 경로를 저..

티스토리툴바