개발하는 고라니

16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net [Kruskal, 최소 스패닝 트리] 문제에서 주어지는 인접 행렬의 정보를 받아 시작 정점(h), 도착 정점(tg) 그리고 비용(c)를 List에 담아 오름차순 정렬 후 크루스칼 알고리즘을 수행한다. 이 때 주의할 점은 비용은 최대 100,000,000이므로 비용을 더할 때 int가 아닌 long에 담아주도록 한다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.In..

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net [BFS * n] 각 사람의 친구 관계를 인접 리스트에 저장. n명에 대하여 BFS를 수행하였다. 이 때 Queue에 들어갈 원소는 2개이다. i 번째 사람, 그리고 1점에 해당하는 친구인지, 2점에 해당하는 친구인지, 혹은 그 이상 점수에 해당하는 친구인지... BFS를 수행하며 친구의 최대값을 저장하고 있다가 BFS의 while문을 빠져나갈 때 저장하고 있던 최대값을 그 사람의 점수를 저장하는 배열 person[]에 담는다. 그리고 저장된 최대값들 중 가장 ..

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

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [BFS] 백준의 벽 부수고 이동하기 시리즈 2번째 문제. 1번 문제의 경우 벽을 1개만 부실 수 있었다면 이 문제는 최대 10개를 부실 수 있다. 따라서 1과 유사하게 풀되, 배열의 사이즈를 조금 늘리면 되겠다. int[][][] dist = new int[1001][1001][11]; 큐에 들어가야할 원소의 개수는 3개이다. 다음 위치의 y좌표, x좌표, 벽을 몇 개 부수었는지. 그래서 만약 다음 위치가 벽이고, 현재 k개 ..

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 기본적인 플로이드-와샬 알고리즘 문제. 플로이드 와샬의 응용이 아니므로 간단하게 풀 수 있다. static void Floyd(int n){ for(int k=1; k

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net [플로이드-와샬 (Floyd-Warshall) 알고리즘] 이 문제를 풀기위해 플로이드 와샬 알고리즘을 공부했다. 이 문제를 DFS만으로 풀려고 하니까 TC에서 헤어나오질 못하였다. 사실 당연하다. 최대 정점의 수는 500개이나, 이후 최대 50,000개의 사건이 주어지므로, DFS 1번 당 최대 50,000 재귀를 한다고 할 때, 25,000,000번 호출되지 않을까? 하는 생각이 들었다. 역시 어떻게 풀어야할지 몰라 무식하게 접근한 꼴이다. 플로이드 와..

그래프가 주어졌을 때 하나의 시작 정점에서 다른 모든 정점들로 가는 최단 경로를 구하는 알고리즘은 다익스트라(Dijkstra)와 벨만-포드(Bellman-Ford)가 있다. 만약 그래프에 존재하는 모든 정점 사이의 최단 경로를 구하려면 다익스트라 알고리즘을 정점의 수(n) 만큼 반복 실행하면 된다. 즉 구해야할 최단 경로가 총 n^2개다. (자기 자신으로의 경로 포함) 하지만 이보다 간단한 방법으로 모든 정점 쌍 사이의 최단 경로를 구하는 방법인 플로이드-와샬(Floyd-Warshall) 알고리즘을 알아보고자 한다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택했다면, 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 또한 이 알고리즘은 동적..

6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net [BFS] 일반적인 2차원 배열에서 3차원 배열로 응용된 문제. 앞 뒤 좌 우 뿐만 아니라 상 하 까지 탐색 범위를 늘려주고 BFS를 실행하되, 탈출구를 찾았는지 못찾았는지에 대한 분기가 필요하다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue;..