[백준] 2146번 - 다리 만들기 (Java)

 

 

 

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

2146번: 다리 만들기

 

<문제 분석>

N x N인 맵에서 여러 개의 섬이 있다. 각 섬을 연결하는 다리를 한 개만 건설한다고 할 때
가장 짧은 거리를 구하라.
BFS탐색으로 각 섬은 탐색할 수 있다. 그런데 각 섬과 다른 섬과 가장 최소거리는 어떻게 구하지?

 

<조건>
시간 제한 : 2초
메모리 제한 : 192MB
지도크기 : N <= 100
0은 바다, 1은 육지
섬은 항상 두개 이상

<풀이>
이 문제풀이는 크게 두 부분으로 구분된다.
첫째, 맵에서 섬들을 구분하는 작업(Flood Fill)
둘째, 구분한 섬에서 다른 섬으로 탐색하는 작업(BFS탐색)

* 섬 구분하기
1. 맵을 부르트포스 탐색해서 육지( '1')인 위치를 찾아서 방문 표시를 하고 큐에 넣는다.
  - 바다('0')면 무시한다.
  - 이미 방문했으면 무시한다.
  - 각 섬을 구분하는 섬번호를 증가시킨다.
2. BFS탐색을 시작한다.
  - 큐에서 꺼낸다.
  - 상/하/좌/우 탐색을 한다.
  - 바다('0')가 아니고, 방문하지 않았으면 큐에 그 위치를 넣는다.

  - 새 위치를 큐에 넣는다.
  - 방문 표시를 한다.
  - 맵에 섬번호를 넣는다.

* 섬끼리 최단거리 찾기
1. 부르트포스로 맵의 값이 0보다 크고, 방문하지 않았으면 다리 거리 탐색 시작한다
  - 그룹번호도 좌표와 함께 같이 넘겨줘야 함.
  - 상/하/좌/우 탐색 시작한다
  - 바다'0'일 경우만 탐색 계속한다.

  - 도착지가 같은 섬번호면 스킵한다.
  - 도착점이 다른 섬일 경우에만 최소값 거리 업데이트
2. 섬 클래스는 x, y좌표와 거리까지 같이 저장하도록 하자.
  - 별도의 변수 하나로만 관리하면 값을 비교하기가 힘들다.

 

<코드 구현>

import java.util.Scanner;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

//[백준] 2146번 - 다리 만들기 (Java)

public class Main {
    static int N;
    static int map[][];
    static boolean visited[][];

    class Point {
        int x;
        int y;
        int len;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
        Point (int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
    }
	public void InputData() throws IOException
	{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                map[i][j] = sc.nextInt();
            }
        }
	}

    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    public void findIsland(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x, y));
        visited[x][y] = true;
        while (!Q.isEmpty()) {
            Point now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                // 맵 범위를 벗어나면 무시
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; 
                if (map[nx][ny] == 0) continue; // 방문한 곳이 바다면 무시
                if (visited[nx][ny]) continue; // 이미 방문한 곳이면 무시
                Q.offer(new Point(nx, ny)); // 큐에 삽입
                map[nx][ny] += group_num; // 맵에 그룹숫자 부여
                visited[nx][ny] = true; // 방문처리
            }
        }
    }

    public void setBridge(int x, int y, int island_id) {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x, y, 0));
        visited[x][y] = true;
        while (!Q.isEmpty()) {
            Point now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 맵 범위를 벗어나면 무시
                if (map[nx][ny] == island_id) continue; // 방문한 곳이 같은섬이면 무시
                if (visited[nx][ny]) continue; // 이미 방문한 곳이면 무시
                if (map[nx][ny] == 0) { // 방문한 곳이 바다면 후속 처리
                    Q.offer(new Point(nx, ny, now.len+1)); // 큐에 삽입
                    visited[nx][ny] = true; // 방문처리        
                } else { // 방문한 곳이 다른 섬이면
                    min_len = Math.min(min_len, now.len); // 이동거리 최소값을 업데이트
                    return; // 다음에 섬에 도착해도 거리는 무조건 더 크기 때문에 탐색 무의미
                }
            }
        }
    }

    int group_num = 0;
    int min_len = Integer.MAX_VALUE;
	public void Solve() {
        visited = new boolean[N][N];
        // 1. 섬 그룹화 하기
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (map[i][j] == 0) continue; // 위치가 바다면 무시
                if (visited[i][j]) continue; // 위치가 도착한 곳이면 무시
                map[i][j] += group_num; // 탐색 시작점에도 그룹번호 부여
                findIsland(i, j); // 섬 그룹화 탐색 시작
                group_num++; // 다음 섬 그룹넘버 생성
            }
        }

        // 2. 섬 끼리 다리놓기 위한 최단거리 찾기
        visited = new boolean[N][N]; // 방문배열 초기화
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (map[i][j] == 0) continue; // 위치가 바다면 무시
                if (visited[i][j]) continue; // 위치가 도착한 곳이면 무시
                setBridge(i, j, map[i][j]); // 같은 섬의 탐색을 막기 위해 섬번호도 같이 전달함
                visited = new boolean[N][N]; // 다음 탐색을 위한 방문배열 초기화
            }
        }
        System.out.println(min_len);
	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>