백준 2147번: 다리 만들기

문제

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

---

풀이

여러 섬으로 이루어진 나라에서 한 섬과 다른 섬을 잇는 다리 하나를 만든다고 할 때 가장 짧은 다리의 길이를 구하는 문제입니다. 이때 섬은 동서남북으로 붙어있는 땅을 의미합니다.

---

접근

어떤 섬과 다른 섬 사이를 잇는 다리를 만들어야 하므로 각 섬이 다른 섬이라는 것을 표시해야 합니다.

여러 가지 알고리즘을 사용할 수 있지만 저는 dfs 알고리즘을 이용하여 각 섬에 번호를 정해주었습니다.

입력이 주어질 때 나라를 2차원 배열 arr로 표현할 때 섬은 1, 바다는 0으로 표시하기 때문에 dfs 함수의 매개변수에 섬의 번호를 의미하는 num을 추가해서 arr[x][y]를 num으로 바꿔주었습니다.

이후 bfs 알고리즘을 이용하여 어떤 섬과 가장 가까이에 있는 섬을 찾아 그 사이의 거리, 즉 다리의 길이를 찾아 최솟값을 구했습니다.

임의의 좌표 (x, y)가 있을 때 x, y와 어떤 섬의 시작하는 위치에서 (x, y)까지 이동했을 때의 최단 거리 cnt를 표현하는 point 클래스를 만들어 사용했습니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

class point {
    int x, y, cnt;

    public point(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

public class Main {

    static int n, min;
    static int[][] arr;
    static boolean[][] visited;

    public static void dfs(int x, int y, int num) {
        visited[x][y] = true;
        arr[x][y] = num; // (2)
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny] && arr[nx][ny] == 1) {
                dfs(nx, ny, num); // (3)
            }
        }
    }

    public static void bfs(int x, int y) {
        Queue<point> queue = new LinkedList<>();
        queue.offer(new point(x, y, 0));
        visited = new boolean[n][n];
        visited[x][y] = true;
        int num = arr[x][y]; // (5)
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };
        while (!queue.isEmpty()) {
            point p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny]) {
                    if (arr[nx][ny] == 0) { // (6)
                        visited[nx][ny] = true;
                        queue.offer(new point(nx, ny, p.cnt + 1));
                    } else if (arr[nx][ny] != num) { // (7)
                        min = Math.min(min, p.cnt);
                        return;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int num = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && arr[i][j] == 1) {
                    dfs(i, j, num++); // (1)
                }
            }
        }
        min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] > 0) {
                    bfs(i, j); // (4)
                }
            }
        }
        System.out.println(min);
    }
}

(1) 모든 입력이 끝난 후에 i와 j를 포함한 2중 for문 안에서 (i, j)에 방문한 적이 없고 섬이면 dfs 함수를 실행합니다.

이때 num을 1부터 시작하여 1씩 더해가며 섬에 번호를 매깁니다.

 

(2) dfs 함수 안에서 (x, y)에 방문처리를 해준 뒤에 arr[x][y]를 num으로 바꿉니다.

이렇게 되면 dfs 함수를 재귀적으로 실행하면서 이어져있는 같은 섬의 번호를 num으로 매길 수 있습니다.

 

(3) 다음으로 이동할 좌표가 가능한 좌표인지, 방문한 적이 없는지, 바다가 아니라 섬인지 확인합니다.

위의 조건을 만족한다면 dfs 함수를 재귀적으로 실행합니다.

 

(4) 모든 섬의 번호를 매긴 후에  i와 j를 포함한 2중 for문 안에서 (i, j)가 바다가 아니라면 bfs 함수를 실행합니다.

같은 섬이어도 어떤 좌표에서 시작하냐에 따라 거리가 달라질 수도 있기 때문에 모두 확인해줍니다.

 

(5) bfs 함수 안에서 시작하는 위치의 섬의 번호를 정수 변수 num에 저장해둡니다.

그전에 큐에 point(x, y, 0)를 삽입하고 visited 배열을 초기화해준 뒤에 (x, y)에 방문처리를 해줍니다.

이후 큐에서 poll한 값을 p라고 했을 때 큐가 비어있지 않을 때까지 다음 과정을 반복해줍니다.

 

(6) 다음으로 이동할 좌표 (nx, ny)가 가능한 좌표이고 방문한 적이 없을 때 (nx, ny)가 바다인지 확인합니다.

바다라면 해당 좌표에 방문처리를 해주고 큐에 point(nx, ny, p.cnt + 1)을 삽입해줍니다.

 

(7) 바다가 아니라면 가장 가까운 다른 섬에 도착한 것이므로 다음 연산을 실행하고 함수를 종료합니다.

가장 짧은 다리의 길이를 의미하는 min을 시작 위치 (x, y)에서 (p.x, p.y)까지 이동했을 때의 최단 거리 p.cnt와 비교하여 더 작은 값으로 바꿔줍니다.

 

모든 과정이 끝나면 min 값을 출력한 후에 프로그램을 종료합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define math_min(a, b) a < b ? a : b
int n, min, **arr, **visited;
typedef struct {
	int x, y, cnt;
} Point;
typedef struct node {
	Point point;
	struct node* next;
} node;
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int x, int y, int cnt) {
	node* now = (node*)malloc(sizeof(node));
	now->point.x = x;
	now->point.y = y;
	now->point.cnt = cnt;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
Point pop(Queue* queue) {
	Point re;
	node* now;
	now = queue->front;
	re = now->point;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
void dfs(int x, int y, int num) {
	visited[x][y] = 1;
	arr[x][y] = num;
	int dx[] = { -1, 0, 1, 0 };
	int dy[] = { 0, -1, 0, 1 };
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && arr[nx][ny] == 1) {
			dfs(nx, ny, num);
		}	
	}
}
void bfs(int x, int y) {
	Queue queue;
	initQueue(&queue);
	push(&queue, x, y, 0);
	for (int i = 0; i < n; i++) {
		memset(visited[i], 0, sizeof(int) * n);
	}
	visited[x][y] = 1;
	int num = arr[x][y];
	int dx[] = { -1, 0, 1, 0 };
	int dy[] = { 0, -1, 0, 1 };
	while (!empty(&queue)) {
		Point p = pop(&queue);
		x = p.x;
		y = p.y;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny] && arr[nx][ny] != num) {
				visited[nx][ny] = 1;
				if (arr[nx][ny] == 0) {
					push(&queue, nx, ny, p.cnt + 1);
				}
				else {
					min = math_min(min, p.cnt);
					return;
				}
			}
		}
	}
}
main() {
	scanf("%d", &n);
	arr = (int**)malloc(sizeof(int*) * n);
	visited = (int**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++) {
		arr[i] = (int*)malloc(sizeof(int) * n);
		visited[i] = (int*)malloc(sizeof(int) * n);
		memset(visited[i], 0, sizeof(int) * n);
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	int num = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j] && arr[i][j] == 1) {
				dfs(i, j, num++);
			}
		}
	}
	min = INT_MAX;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] > 0) {
				bfs(i, j);
			}
		}
	}
	printf("%d", min);
}

자바를 이용한 풀이와 동일합니다.

 

---

결론

서로 떨어져 있는 섬들의 번호를 매기는 함수를 dfs가 아닌 bfs로 만들 수도 있었는데 처음에 공부할 때 1개의 코드 안에 다양한 방법으로 문제를 해결했으면 좋겠다는 생각에 이렇게 풀었던 것 같습니다.

이제와서 생각해보면 이러한 방식이 dfs와 bfs 알고리즘과의 특성을 이해하는 데에 도움이 많이 됐었던 것 같습니다.