백준 그래프 이론

    [백준, BOJ 2644] 촌수계산 (java)
    Problem Solving/BOJ

    [백준, BOJ 2644] 촌수계산 (java)

    https://www.acmicpc.net/problem/2644메모리: 14,136 KB , 시간: 100 ms사용 알고리즘: 그래프 이론, 그래프 탐색, 너비 우선 탐색import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(n..

    [백준, BOJ 14950] 정복자 (java)
    Problem Solving/BOJ

    [백준, BOJ 14950] 정복자 (java)

    https://www.acmicpc.net/problem/14950메모리: 26,704 KB , 시간: 376 ms사용 알고리즘: 그래프 이론, 최소 스패닝 트리처음에 다익스트라로 풀었다가, 알고리즘 분류를 보고 크루스칼 알고리즘으로도 풀 수 있겠다고 알게 돼서 다시 크루스칼로 풀었다...알고리즘 며칠 안 했다고 이전에는 당연히 크루스칼로 풀었을 문제를 다익스트라로 풀었네,,import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { static int[] parent; public static..

    [백준, BOJ 2211] 네트워크 복구 (java)
    Problem Solving/BOJ

    [백준, BOJ 2211] 네트워크 복구 (java)

    https://www.acmicpc.net/problem/2211메모리: 131,376 KB , 시간: 864 ms사용 알고리즘: 데이크스트라, 그래프 이론, 최단 경로이 문제에서 주의해야 할 점은 '슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.'는 점이다.이 부분을 간과하고 호기롭게 크루스칼 알고리즘으로 풀었다가 틀리고 나서야 문제를 다시 보고 이 점을 알았다. 따라서 이 문제는 크루스칼 알고리즘이 아니라 다익스트라 알고리즘을 사용해야 하는데, 관건은 최단 거리에 사용한 회선 정보를 출력해야 하는 것이다.이 문제를 해결하기 위해 다익스트라에서 사용하는 우선순위 큐에 넣을 Route 클래스를 만들고 객체에 경로의 마지막..

    [백준, BOJ 10423] 전기가 부족해 (java)
    Problem Solving/BOJ

    [백준, BOJ 10423] 전기가 부족해 (java)

    https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 메모리: 47,436 KB , 시간: 560 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class ..

    [백준, BOJ 3665] 최종 순위 (java)
    Problem Solving/BOJ

    [백준, BOJ 3665] 최종 순위 (java)

    https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 메모리: 36,928 KB , 시간: 424 ms 사용 알고리즘: 방향 비순환 그래프, 그래프 이론, 위상 정렬 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.S..

    [백준, BOJ 17490] 일감호에 다리 놓기 (java)
    Problem Solving/BOJ

    [백준, BOJ 17490] 일감호에 다리 놓기 (java)

    https://www.acmicpc.net/problem/17490 17490번: 일감호에 다리 놓기 2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다. www.acmicpc.net 메모리: 373,380 KB , 시간: 1,816 ms 사용 알고리즘: 자료 구조, 그래프 이론, 그리디 알고리즘, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer;..

    [백준, BOJ 11437] LCA (java)
    Problem Solving/BOJ

    [백준, BOJ 11437] LCA (java)

    https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 메모리: 47,624 KB , 시간: 1,276 ms 사용 알고리즘: 그래프 이론, 최소 공통 조상, 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static ArrayL..

    [백준, BOJ 2406] 안정적인 네트워크 (java)
    Problem Solving/BOJ

    [백준, BOJ 2406] 안정적인 네트워크 (java)

    https://www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1 ≤ n ≤ 1,000), m(0 ≤ m ≤ 10,000)이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서 www.acmicpc.net 메모리: 104,684 KB , 시간: 1,136 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.uti..

    [백준, BOJ 9470] Strahler 순서 (java)
    Problem Solving/BOJ

    [백준, BOJ 9470] Strahler 순서 (java)

    https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 메모리: 15,880 KB , 시간: 148 ms 사용 알고리즘: 방향 비순환 그래프, 그래프 이론, 위상 정렬 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java...

    [백준, BOJ 1516] 게임 개발 (java)
    Problem Solving/BOJ

    [백준, BOJ 1516] 게임 개발 (java)

    https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 메모리: 22,328 KB , 시간: 300 ms 사용 알고리즘: 방향 비순환 그래프, 그래프 이론, 위상 정렬 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import j..

티스토리툴바