🔗 링크
https://www.acmicpc.net/problem/2146
✏️ 문제
지도 상에서 주어진 섬을 연결하는 최단 경로를 찾는 문제입니다.
🧠 접근
각 지도의 섬을 구분할 수 있도록 섬 번호 설정
다리를 놓기 시작해야 하는 위치는 간단히 정할 수 있지만, 현재 배열에는 0, 1만 들어 있으므로 다른 섬에 도달했는지를 판정할 수 없습니다.
그래서 아래와 같은 메서드를 사용해 배열의 내용을 '각 섬마다 다른 숫자를 가지도록' 변경해 줍니다.
private static void setIslandNumber(int[][] map, int x, int y, int size, int number) {
isVisited = new boolean[size][size];
map[x][y] = number;
for (int i = 0; i < 4; i++) {
int nextX = x + DX[i];
int nextY = y + DY[i];
if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
if (map[nextX][nextY] == 1) setIslandNumber(map, nextX, nextY, size, number);
}
}
예제의 지도 입력은 아래와 같이 바뀌어 저장되게 됩니다.
// before
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
// after
2 2 2 0 0 0 0 3 3 3
2 2 2 2 0 0 0 0 3 3
2 0 2 2 0 0 0 0 3 3
0 0 2 2 2 0 0 0 0 3
0 0 0 2 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0
0 0 0 0 4 4 0 0 0 0
0 0 0 0 4 4 4 0 0 0
0 0 0 0 0 0 0 0 0 0시작 위치를 결정
현재 판정하고자 하는 위치가 섬 안에 있고 주위 4방향을 탐색, 바다가 한 칸 이상 있다면 다리를 놓을 수 있는 위치입니다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] != 0) {
boolean flag = false;
for (int k = 0; k < 4; k++) {
int nextX = i + DX[k];
int nextY = j + DY[k];
if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
if (map[nextX][nextY] == 0) {
flag = true;
break;
}
}
if (flag) calculateDistance(map, i, j, n);
}
}
}모든 시작 위치에 대해 시작점으로부터 거리를 구한 2차원 배열 작성
- 현재 시작한 섬의 번호라면 탐색할 필요가 없으니 더 이상 탐색하지 않습니다.
- map의 범위를 넘어선 경우에는 더 이상 탐색하지 않습니다.
- 그 외에는 모두 시작점으로부터의 거리를 구합니다.
- 작성된 2차원 배열에서 현재 섬 번호, 바다가 아닌 점까지의 거리 중 최솟값을 구합니다.
위 단계에서 구한 최솟값은 다른 섬에 도달한 이후에 한 칸을 더 세었으므로 1을 빼 주어야 합니다.
private static void calculateDistance(int[][] map, int x, int y, int size) {
isVisited = new boolean[size][size];
int startIslandNumber = map[x][y];
distance[x][y] = 0;
isVisited[x][y] = true;
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y));
while (!queue.isEmpty()) {
Point current = queue.poll();
for (int i = 0; i < 4; i++) {
int nextX = current.x + DX[i];
int nextY = current.y + DY[i];
if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
if (isVisited[nextX][nextY]) continue;
isVisited[nextX][nextY] = true;
distance[nextX][nextY] = distance[current.x][current.y] + 1;
queue.add(new Point(nextX, nextY));
}
}
// 다른 섬이라면 해당 위치까지의 값 중 최솟값으로 갱신
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (map[i][j] != 0 && map[i][j] != startIslandNumber)
minimumDistance = Math.min(minimumDistance, distance[i][j]);
}
}
}번외: 섬의 번호를 기입하는 방법
private static void setIslandNumber(int[][] map, int x, int y, int size, int number) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y));
map[x][y] = number;
while (!queue.isEmpty()) {
Point current = queue.poll();
map[current.x][current.y] = number;
for (int i = 0; i < 4; i++) {
int nextX = current.x + DX[i];
int nextY = current.y + DY[i];
if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
if (map[nextX][nextY] == 1) queue.add(new Point(nextX, nextY));
}
}
}
}섬의 번호를 기입하는 과정을 너비 우선 탐색(BFS)으로 작성하게 될 경우 섬의 크기가 클 경우 큐에 좌표 정보가 계속 쌓여 메모리를 매우 많이 사용하게 됩니다.
가령, Java에서 아래 코드와 같이 class를 생성하고 해당 인스턴스를 계속 사용한다면 메모리 제한을 넘을 위험이 있으니 섬의 번호를 매길 때에는 깊이 우선 탐색(DFS)를 사용하는 것을 고려해 보시기 바랍니다.
아래 코드에서 setIslandNumber()를 BFS로 작성했을 때에는 메모리 초과 오류를, DFS로 변경 이후에는 AC를 받았습니다.
📄 전체 소스 코드
import java.util.*;
import java.io.*;
public class Main {
private final static int[] DX = { 1, 0, -1, 0 };
private final static int[] DY = { 0, -1, 0, 1 };
private static int minimumDistance = Integer.MAX_VALUE;
private static int[][] distance;
private static boolean[][] isVisited;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int[][] map = new int[n][n];
for (int i = 0; i < n; i++) map[i] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
distance = new int[n][n];
int currentNumber = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 1) {
setIslandNumber(map, i, j, n, currentNumber);
currentNumber += 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] != 0) {
boolean flag = false;
for (int k = 0; k < 4; k++) {
int nextX = i + DX[k];
int nextY = j + DY[k];
if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
if (map[nextX][nextY] == 0) {
flag = true;
break;
}
}
if (flag) calculateDistance(map, i, j, n);
}
}
}
System.out.print(minimumDistance - 1);
}
/**
* 섬에 번호를 매긴다.
* @param map
* @param x
* @param y
* @param size
* @param number
*/
private static void setIslandNumber(int[][] map, int x, int y, int size, int number) {
isVisited = new boolean[size][size];
map[x][y] = number;
for (int i = 0; i < 4; i++) {
int nextX = x + DX[i];
int nextY = y + DY[i];
if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
if (map[nextX][nextY] == 1) setIslandNumber(map, nextX, nextY, size, number);
}
}
private static void calculateDistance(int[][] map, int x, int y, int size) {
isVisited = new boolean[size][size];
int startIslandNumber = map[x][y];
distance[x][y] = 0;
isVisited[x][y] = true;
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y));
while (!queue.isEmpty()) {
Point current = queue.poll();
for (int i = 0; i < 4; i++) {
int nextX = current.x + DX[i];
int nextY = current.y + DY[i];
if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
if (isVisited[nextX][nextY]) continue;
isVisited[nextX][nextY] = true;
distance[nextX][nextY] = distance[current.x][current.y] + 1;
queue.add(new Point(nextX, nextY));
}
}
// 다른 섬이라면 해당 위치까지의 값 중 최솟값으로 갱신
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (map[i][j] != 0 && map[i][j] != startIslandNumber)
minimumDistance = Math.min(minimumDistance, distance[i][j]);
}
}
}
}
class Point {
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
사진찍는 주니어 프론트엔드 개발자