겜돌이의 개발일지

문제 백준 5972 택배 배송 C++ 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 문제 설명이 애매하게 되어있는데, 하나 이상의 길로 연결되어 있을 수 있다는 점이 거슬렸다. 시작, 끝 점은 똑같은데 비용이 다른 간선을 말한다기보다는 다른 점으로 우회하여 갈 수 있다고 받아들였다. 풀이는 일반적인 다익스트라 문제 해법을 사용해 해결해주면 된다. 우선 순위 큐를 사용하여 시작 점부터 간선 정보를 갱신해 주고, N까지 가는 비용을 출력한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

개요 다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서, 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제이다. 알고리즘의 단계는 다음과 같다. 1. F는 공집합으로 둔다. 2. Y(최단 경로가 확정된 집합)에는 시작 정점 v1을 포함해 {v1}으로 둔다. 3. 최종해답을 얻을 때까지 다음 과정을 반복한다. (a) 선정 절차 / 적정성 점검 : V-Y에 속한 정점 중에서, v1에서 Y에 속한 정점만을 거쳐서 최단 경로가 되는 v를 선정한다. (b) v를 F에 추가한다. (c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가한다. (d) 해답 점검 : Y = V가 되면 T = (V, F)가 최단경로를 나타내는 그래프가 된다. 예시 초기화 : v1에서 v2~v5까지의 최단 거리를..

문제 백준 4485 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 처음에 오른쪽, 아래쪽으로만 이동 가능한 줄 알고, 'DP로 쉽게 풀리겠네'라고 잘못 생각했다. 상하좌우 이동이 모두 가능하기 때문에 다익스트라로 해결해야 한다. struct 타입을 새로 정의하고 우선순위 큐에 넣으면 비교가 불가하기 때문에 에러가 발생한다. 오퍼레이터를 정의해줘서, 오름차순으로 PQ에 들어가게 해 주었다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

문제 백준 1504 특정한 최단 경로 C++ 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 다익스트라를 사용합니다. 정점 v1, v2를 지나고 1부터 시작해서 N에서 끝나는 경로는 다음 2가지 중 하나입니다. 1) 1 -> v1 -> v2 -> N 2) 1 -> v2 -> v1 -> N 따라서 다익스트라를 3번 사용하여 각각의 최소거리를 구해주고 1)과 2)중 최솟값이 정답이 됩니다. 1), 2)의 경로로 모두 도달이 불가능 할 때 (INF일 때)는 -1을 ..

문제 백준 1261 알고스팟 C++ 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 1. 시작점부터 bfs를 실행하여 목적지까지 도달하는 경로를 찾습니다. 2-1. 목적지에 도달하지 못했다면, 이번 bfs를 실행하는 동안 만난 벽(1)들을 빈 방(0)으로 바꿔줍니다. 2-2. 목적지에 도달했다면, 지금까지 실행했던 bfs 횟수 - 1을 출력합니다. 3. 목적지에 도달할 수 있을 때까지 1 ~ 2 과정을 반복합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..