개발하는 고라니

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..

코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr [Dijkstra] 1번 정점에서 모든 정점까지의 최단 거리를 구해 dist[ ]에 저장 후, 1번 정점부터 n번 정점까지 dist[i]를 돌면서 dist[i]가 max인 곳의 정점 개수를 카운팅 한다. # Code import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; class Solution { static class Edge{ int tg, d; public Edge(int target, i..

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

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

16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net [다익스트라] 오랜만에 다익스트라 알고리즘 문제를 풀어볼까 해서 여유롭게 푸는가 했으나 너무 안일하게 생각했던 문제. 여우는 문제없이 최단거리를 구할 수 있겠는데.... 늑대는 속도가 x2배 일 수도, 0.5배 일 수도 있으므로 조금 고민해보지 않으면 쉽지 않은 문제인 것 같다. 도대체 어떻게 접근해야할지 떠오르질 않아 질문 게시판을 보다가 아 이거구나 하는 질문을 찾았다. 링크는 하단에 공유하도록 한다. ..

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net [다익스트라] 입력으로 출발 정점과 도착 정점이 주어지므로 한 정점에서 모든 정점으로의 최단 거리를 구하면 된다. 이 문제는 무난한 다익스트라 문제같이 보이나, 출발 정점 ~ 도착 정점 최단 거리의 경로를 구해야 한다. 나는 이 과정을 Dijkstra() 내에서 구현하였다. int[] from 라는 배열에 다음 정점을 방문하기 전에 어디서 왔는지에 대한 정보를 적었다. ( from[next] = current ) 아무튼 이건 포스팅..

1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net [플로이드 - 와샬, Floyd - Warshall] A, B, C, D, E가 있다고 하자. A와 B가 친구이고, B와 C가 친구일 때 A와 C는 친구이다. 그럼 C와 D가 친구일 때 A와 D는 친구일까? 아니다. 2-친구이므로 나의 친구의 친구까지만 친구로 인정된다. 따라서 D는 A의 3-친구이다. 이 문제에서는 2-친구만을 답으로 원하므로 플로이드 와샬을 수행하여 각 친구들이 n-친구인지 구하고 2 이하인 친구들의 개수를 구하도록 한다. (0일 때는 친구가 아..