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

solution 1

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][n];
        int[][] d = new int[n][n];
        int[][] g = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int cnt = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 1 && g[i][j] == 0) {
                    Queue<Pair> q = new LinkedList<Pair>();
                    g[i][j] = ++cnt;
                    q.add(new Pair(i, j));
                    while (!q.isEmpty()) {
                        Pair p = q.remove();
                        int x = p.x;
                        int y = p.y;
                        for (int k=0; k<4; k++) {
                            int nx = x+dx[k];
                            int ny = y+dy[k];
                            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                                if (a[nx][ny] == 1 && g[nx][ny] == 0) {
                                    q.add(new Pair(nx, ny));
                                    g[nx][ny] = cnt;
                                }
                            }
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int l=1; l<=cnt; l++) {
            Queue<Pair> q = new LinkedList<Pair>();
            for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    d[i][j] = -1;
                    if (g[i][j] == l) {
                        q.add(new Pair(i,j));
                        d[i][j] = 0;
                    }
                }
            }
            while (!q.isEmpty()) {
                Pair p = q.remove();
                int x = p.x;
                int y = p.y;
                for (int k=0; k<4; k++) {
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                        if (d[nx][ny] == -1) {
                            d[nx][ny] = d[x][y] + 1;
                            q.add(new Pair(nx,ny));
                        }
                    }
                }
            }

            for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    if (a[i][j] == 1 && g[i][j] != l) {
                        if (ans == -1 || d[i][j]-1 < ans) {
                            ans = d[i][j]-1;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

g에는 1,2,3영역표시, l은 총 몇까지 있나 확인한다

d에서 섬인 곳은 0,바다는 -1 로 초기화 한다. 그리고 d에서 각 섬에서 떨어진 만큼 1씩 늘린다. 그리고 각 섬과 다른 섬과의 거리를 다 측정하고 그중 가장 큰 것 구하는 거다

solution 2

[더 효율적인 것]

import sys
read = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(100000)

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

n = int(read())
a = [[int(i) for i in read().split()] for _ in range(n)]
d = [[0]*(n) for _ in range(n)]
g = [[0]*(n) for _ in range(n)]

cnt = 0

for i in range(n):
    for j in range(n):
        if a[i][j] == 1 and g[i][j] == 0:
            q = []
            cnt += 1
            g[i][j] = cnt
            q.append((i, j))
            while len(q):
                x, y = q.pop(0)
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx and nx < n and 0 <= ny and ny < n :
                        if a[nx][ny] == 1 and g[nx][ny] == 0:
                            g[nx][ny] = cnt
                            q.append((nx, ny))
q = []
for i in range(0, n):
    for j in range(0, n):
        d[i][j] = -1
        if a[i][j] == 1:
            q.append((i, j))
            d[i][j] = 0

while len(q):
    x, y = q.pop(0)
    for k in range(0, 4):
        nx, ny = x + dx[k], y + dy[k]
        if 0 <= nx and nx < n and 0 <= ny and ny < n :
            if d[nx][ny] == -1 :
                d[nx][ny] = d[x][y] + 1
                g[nx][ny] = g[x][y]
                q.append((nx, ny))


ans = -1
for i in range(0, n):
    for j in range(0, n):
        for k in range(0, 4):
            nx, ny = i + dx[k], j + dy[k]
            if 0 <= nx and nx < n and 0 <= ny and ny < n :
                if g[i][j] != g[nx][ny]:
                    if ans == -1 or ans > d[i][j] + d[nx][ny]:
                        ans = d[i][j] + d[nx][ny]

print(ans)

근처에 있는것과 값이 다르면 그건 다른 섬에서 나온 거리