개발하는 고라니

코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr [Floyd-Warshall] 플로이드 와샬 알고리즘을 수행해서, i번 사람이 j번 사람에게 직접/간접적으로 도달할 수 있는지 체크한 다음, i번 사람이 자기 자신을 제외한 모든 사람에게 도달할 수 있으면 순위를 확실히 알 수 있다. 문제에서 주어진 조건은 간선이 단방향이라는 것을 알려준다. 따라서 주어진 입력을 적절히 이용하여 직접적인 A와 B의 관계를 boolean[ ][ ]에 표현하고 플로이드 와샬을 수행하면, A가 C에게 도달 할 수 있는지 여부를 알 수 있다. 표를 보며 이해하면 더 쉽게 와닿을 수 있을 것이다. 주어진 입력으로 boolean[][] 배열을 지..

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

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일 때는 친구가 아..

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

[Floyd-Warshall] 조금 독특한(?) 문제라고 생각된다. 매번 모든 정점에 대해 다른 정점들로의 최단 거리를 구하는 것을 목표로 풀었는데 이번엔 모든 최단 거리를 주어지고, 초기 인접 행렬을 구해보라고 하는 문제라서 일까. 문제를 풀기 위해 boolean origin[ ][ ]이라는 배열을 준비했다. 이 배열의 원소 값이 true가 된다면, 기존에 있던 간선이 아닌 다른 정점을 통해 이어진 간선이라는 것을 나타내게 될 것이다. 만일 현재 3번 정점에 있다고 하고, 5번 정점으로의 최단 거리가 a일 때, map[3][5] = a 이다. 그리고 1번 정점을 거쳐서 5번 정점으로 가는 거리를 map[1][5] = b이고, 정점 3에서 정점 1로의 거리 map[3][1] = c라고 할 때 a == b..

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) 비교 결과를 ..

2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [플로이드-와샬] 일반적인 플로이드-와샬을 이용하여 모든 사람간의 키 순서를 구하면 된다. 여기까지는 유추하기 쉬울 수 있으나, 특정 사람 i가 몇 번째로 큰 것 인지에 대한 것을 판단하기는 약간 어려울 수 있다. 만일 특정 사람 i가 다른 사람 j에 대하여 키 관계를 모를 때, j 입장에서도 i의 키 관계를 모른다면 그것은 자신이 몇 번째로 큰 사람인지 모르는 것과 마찬가지이다. # Code import java.io.BufferedReader; import j..