[백준 2146] 다리 만들기

[문제 바로가기]👇

2146번: 다리 만들기

💡풀이💡

한 섬에서 다른 섬으로 최소의 거리를 가진 다리 놓기!

• 출발하는 섬과 도착하는 섬이 달라야 하고, 이를 판단할 수 있어야 함! >> 섬 별로 번호 붙이기
• 한 섬에서 출발해서 다른 섬까지 도착하는 최소 거리 재기 >> BFS로 최소 찾기

 

1. 입력 받기

		static int[] dr = {-1,0,1,0}; // 상우하좌
    static int[] dc = {0,1,0,-1}; // 상우하좌
    
    static int N, min;
    static boolean[][] v; // 방문 확인
    static int[][] map; // 지도 정보
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

 

2. 섬에 번호 붙이기

출발하는 섬과 도착하는 섬이 달라야 하고, 이를 판단하기 위해 섬에 번호를 붙이기

• 섬은 상하좌우로 연결되어 있기 때문에 상하좌우 4방향 탐색을 해서 연결되어 있는 곳은 같은 번호 붙이기
• 한 번의 BFS 탐색이 끝나면(연결 되어 있는 모든 곳을 다 탐색하면) 다음 연결되어 있는 곳을 찾기(다음 섬 찾기)

v = new boolean[N][N];
int num = 2;
for(int i=0; i<N; i++) {
	for(int j=0; j<N; j++) {
	  if(map[i][j]==1) {
      bfsNum(i, j, num);
      num++;
    }
	}
}

static void bfsNum(int i, int j, int num) {
	ArrayDeque<int[]> q = new ArrayDeque<>();
  v[i][j] = true;
  q.offer(new int[] {i,j});
  map[i][j] = num;
        
  while(!q.isEmpty()) {
    int[] pos = q.poll();
            
     for(int d=0; d<4; d++) {
        int ni = pos[0] + dr[d];
        int nj = pos[1] + dc[d];
                
         if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj] && map[ni][nj]==1) {
             v[ni][nj] = true;
             q.offer(new int[] {ni,nj});
             map[ni][nj] = num;
        }
     }
   }
}

 

3. 다리 놓는 최소값 찾기

BFS로 한 섬에서 출발해서 섬에 도착할 때까지 BFS의 깊이 구하기

• BFS의 깊이가 최소 다리 길이가 됨!

이때 BFS 탐색을 시작하는 섬(출발하는 섬)의 번호를 같이 넘겨줘서 도착한 섬이 출발한 섬과 다르면 최소값 구하기

• 최소값을 구하면 큐에 남아 있는 나머지 경로 탐색을 할 필요가 x
• queue를 모두 비우고 리턴해서 해당 위치에서의 다리 놓기 탐색 종료

// 다리 놓기 - 다리 최소값 찾기
min = Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
  v = new boolean[N][N];
  for(int j=0; j<N; j++) {
      if(!v[i][j] && map[i][j]>1) {
          bfsBridge(i, j, map[i][j]);
      }
  }
}
System.out.println(min);

static void bfsBridge(int i, int j, int start) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        v[i][j] = true;
        q.offer(new int[] {i,j});
        
        int size=0, depth=0; // BFS의 깊이가 결국 최소 다리 길이
        while(!q.isEmpty()) {
            size = q.size();
            
            while(size > 0) {
                int[] pos = q.poll();
                
                for(int d=0; d<4; d++) {
                    int ni = pos[0] + dr[d];
                    int nj = pos[1] + dc[d];
                    
                    // 범위 안에 있고, 방문하지 않았으면
                    if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj]) {
                        // 섬이고, 출발한 섬과 다른 섬이면
                        if(map[ni][nj] != 0 && start != map[ni][nj] ) {
                            min = Math.min(min, depth);
                            q.clear();
                            return;
                        }
                        else if(map[ni][nj] ==0) { // 바다이면 큐에 추가
                            v[ni][nj] = true;
                            q.offer(new int[] {ni,nj});
                        }
                    }
                }
                size--;
            }
            depth++;
        }
}

 

📌놓쳤던 부분

처음에는 시작하는 섬의 위치를 start 변수에 담고 바다에서 출발해서 다른 섬에 도착하게끔 구현을 했다. 이 경우에 2중 루프로 j가 계속 바뀌기 때문에 바다인데도 섬이라고 생각해서 거리를 계산하는 경우가 있었다. 그래서 출발을 바다가 아니라 섬 일 때만 가능하도록 바꿈

 

잘못된 코드

// 다리 놓기 - 다리 최소값 찾기
min = Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
	int start = 0; // 출발하는 섬 번호 저장
	v = new boolean[N][N];
	for(int j=0; j<N; j++) {
		if(map[i][j]>1) start = map[i][j]; // 섬이면 섬 번호 저장
				
		// 방문하지 않았고, 현재 바다이고, 출발 섬이 바다가 아니면
		if(!v[i][j] && map[i][j]==0 && start!=0) { 
			bfsBridge(i, j, start);
		}
	}
}

 

4. 전체 코드

package M02_4;

import java.io.*;
import java.util.*;

public class B2146 {
    static int[] dr = {-1,0,1,0}; // 상우하좌
    static int[] dc = {0,1,0,-1}; // 상우하좌
    
    static int N, min;
    static boolean[][] v;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        
				// 지도 정보 받기
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 섬 번호 붙이기
        v = new boolean[N][N];
        int num = 2;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j]==1) {
                    bfsNum(i, j, num);
                    num++;
                }
            }
        }
        
        // 다리 놓기 - 다리 최소값 찾기
        min = Integer.MAX_VALUE;
        for(int i=0; i<N; i++) {
            v = new boolean[N][N];
            for(int j=0; j<N; j++) {
                if(!v[i][j] && map[i][j]>1) {
                    bfsBridge(i, j, map[i][j]);
                }
            }
        }
        System.out.println(min);
    }
    
    static void bfsNum(int i, int j, int num) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        v[i][j] = true;
        q.offer(new int[] {i,j});
        map[i][j] = num;
        
        while(!q.isEmpty()) {
            int[] pos = q.poll();
            
            for(int d=0; d<4; d++) {
                int ni = pos[0] + dr[d];
                int nj = pos[1] + dc[d];
                
                if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj] && map[ni][nj]==1) {
                    v[ni][nj] = true;
                    q.offer(new int[] {ni,nj});
                    map[ni][nj] = num;
                }
            }
        }
    }
    
    static void bfsBridge(int i, int j, int start) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        v[i][j] = true;
        q.offer(new int[] {i,j});
        
        int size=0, depth=0;
        while(!q.isEmpty()) {
            size = q.size();
            
            while(size > 0) {
                int[] pos = q.poll();
                
                for(int d=0; d<4; d++) {
                    int ni = pos[0] + dr[d];
                    int nj = pos[1] + dc[d];
                    
                    // 범위 안에 있고, 방문하지 않았으면
                    if(0<=ni&&ni<N && 0<=nj&&nj<N && !v[ni][nj]) {
                        // 섬이고, 출발한 섬과 다른 섬이면
                        if(map[ni][nj] != 0 && start != map[ni][nj] ) {
                            min = Math.min(min, depth);
                            q.clear();
                            return;
                        }
                        else if(map[ni][nj] ==0) { // 바다이면 큐에 추가
                            v[ni][nj] = true;
                            q.offer(new int[] {ni,nj});
                        }
                    }
                }
                size--;
            }
            depth++;
        }
    }
}