https://www.acmicpc.net/problem/17472
1. 아이디어
BFS, DFS 알고리즘으로 각 섬에 대해 번호를 매긴 후 설치할 수 있는 모든 다리를 찾아서 섬은 노드, 다리를 간선으로 하는 최소 스패닝 트리를 구하는 방식으로 해결했다.
2. 문제풀이
각 섬에 번호를 붙여서 섬들을 구분하려고 했고 지도를 순회하며 섬을 발견하면 BFS, DFS 알고리즘으로 해당 섬 전체에 번호를 부여했다. 이후 지도를 순회하며 현재 위치가 섬이면서 오른쪽이 바다인 경우, 현재 위치가 섬이면서 아래쪽이 바다인 경우, 다시 섬을 발견할 때까지 해당 방향으로 계속 가며 섬을 발견하면 이 정보로 다리를 생성해서 우선순위 큐에 넣어줬다. 이후 이 우선순위 큐로 크루스칼 알고리즘을 돌려 모든 섬을 연결하는 다리 길이의 최솟값을 찾았다.
3. 코드
import java.io.*;
import java.util.*;
public class Main_BFS {
private static class Edge implements Comparable<Edge> {
int a;
int b;
int w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}
private static int[] p;
private static int[] make(int N) {
int[] arr = new int[1 + N];
for (int i = 1; i <= N; i++) arr[i] = i;
return arr;
}
private static int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
private static void union(int x, int y) {
p[find(y)] = find(x);
}
private static final int[] dr = {-1, 0, 1, 0};
private static final int[] dc = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 섬에 번호 붙이기
boolean[][] visited = new boolean[N][M];
int num = 1;
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0 || visited[i][j]) continue;
bfs(i, j, num, N, M, map, visited);
num++;
cnt++;
}
}
PriorityQueue<Edge> edges = new PriorityQueue<>();
// 가로 방향 다리 탐색
for (int i = 0; i < N; i++) {
for (int j = 0; j < M - 1; j++) {
if (map[i][j] != 0 && map[i][j + 1] == 0) {
int k = 1;
while (j + k < M && map[i][j + k] == 0) {
k++;
}
if (j + k != M && k > 2) edges.add(new Edge(map[i][j], map[i][j + k], k - 1));
// 탐색 위치 변경
j += k - 1;
}
}
}
// 세로 방향 다리 탐색
for (int j = 0; j < M; j++) {
for (int i = 0; i < N - 1; i++) {
if (map[i][j] != 0 && map[i + 1][j] == 0) {
int k = 1;
while (i + k < N && map[i + k][j] == 0) {
k++;
}
if (i + k != N && k > 2) edges.add(new Edge(map[i][j], map[i + k][j], k - 1));
// 탐색 위치 변경
i += k - 1;
}
}
}
int ans = kruskal(cnt, edges);
System.out.println(ans);
}
private static void bfs(int r, int c, int num, int N, int M, int[][] map, boolean[][] visited) {
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{r, c});
visited[r][c] = true;
while (!q.isEmpty()) {
int[] node = q.remove();
map[node[0]][node[1]] = num;
for (int dir = 0; dir < 4; dir++) {
int nr = node[0] + dr[dir];
int nc = node[1] + dc[dir];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if (map[nr][nc] == 0 || visited[nr][nc]) continue;
q.add(new int[]{nr, nc});
visited[nr][nc] = true;
}
}
}
private static int kruskal(int N, PriorityQueue<Edge> edges) {
p = make(N);
int sum = 0;
int cnt = 0;
while (!edges.isEmpty()) {
Edge e = edges.remove();
if (find(e.a) == find(e.b)) continue;
union(e.a, e.b);
sum += e.w;
cnt++;
if (cnt == N - 1) return sum;
}
return -1;
}
}import java.io.*;
import java.util.*;
public class Main_DFS {
private static class Edge implements Comparable<Edge> {
int a;
int b;
int w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}
private static int[] p;
private static int[] make(int N) {
int[] arr = new int[1 + N];
for (int i = 1; i <= N; i++) arr[i] = i;
return arr;
}
private static int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
private static void union(int x, int y) {
p[find(y)] = find(x);
}
private static final int[] dr = {-1, 0, 1, 0};
private static final int[] dc = {0, 1, 0, -1};
private static int N;
private static int M;
private static int[][] map;
private static boolean[][] visited;
private static int num = 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 섬에 번호 붙이기
visited = new boolean[N][M];
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0 || visited[i][j]) continue;
dfs(i, j);
num++;
cnt++;
}
}
PriorityQueue<Edge> edges = new PriorityQueue<>();
// 가로 방향 다리 탐색
for (int i = 0; i < N; i++) {
for (int j = 0; j < M - 1; j++) {
if (map[i][j] != 0 && map[i][j + 1] == 0) {
int k = 1;
while (j + k < M && map[i][j + k] == 0) {
k++;
}
if (j + k != M && k > 2) edges.add(new Edge(map[i][j], map[i][j + k], k - 1));
// 탐색 위치 변경
j += k - 1;
}
}
}
// 세로 방향 다리 탐색
for (int j = 0; j < M; j++) {
for (int i = 0; i < N - 1; i++) {
if (map[i][j] != 0 && map[i + 1][j] == 0) {
int k = 1;
while (i + k < N && map[i + k][j] == 0) {
k++;
}
if (i + k != N && k > 2) edges.add(new Edge(map[i][j], map[i + k][j], k - 1));
// 탐색 위치 변경
i += k - 1;
}
}
}
int ans = kruskal(cnt, edges);
System.out.println(ans);
}
private static void dfs(int r, int c) {
map[r][c] = num;
visited[r][c] = true;
for (int dir = 0; dir < 4; dir++) {
int nr = r + dr[dir];
int nc = c + dc[dir];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if (map[nr][nc] == 0 || visited[nr][nc]) continue;
dfs(nr, nc);
}
}
private static int kruskal(int N, PriorityQueue<Edge> edges) {
p = make(N);
int sum = 0;
int cnt = 0;
while (!edges.isEmpty()) {
Edge e = edges.remove();
if (find(e.a) == find(e.b)) continue;
union(e.a, e.b);
sum += e.w;
cnt++;
if (cnt == N - 1) return sum;
}
return -1;
}
}4. 후기
- BFS
- DFS
'코딩테스트 준비 > 백준' 카테고리의 다른 글
| [백준] 2075번 - N번째 큰 수 [Java] (0) | 2025.02.11 |
|---|---|
| [백준] 9626번 - 크로스워드 퍼즐 [Java] (0) | 2025.02.11 |
| [백준] 2146번 - 다리 만들기 [Java] (0) | 2025.02.11 |
| [백준] 2887번 - 행성 터널 [Java] (0) | 2025.02.11 |
| [백준] 16398번 - 행성 연결 [Java] (0) | 2025.02.11 |
