알고리즘/백준5 1504번 특정한 최단 경로 G4 문제는 간단하다. 1번 정점부터 N번 정점까지 최단 거리를 구하는데, U정점과 V정점을 반드시 거쳐야 하는 것이다. 일단 처음 문제를 보면 해당 정점까지의 최단 거리를 구하는 다익스트라를 떠올릴 수 있겠다. 그리고 정적으로 2정점을 지난다는 것이 조건이니 두 개의 정점을 지난다는 걸 구현하면 된다. 그렇다면 일단 1을 시작 정점으로 해서 모든 정점으로 향하는 최단 거리를 구하고, 또 U 정점을 시작정점으로 구하고, V 정점을 시작정점으로 구한 뒤, 1부터 U까지, U에서 V까지, V에서 N까지 최단 거리와 1부터 V까지, V에서 U까지, U에서 N까지 최단 거리를 비교한 후 최단 거리를 출력하면 되지 않을까? 생각했다. 여기서 중요한 것은 만약 1에서 부터 두 정점을 지나 N까지 가는 경우가 없다면 -1.. 2023. 4. 3. 1005번 ACM Craft G3 문제가 꽤나 길다. 간단하게 말하자면 해당 건물을 올리기 위해 먼저 다른 건물을 올려야 한다는 것이다. 하지만 여기서 특기할 점이 있다면 1번 건물을 짓고 동시에 2번과 3번 건물을 짓기 시작할 수 있다는 것이다. 따라서 4번 건물을 짓기 위해 필요한 시간은 1번 건물 10초 + 2번 건물 1초 + 3번 건물 100초 + 4번 건물 10초로 121초 가 아니라 1번 건물 10초 + (동시에 짓는 건물 중 오래걸리는 시간(2번, 3번))100초 + 4번 건물 10초로 120초이다. 이런 개념을 가지고 가면 간단하게 위상 정렬로 풀린다. 다른 건 다 위상정렬과 비슷하나 추가적으로 필요한 것은 최소의 시간을 기록할 DP 배열과 건물짓는데 걸리는 시간을 비교할 방법이다. DP[1] (1번째 값) 은 건물1의 건.. 2023. 4. 3. 2252번 줄 세우기 G3 문제의 내용은 위와 같다. 중요한 것은 N과 M을 입력 받은 후, M번 입력을 받는데, 그때 입력받는 두 번호가 비교하는 학생의 번호이고, 앞에 입력받는 번호의 학생이 뒤에 입력받는 학생보다 앞에 선다는 것이다. 즉 3 2 1 3 2 3 이면 1번 학생은 3번 학생의 앞에, 2번 학생은 3번 학생의 앞에 줄을 선다는 것이다. 1번과 2번 학생의 순서는 상관없으므로 답은 1 2 3 또는 2 1 3이 될 수 있다. 이를 위해 우선 Linked List배열을 생성한다. 이 때 받을 인자는 Integer이다. 그 후 N의 크기만큼의 배열을 생성하고, 각각 초기화를 시켜준다. 이후 순서 비교를 위해 입력받은 인자를 리스트에 입력한다. 순서를 정해준 것이기 때문에 유향 그래프라고 할 수 있다. 이런 느낌. 또한 학.. 2023. 4. 3. 백준 1922번 네트워크 연결 G4 문제는 위와 같다. 놀랍게도 입력만 고쳐주면 최소 스패닝 트리 문제의 코드와 똑같이 내도 통과 가능하다. 같은 논리이기 때문이다. 구체적인 풀이는 최소 스패닝 트리 글을 확인하도록 하고, 전체 코드만 확인해보겠다. 전체 코드는 다음과 같다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Mai.. 2023. 3. 29. 이전 1 2 다음
