넘치게 채우기

https://www.acmicpc.net/problem/11404BOJ - 플로이드문제 유형: 최단 거리, 그래프, 플로이드-워셜문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주..

https://www.acmicpc.net/problem/1504BOJ - 특정한 최단 경로문제 유형: 최단 경로, 다익스트라, 그래프문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 ..

https://www.acmicpc.net/problem/1043BOJ - 거짓말문제 유형: 유니온-파인드, BFS, DFS, 그래프 문제 난이도: Gold IV 시간 제한: 2초 메모리 제한: 128MB 문제지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히,..

https://www.acmicpc.net/problem/1916BOJ - 최소비용 구하기문제 유형: 최단 거리, 그래프이론문제 난이도: Gold V시간 제한: 0.5초메모리 제한: 128MB 문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의..

https://www.acmicpc.net/problem/25601BOJ - 자바의 형변환문제 유형 : 해시, 그래프, 트리문제 난이도 : Silver I시간 제한: 2초메모리 제한: 512MB 문제자바의 클래스끼리는 상속을 통해 자신의 기능 일부를 다른 클래스에게 이식할 수 있다. 여기서 상속을 받은 클래스는 자식 클래스, 상속을 한 클래스는 부모 클래스가 된다. 클래스를 이용해서 만든 객체는 다른 클래스로 형태를 변환할 수 있는데, 이를 형변환(Casting)이라고 한다. 만약 자식 클래스에서 부모 클래스로 변환한다면 업캐스팅(Upcasting), 부모 클래스에서 자식 클래스로 변환한다면 다운캐스팅(Downcasting) 이라고 부른다. 즉, 자식 클래스와 부모 클래스 관계에 놓여있다면 형변환이 가능..

https://www.acmicpc.net/problem/28360BOJ - 양동이 게임문제 유형 : 그리디, 그래프문제 난이도 : Silver I 문제찬우는 천하제일 코딩대회 참가자들과 간단한 게임을 하기로 했다. 게임은 '양동이 게임'으로, 맨 위의 양동이에 물을 100$만큼 부어 흘려보냈을 때 최종적으로 가장 많은 물이 담긴 양동이를 선택하면 이기는 게임이다. 양동이를 고르기 전까지는 연결 상태를 알 수 없다. 하지만 찬우는 양동이들이 어떻게 연결되어 있는지 이미 알고 있는 상태였다! 찬우가 게임을 이기기 위해서 골라야 하는 양동이에는 얼마만큼의 물이 들어있는지 알아보자. 1번 양동이가 항상 맨 위에 있으며, 1의 양만큼 물이 채워져 있는 양동이에 K>0개의 나가는 방향 호스가 연결되어 있으면 양동..

https://leetcode.com/problems/maximum-total-importance-of-roads/description/leetcode - Maximum Total Importance of Roads문제 유형 : 그리디, 우선순위 큐, 그래프문제 난이도 : Medium 문제You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecti..

https://leetcode.com/problems/find-center-of-star-graph/description/leetcode - Find Center of Star Graph문제 유형 : 그래프, 해시문제 난이도 : Easy 문제There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.You are given a 2D integer array edges where each edges[..

https://leetcode.com/problems/find-if-path-exists-in-graph/description/ Leetcode - Find if Path Exists in Graph 문제 유형 : 그래프, dfs / bfs 문제 난이도 : Easy There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between verte..

https://leetcode.com/problems/find-the-town-judge/description/ Find the Town Judge - LeetCode Can you solve this real interview question? Find the Town Judge - In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: 1. The town judge trusts nobody. 2. E leetcode.com LeetCode - Find the Town Judge 문제 ..