알고리즘

BOJ - 네트워크 복구 2211번 (JAVA)

❓ 문제 - 백준 네트워크 복구 2211번 - JAVA 풀이법 출처 ( https://www.acmicpc.net/problem/2211) 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 📝 문제해결법 1. 문제 N개로 구성된 컴퓨터에서 1번(슈퍼컴퓨터)와 다른 컴퓨터들을 최소 경로의 비용으로 연결시켜야 한다. 이때, 복구한 회선의 갯수와 복구한 회선의 수를 나타내는 두 정수 A, B를 출력한다. 2. 해결 방법 문제를 봤을 때 N의 범위가 우선 (1

BOJ - 우주신과의 교감 1774번 (JAVA)

❓ 문제 - 백준 우주신과의 교감 1774번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/1774) 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 📝 문제해결법 1. 문제 n개의 우주신의 정보(x, y)가 주어질 때 이미 연결된 신들을 제외한 다른 우주신을 최소 비용으로 해서 모두 다 연결할 때의 통로 길이 합을 구하여라. 2. 해결 방법 MST(최소 스패닝 트리)로 우선 각 우주신들의 모두 연결된 경우를 union_find 해준다. 그리고 ..

BOJ - 다리 만들기 2146번 (JAVA)

❓ 문제 - 백준 다리 만들기 2146번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/2146) 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 📝 문제해결법 1. 문제 N*N 크기의 이차원 평면상에 여러 개의 섬으로 이루어져 있는데 각 섬을 바다 위에 놓을 수 있다. 두 대륙을 잇는 가장 짧은 다리의 길이를 구하여라. 2. 해결 방법 우선 N의 크기가 (100이하의 자연수)이기 때문에 BFS나 DFS의 완전탐색 기법으로 이어진 섬을 분류하고 각 섬에서 다른 섬으로 다시 BF..

BOJ - 벽 부수고 이동하기4 16946번 (JAVA)

❓ 문제 - 백준 벽 부수고 이동하기4 16946번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/16946) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 📝 문제해결법 1. 문제 벽은 1, 이동할 수 있는 곳은 0인데 각 벽에 대해서 이동할 수 있다고 하면 최대 이동할 수 있는 칸의 개수를 나타내라. 2. 해결 방법 우선 N, M의 각 범위가 1이상 1000이하 이므로 각 벽에 대해서 이동허락했을 때 BFS를 돌리면 N^2 * M ^2로 당연히 시..