개발하는 고라니

12763번: 지각하면 안 돼 1호관에서 3호관, 4호관을 거쳐 5호관으로 간다면, 3시간만에 3500원의 지출로 도착할 수 있다. (다행히 이번 수업은 휴강이었다고 합니다.) www.acmicpc.net [Dijkstra + DFS] N개의 정점을 탐색하는 것에서 그래프 문제임을 유추할 수 있고, 조건이 주어지며 최소한의 값으로 목표 정점에 도착하는 것을 구하는 것에서 최단경로 문제임을 유추할 수 있다. 그저 그런 다익스트라 문제인줄 알고 여유롭게 풀었지만 85% 쯤 오답판정을 받았다. 이럴리가 없는데..하면서 몇 번을 다시 제출했지만 여전히 오답이었다. 틀린 이유에 대한 해답은 질문 게시판에서 찾을 수 있었다. 링크 : https://www.acmicpc.net/board/view/37703#post..

16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [Dijkstra] BFS로 풀어보았으나 풀다보니 다익스트라 알고리즘이 더 풀기 쉬울 것 같아서 급히 방향을 바꾸어서 풀었다. map[ ]이라는 배열을 만들어서 i번 째 원소의 값은 i로 초기화한다. 그리고 n, m만큼 뱀과 사다리의 정보를 받아 해당 map[ i ]의 값을 바꾸고 다익스트라 알고리즘을 수행하면 된다. # Code import java.io.BufferedReader; import java.io.IOE..

14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1

10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net [Dijkstra] 이 문제의 정점은 n+2개다. 출발점, 도착점, 그리고 n개의 대포들. 다음과 같은 주의사항을 지닌다. 1) 출발점/도착점은 인간 대포를 사용할 수 없다. 2) 한 정점에서 다른 정점으로 갈 수 있는 방법은 오직 걸음으로만 가거나, (인간 대포 + 걸음)을 이용하는 방법이 있다. (단, 출발점/도착점은 제외) 3) 대포를 사용할 시, 거리가 50 이상일 때와, 50 미만일 때를 고려해야한다. 나는 정점에 대한 클래스와 간선에 대한 클래스..

13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net [Floyd-Warshall or 다익스트라] 나는 플로이드-와샬로 풀었으나, 다익스트라로 푸는 것이 어쩌면 더 적은 시간이 들지도 모르겠다. 다익스트라를 사용한다면 k번의 다익스트라를 수행하게 되니까 말이다. 일반적인 플로이드 와샬 문제처럼 거리의 대한 배열 dist를 i == j일때는 0으로, 아닐때는 INF로 초기화 해놓고, 입력에 따라 dist에 값을 대입한다. for(int i=1; i

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 모든 정점에 대하여 다른 정점으로의 최단 경로를 구하는 문제이므로 n * Djikstra / Floyd Warshall을 사용할 수 있겠다. [Dijkstra] # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static class Edge implements Compa..

1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net [Dijkstra / Floyd Warshall] 모든 정점에서 다른 모든 정점에 대한 최단 경로를 구하는 문제이므로 다익스트라를 이용하거나, 플로이드 와샬을 이용해도 무방할 듯 하다. 나는 N x M개의 모든 정점에 대해 다익스트라 알고리즘을 수행하였다. 우선 map이 알파벳으로 주어지는데, 각 알파벳은 그에 맞는 높이를 정수형으로 가진다. 따라서 map을 저장할 때 char가 아닌 int로 변환해서 저장하였다. for(int i=1; i

10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [Floyd Warshall (플로이드 와샬)] 일반적인 플로이드 와샬 알고리즘으로 모든 정점에서 다른 모든 정점으로의 최단 거리를 구한다. 이 때 가볍고 무겁다는 것은 양방향이 아닌 단방향이다. 그러므로 a정점에서 b정점에 대하여 어느 것이 가볍고 무거운지 모르고, 마찬가지로 b정점에서 a정점에 대하여 어느 것이 가볍고 무거운지 모른다면 (distance[a][b] == INF && distance[b][a] == INF) 비교 결과를 ..