BOJ - 2146 ) 다리만들기

 

 

 

---

 

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

2146번: 다리 만들기

---

 

다리만들기 문제는 입력으로 들어온 맵에서 1로만이루어진곳을 섬으로 나누고,

 

나누어진 섬끼리 연결하는 최단경로를 찾는 문제이다.

 

2번의 BFS를 통하여 답을 구할 수 있다.

 

단계적으로

 

1. 맵 나누기

 

2. 맵의 경계를 찾기 ( 중간에서는 실시할 필요가 없다 )

 

3. 경계에서 0 을따라가서 다른섬이 나올때까지 반복한다.

 

4. 섬을 바꾸어서 실행

 

의 4단계를 반복하면된다. 모든섬을 잇는 경로를 찾을 필요는 없으므로, 전체 맵에서 최솟값만을 구한다.

 

 

 

---

package practice;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;


public class BOJ_다리만들기 {
	static int N;
	static int map[][];
	static int dx[]= {0 , 0 , -1, +1};
	static int dy[]= {1, -1, 0 ,0 };
	static int road_max = Integer.MAX_VALUE;
	static class pos{
		
		int x,y;
		int area,len;
		pos(int y,int x){
			this.x =x;
			this.y =y;
		}
		pos(int y,int x,int len){
			this.x =x;
			this.y =y;
			this.len = len;
		}

	}
	public static void SplitMap() {
		int mark = 0;
		Deque<pos> dq = new ArrayDeque<pos>();
		boolean visit[][] = new boolean [N+1][N+1];
		for(int y=0 ; y < N ; y++) {
			for(int x=0; x< N ; x++) {
				if(map[y][x] == 1 && !visit[y][x]) {
					visit[y][x] = true;
					dq.add(new pos(y,x));
					mark++;
					map[y][x] = mark;
					while(!dq.isEmpty()) {
						pos now = dq.poll();
						
						for(int index = 0; index < 4; index++) {
							int nx  = now.x + dx[index];
							int ny =  now.y + dy[index];
							if(nx >= 0 && ny >= 0 && nx <N && ny <N && !visit[ny][nx] && map[ny][nx]==1) {
								visit[ny][nx] = true;
								map[ny][nx] = mark;
								dq.add(new pos(ny,nx));
							}
						}
						
					}
				}
			}
		}
		
	}

	public static void main(String[] args) throws Exception {
		
		input();
		SplitMap();
		Bridge();
		System.out.println(road_max);
	}

	
	public static void Bridge() {
		
		for(int y = 0 ; y < N ; y++) {
			for(int x = 0 ; x < N ; x++) {
				if(map[y][x] !=0) {
					judge(y,x);
				}
			}
		}
	}


	public static void judge(int y, int x) {
		for(int index = 0 ; index < 4 ;index++) {
			int ny = y + dy[index];
			int nx = x + dx[index];
			if(nx >= 0 && ny >= 0 && nx <N && ny <N) {
				if(map[ny][nx] != map[y][x]) {
					// ny nx 0을 가리키고 있음
					// 즉 0 에서 시작해서 map[y][x]가 아닌 다른 숫자가 나올때까지만 bfs실행
					BFS(ny,nx,map[y][x]);
				}
			}
		}
	}


	public static void BFS(int ny, int nx, int start) {
		ArrayDeque<pos> dq = new ArrayDeque<pos>();
		dq.add(new pos(ny,nx,0));
		boolean visit[][] = new boolean[N+1][N+1];
		visit[ny][nx] = true;
		while(!dq.isEmpty()) {
			pos now = dq.poll();
			int x = now.x;
			int y = now.y;
			int len = now.len;
			if(map[y][x] != 0 && map[y][x] != start) {
				road_max = Math.min(road_max, len);
				break;
			}
			for(int index = 0 ; index < 4 ; index++) {
				int next_y= y +dy[index];
				int next_x= x +dx[index];
				if(next_x >=0 && next_y >=0 && next_x < N && next_y < N ) {
					if(map[next_y][next_x] != start && !visit[next_y][next_x]) {
						visit[next_y][next_x] = true;
						dq.add(new pos(next_y,next_x,len+1));
					}
				}
			}		
		}	
	}

	public static void input() throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		for(int y = 0 ; y < N ; y++) {
			st= new StringTokenizer(br.readLine());
			for(int x = 0 ; x < N ; x++) {
				map[y][x] = Integer.parseInt(st.nextToken());
			}
		}	
	}
}

 

---