문제
https://www.acmicpc.net/problem/17472
풀이
N*M크기의 이차원 격자에 땅 or 바다- 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리
- 다리는 바다에만 건설 가능
- 다리의 길이는 다리가 격자에서 차지하는 칸의 수
- 모든 섬을 다리로 연결하려고 함
- 다리의 양 끝은 섬과 인접한 바다 위에 있어야 함
- 다리의 방향이 중간에 바뀌면 안 됨
- 다리의 길이는 2 이상
- 나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값 출력
간만에 구현 문제를 풀어보았습니다..
(오랜만에 하니 빡세더군요..)
그래도 구현해야 할 부분들을 나눠서 구현하면 생각보단(?) 금방 풀 수 있는 문제입니다.
문제 해석부터 해보겠습니다.
- 땅 or 바다로 이루어진
N*M사이즈의 격자 - 땅이 상하좌우로 인접해있으면 하나의 덩어리로 봄
- 모든 섬을 다리로 연결
- 여기서 다리는 바다 위에만 설치 가능하며, 직선으로만 연결(최소 길이 2)
- 모든 섬을 연결하는 다리 길이의 최솟값 구하기
이 정도만 고려하면 될 것 같습니다.
우선 입력부터 받아봅시다.
입력
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];
visited = new boolean[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());
}
}- 지도는
map으로 선언했습니다. - 입력을 받았으니, 기본적으로 섬들을 고유의 번호로 분류해 주겠습니다.
섬 그룹화
private static void grouping() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 1) {
bfs(i, j);
label++;
}
}
}
}- 지도 전체를 탐색하다가 땅(
1)을 만나면 BFS를 통해 인접한 땅들을 하나의 그룹으로 만들어 줍니다.
private static void bfs(int sr, int sc) {
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[] { sr, sc });
visited[sr][sc] = true; // 방문 처리
map[sr][sc] = label; // 시작 좌표부터 label로 채움
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0], c = cur[1];
// 4방 탐색
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue; // 범위 밖이면 pass
if (map[nr][nc] == 0 || visited[nr][nc]) continue; // 땅이 아니거나, 이미 방문한 좌표라면 pass
map[nr][nc] = label; // 현재 땅을 label로 채움
visited[nr][nc] = true; // 방문 처리
queue.add(new int[] { nr, nc });
}
}
}grouping()메서드에서 가져온 좌표를 기준으로 인접한 땅들을 모두label에 주어진 번호로 채워 줍니다.- 여기서
label은 2로 선언해 주었습니다.- 땅이 1로 이루어져 있기 때문에, 섬으로 라벨링을 할 때 2, 3, 4, ... 순으로 매겨주었습니다.
- 하나의 섬이 그룹화가 끝나면
label을 증가 시켜주었습니다.(grouping()메서드 참조)
그룹화가 끝났으면, 다리를 지어주도록 합시다.
다리 건설
private static void buildEdges() {
// 다리의 최소 길이를 저장할 배열
int[][] lens = new int[label][label];
for (int i = 2; i < label; i++) Arrays.fill(lens[i], INF);
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
int start = map[r][c]; // 현재 좌표
if (start <= 1) continue; // 하나의 나라가 아니라면 pass
// 4방 탐색
for (int i = 0; i < 4; i++) {
int len = 0; // 길이를 저장할 변수
int nr = r + dr[i], nc = c + dc[i];
// 범위 내일 경우에 계속 반복
while (0 <= nr && nr < n && 0 <= nc && nc < m) {
int bridge = map[nr][nc]; // 다리를 시작할 좌표
if (bridge == start) break; // 다리의 시작 좌표가 땅이라면 break
// 다리의 시작이 바다라면
if (bridge == 0) {
len++; // 길이 증가
// 다음 좌표로 뻗어나감
nr += dr[i];
nc += dc[i];
continue;
}
// 다리 길이가 2 이상이고 다른 나라를 만났다면
if (len >= 2) {
int end = bridge; // 현재 좌표를 다리의 끝으로 설정
// 만약 start -> end 까지의 길이가 최솟값이라면 갱신
if (lens[start][end] > len) {
lens[start][end] = len;
lens[end][start] = len;
}
}
break;
}
}
}
}- 시작 좌표 -> 도착 좌표까지의 거리를 저장할 배열을 선언해 줍니다.
- 모든 값을 최댓값으로 채우고 더 짧을 경우 갱신하는 방식으로 구현했습니다.
- 모든 좌표를 탐색하는데, 나라가 아닐 경우엔 지나쳐 줍니다.
- 땅에서 시작하여 바다일 경우에 다음 좌표로 일자로 뻗어나가면서 탐색을 진행합니다.
- 만약 길이가 2 이상이고 다른 나라를 만났다면 최솟값을 갱신해 줍니다.
edges = new ArrayList<>();
for (int u = 2; u < label; u++) {
for (int v = u + 1; v < label; v++) {
if (lens[u][v] != INF) edges.add(new Edge(u, v, lens[u][v]));
}
}
}- 모든 좌표 탐색을 마쳤다면,
edges배열에 최댓값이 아닌 경우의 값들을 모두 넣어 줍니다.
Edge Class
class Edge implements Comparable<Edge> {
int u, v, w;
Edge (int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}- 크루스칼로 정렬을 할 것이기 때문에, 편의상 Edge 클래스를 따로 선언해 주었습니다.
- 가중치순으로 정렬하기 위해 compareTo를 오버라이딩 했습니다.
모든 섬들 사이에 다리들을 놓아준 최소 다리 길이 배열을 얻었으니, 이를 이용해서 모든 섬들을 잇는 다리들을 배치해 주겠습니다.
최소 길이 다리 놓기(크루스칼 알고리즘)
다리를 놓았을 때 모든 다리가 연결되는지 확인하기 위해 유니온 파인드 알고리즘을 사용하였습니다.
private static void make() {
p = new int[label];
s = new int[label];
for (int i = 2; i < label; i++) {
p[i] = i; // 자기 자신의 부모는 자신
s[i] = 1; // 자신 혼자 존재하니 크기는 1
}
}- 사이즈 순으로 그룹화를 진행할 것이기 때문에, 부모 배열과 사이즈 배열을 선언했습니다.
private static int find(int x) {
if (p[x] == x) return x; // 부모가 자신이면 자신 리턴
return p[x] = find(p[x]); // 경로 압축
}- 부모를 찾는
find()메서드
private static boolean union(int a, int b) {
int ra = find(a), rb = find(b); // a와 b의 부모
if (ra == rb) return false; // 부모가 같다면 return false
// ra를 기준으로 값을 넣을 것이기 때문에
// rb의 크기가 더 크다면 서로 위치 swap
if (s[ra] < s[rb]) {
int t = ra;
ra = rb;
rb = t;
}
// rb의 부모를 ra로 설정
p[rb] = ra;
s[ra] += s[rb]; // ra 밑에 들어가는 것이기 때문에 rb의 크기 추가
return true; // 유니온 연산이 진행되었으니 return true
}union()메서드- 합집합 연산을 진행하는 메서드입니다.
private static int kruskal() {
Collections.sort(edges); // 가중치 기준 정렬
int mstCost = 0; // 최소 다리 길이
int usedEdges = 0; // 사용한 다리 개수
for (Edge e : edges) {
if (union(e.u, e.v)) { // union 연산이 이루어졌다면,
mstCost += e.w; // 다리길이 추가
if (++usedEdges == label - 3) { // 모든 다리의 배치가 끝났다면
return mstCost; // 최소 다리 길이 리턴
}
}
}
return -1; // 모든 섬을 연결하지 못했다면 -1 리턴
}kruskal()메서드- 우리가 사용해야할 다리 길이는
label - 3임을 헷갈리시면 안 됩니다!!- 섬의 라벨링을 2번부터 시작했으므로 -3을 해주어야 합니다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static int[][] map;
static boolean[][] visited;
static int[] p, s;
static List<Edge> edges;
static int label = 2;
static final int[] dr = { -1, 1, 0, 0 };
static final int[] dc = { 0, 0, -1, 1 };
static final int INF = 1_000_000_000;
private static void grouping() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 1) {
bfs(i, j);
label++;
}
}
}
}
private static void bfs(int sr, int sc) {
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[] { sr, sc });
visited[sr][sc] = true;
map[sr][sc] = label;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0], c = cur[1];
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if (map[nr][nc] == 0 || visited[nr][nc]) continue;
map[nr][nc] = label;
visited[nr][nc] = true;
queue.add(new int[] { nr, nc });
}
}
}
private static void make() {
p = new int[label];
s = new int[label];
for (int i = 2; i < label; i++) {
p[i] = i;
s[i] = 1;
}
}
private static void buildEdges() {
int[][] lens = new int[label][label];
for (int i = 2; i < label; i++) Arrays.fill(lens[i], INF);
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
int start = map[r][c];
if (start <= 1) continue;
for (int i = 0; i < 4; i++) {
int len = 0;
int nr = r + dr[i], nc = c + dc[i];
while (0 <= nr && nr < n && 0 <= nc && nc < m) {
int bridge = map[nr][nc];
if (bridge == start) break;
if (bridge == 0) {
len++;
nr += dr[i];
nc += dc[i];
continue;
}
if (len >= 2) {
int end = bridge;
if (lens[start][end] > len) {
lens[start][end] = len;
lens[end][start] = len;
}
}
break;
}
}
}
}
edges = new ArrayList<>();
for (int u = 2; u < label; u++) {
for (int v = u + 1; v < label; v++) {
if (lens[u][v] != INF) edges.add(new Edge(u, v, lens[u][v]));
}
}
}
private static int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
private static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (s[ra] < s[rb]) {
int t = ra;
ra = rb;
rb = t;
}
p[rb] = ra;
s[ra] += s[rb];
return true;
}
private static int kruskal() {
Collections.sort(edges);
int mstCost = 0;
int usedEdges = 0;
for (Edge e : edges) {
if (union(e.u, e.v)) {
mstCost += e.w;
if (++usedEdges == label - 3) {
return mstCost;
}
}
}
return -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];
visited = new boolean[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());
}
}
grouping();
make();
buildEdges();
System.out.println(kruskal());
}
}
class Edge implements Comparable<Edge> {
int u, v, w;
Edge (int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}