https://www.acmicpc.net/problem/2146
다리 만들기
문제
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.
위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.
물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
입력
첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
출력
첫째 줄에 가장 짧은 다리의 길이를 출력한다.
예제 입력 1 복사
10
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
예제 출력 1 복사
3풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N; // 지도크기
static int[][] A;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int num = 1; // 육지번호
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()); // 지도크기
A = new int[N][N]; // 지도배열
visited = new boolean[N][N]; // 방문배열
// 지도 정보 입력받기
StringTokenizer st;
for (int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
for (int j=0; j<N; j++){
A[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1. 섬 구분해서 번호 붙이기
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
if (!visited[i][j] && A[i][j]!=0){
labelIsland(i,j); // 같은 육지 탐색 (BFS탐색하면서 육지번호 붙여줌)
num++; // 육지번호 증가(변경)
}
}
}
// 2. 섬마다 BFS 돌려서 최소 다리 길이 찾기
int min = Integer.MAX_VALUE; // 다리길이 최솟값
for (int n=2; n<num; n++){
min = Math.min(min, bridgeBFS(n));
}
System.out.println(min);
}
private static void labelIsland(int i, int j){
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {i, j});
A[i][j] = num; // 시작좌표 육지번호 붙여주기
while (!q.isEmpty()){
int[] now = q.poll();
visited[now[0]][now[1]] = true; // 현재좌표 방문처리
for (int k=0;k<4; k++){ // 현재좌표 상하좌우 탐색
int nx = now[0] + dx[k];
int ny = now[1] + dy[k];
if (isIn(nx, ny)&&!visited[nx][ny]){
// 상하좌우 탐색좌표가 유효하고, 방문한적 없다면
visited[nx][ny] = true; // 방문체크
if (A[nx][ny]!=0) {
A[nx][ny] = num; // 육지번호 붙여주기
q.offer(new int[]{nx, ny}); // 큐에 탐색좌표 넣기
}
}
}
}
}
private static int bridgeBFS(int islandNum){
Queue<int[]> q = new LinkedList<>();
int[][] dist = new int[N][N];
boolean[][] visited = new boolean[N][N];
// 섬 테두리 찾기
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
if (A[i][j] == islandNum){
for (int n=0; n<4; n++){
int nx = i + dx[n];
int ny = j + dy[n];
if (isIn(nx,ny) && A[nx][ny] == 0){
q.offer(new int[] {i, j});
visited[i][j] = true;
break;
}
}
}
}
}
// 다리건설
while (!q.isEmpty()){
int[] now = q.poll();
for (int n=0; n<4; n++){
int nx = now[0] + dx[n];
int ny = now[1] + dy[n];
if (isIn(nx,ny) && !visited[nx][ny]){
// 상하좌우 탐색좌표가 유효하고 아직 방문하지 않았다면
// 다른섬에 도착
if (A[nx][ny]!=0 && A[nx][ny]!=islandNum){
return dist[now[0]][now[1]]; // 다리길이 return
}
// 바다면 계속 확장
if (A[nx][ny] == 0){
visited[nx][ny] = true;
dist[nx][ny] = dist[now[0]][now[1]] + 1;
q.offer(new int[] {nx, ny});
}
}
}
}
return Integer.MAX_VALUE;
}
private static boolean isIn(int x, int y){
return x >= 0 && y >= 0 && x < N && y < N;
}
}- BFS를 활용한 문제. 레전더리 어렵다
- 문제접근 방식 :
- 1. BFS로 섬을 구분해서 라벨링을 해준다 (섬 번호 붙이기)
- 2. 섬의 테두리를 구한다
- 3. 테두리에서 다른섬에 닿을때까지의 최솟값을 구한다.
1. 섬 라벨링
Main함수
// 1. 섬 구분해서 번호 붙이기
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
if (!visited[i][j] && A[i][j]!=0){
labelIsland(i,j); // 같은 육지 탐색 (BFS탐색하면서 육지번호 붙여줌)
num++; // 육지번호 증가(변경)
}
}
}- 만약 방문하지 않았고, 육지를 발견하면 BFS 탐색을하면서 같은구역에 존재하는 섬에 육지번호를 붙여준다.
- BFS문 하나에서 하나로 이루어진 섬을 모두 구분하고 빠져나오므로 섬번호인 num을 1증가 시켜준다.
- 최종적으로 for문을 빠져나오면 num-1은 육지의 개수이다.
labelIsland: 라벨링 BFS
private static void labelIsland(int i, int j){
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {i, j});
A[i][j] = num; // 시작좌표 육지번호 붙여주기
while (!q.isEmpty()){
int[] now = q.poll();
visited[now[0]][now[1]] = true; // 현재좌표 방문처리
for (int k=0;k<4; k++){ // 현재좌표 상하좌우 탐색
int nx = now[0] + dx[k];
int ny = now[1] + dy[k];
if (isIn(nx, ny)&&!visited[nx][ny]){
// 상하좌우 탐색좌표가 유효하고, 방문한적 없다면
visited[nx][ny] = true; // 방문체크
if (A[nx][ny]!=0) {
A[nx][ny] = num; // 육지번호 붙여주기
q.offer(new int[]{nx, ny}); // 큐에 탐색좌표 넣기
}
}
}
}
}
- 현재 좌표의 상,하,좌,우 좌표를 탐색하면서
- 탐색좌표가 유효하고, 아직 방문하지 않았다면 방문체크한다.
- 해당 좌표값이 육지라면 육지번호를 붙여주고, 큐에 탐색좌표를 넣어준다.
2. 섬의 테두리 구하기 -> 연결다리 짓기
Main 함수
// 2. 섬마다 BFS 돌려서 최소 다리 길이 찾기
int min = Integer.MAX_VALUE; // 다리길이 최솟값
for (int n=2; n<num; n++){
min = Math.min(min, bridgeBFS(n));
}
System.out.println(min);
- 섬의 테두리를 찾는다.
- 다리건설 시 섬 내부에서 출발하면 쓸데없는 경로가 생기므로, 바다랑 맞닿은 경계의 육지만 출발점으로 삼아 이걸로 최단거리만 고려할 수 있다.
- 2번 섬부터 num-1까지 bridgeBFS를 수행하면서 최솟값을 비교한다.
bridgeBFS
private static int bridgeBFS(int islandNum){
Queue<int[]> q = new LinkedList<>();
int[][] dist = new int[N][N];
boolean[][] visited = new boolean[N][N];
// 섬 테두리 찾기
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
if (A[i][j] == islandNum){
for (int n=0; n<4; n++){
int nx = i + dx[n];
int ny = j + dy[n];
if (isIn(nx,ny) && A[nx][ny] == 0){
q.offer(new int[] {i, j});
visited[i][j] = true;
break;
}
}
}
}
}- 섬의 테두리를 찾는다.
- 현재좌표가 파라미터로 받은 섬의 번호라면,
- 상,하,좌,우를 탐색하면서 만약 주변 탐색좌표가 바다라면 섬의 경계라는 의미이므로, 현재좌표를 큐에 넣는다.
- 즉 경계좌표만 큐에 넣는 것.
다리건설하기
// 다리건설
while (!q.isEmpty()){
int[] now = q.poll();
for (int n=0; n<4; n++){
int nx = now[0] + dx[n];
int ny = now[1] + dy[n];
if (isIn(nx,ny) && !visited[nx][ny]){
// 상하좌우 탐색좌표가 유효하고 아직 방문하지 않았다면
// 다른섬에 도착
if (A[nx][ny]!=0 && A[nx][ny]!=islandNum){
return dist[now[0]][now[1]]; // 다리길이 return
}
// 바다면 계속 확장
if (A[nx][ny] == 0){
visited[nx][ny] = true;
dist[nx][ny] = dist[now[0]][now[1]] + 1;
q.offer(new int[] {nx, ny});
}
}
}
}- 큐에서 꺼낸 경계 좌표의 상,하,좌,우를 탐색한다.
- 탐색좌표가 유효하고 아직 방문하지 않았다면
- 탐색좌표가 섬이면서 파라미터로 받은 현재 섬이 아니라면(다른 섬에 도착했다면)
- 다리길이를 return 한다.
- 바다면 계속해서 확장해나간다.
- dist[탐색좌표]값에 해당하는 데이터에 dist[현재좌표]+1 값을 넣는다.
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준 2583] 영역 구하기 (Java) - BFS (0) | 2025.04.26 |
|---|---|
| [백준 16922] 로마 숫자 만들기 (Java) - DFS, 백트래킹 (0) | 2025.04.25 |
| [백준 1316] 그룹 단어 체커 (Java) - 구현 (0) | 2025.04.23 |
| [백준 2579] 계단 오르기 (Java) - 다이나믹 프로그래밍 (1) | 2025.04.22 |
| [백준 1003] 피보나치 함수 (Java) - 다이나믹 프로그래밍 (0) | 2025.04.21 |