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

개츠비·2023년 6월 6일

목록 보기

84/84

소요시간 : 30분
문제 사이트 : 백준
문제 수준 : 골드 3
문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
다른 사람의 풀이를 참고 했는가 ? : X
문제 링크 : https://www.acmicpc.net/problem/2146
푼 날짜 : 2023.06.06

1. 사용한 자료구조 & 알고리즘

그래프 이론, 그래프 탐색, BFS, DFS

2. 사고과정

가장 먼저 든 생각은, 각각의 섬들마다 번호를 붙여줘야겠다고 생각했다.
1. 섬들마다 번호를 어떻게 붙여줄 것인가?
👉 DFS를 통해서 붙여준다. map[i][j] 의 숫자가 1이라면, 그 좌표에서 DFS를 수행, 섬의 번호는 2부터 시작해서 각각의 섬들에 번호를 붙여준다.
붙여주었다면 예제 입력의 섬 번호는 다음과 같을 것이다.

2 2 2 0 0 0 0 3 3 3
2 2 2 2 0 0 0 0 3 3
2 0 2 2 0 0 0 0 3 3
0 0 2 2 2 0 0 0 0 3
0 0 0 2 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0
0 0 0 0 4 4 0 0 0 0
0 0 0 0 4 4 4 0 0 0
0 0 0 0 0 0 0 0 0 0

2. 최단거리를 어떻게 구할 것인가?
👉 섬의 번호를 구했으니, 섬의 테두리 부분에서 BFS를 수행. BFS를 하다가 BFS를 시작한 위치의 섬 번호와 다른 번호의 섬을 만날 때마다 최소거리를 갱신하면 될 것이라고 생각했다.

3. 섬의 테두리 부분을 어떻게 구할 것인가?
👉 사실 섬의 테두리 부분을 구했다기 보다는, BFS를 통해 이동하는 좌표는 0 (바다) 이어야만 한다. 섬의 모든 좌표에서 BFS를 수행하되, 다음 노드를 탐색할 때, 시작 노드와 번호가 같다면, 이어서 탐색하지 않음으로써 섬의 중간 부분에서 탐색했을 때 다음 노드로 이어지지 않게 할 수 있다.

3. 풀이과정

DFS를 통해서 섬에 번호를 부여
모든 섬에서 BFS를 수행
시작한 섬의 번호와 다른 경우에만 다음 좌표로 이어서 탐색.
만약, 시작 좌표와 다른 좌표의 섬을 만났다면, 최솟값을 갱신

4. 소스코드

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


public class Main {
	static int map[][];
	static boolean visited[][];
	static int min=Integer.MAX_VALUE;
	static int dy[] = {-1,1,0,0};
	static int dx[] = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();

		int N=Integer.parseInt(br.readLine());

		map=new int[N][N];
		visited=new boolean[N][N];

		for(int i=0;i<map.length;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<map.length;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int number = 2;
		//각각의 섬들마다 번호를 붙여준다 (dfs를 사용). 섬의 번호는 2부터 시작
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				if(map[i][j]==1) {
					dfs(i,j,number++);
				}
			}
		}
		
	
		
		

		//섬의 번호가 2이상이면 bfs를 통해서 다른 섬과의 거리를 구한다
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				if(map[i][j]>1) {
					bfs(i,j,map[i][j]);
				}
			}
		}
		
		System.out.println(min);




	}
	public static void bfs(int y,int x,int number) {
		Queue<Integer[]> queue=new LinkedList<>();
		visited=new boolean[map.length][map.length];
		visited[y][x] = true;
		queue.add(new Integer[] {y,x,0});

		while(!queue.isEmpty()) {
			Integer temp[] = queue.poll();
			int nowY=temp[0];
			int nowX=temp[1];
			int count=temp[2];
			
			//현재 위치가 바다가 아니고, 탐색을 시작한 섬의 번호와 현재 번호가 다르다면
			//최솟값 갱신
			if(map[nowY][nowX]!=0&&map[nowY][nowX]!=number) 
				min=Math.min(min,count-1);
			//count가 최소이상이면, 굳이 탐색할 필요없음. 리턴
			if(count>min)
				return;

			for(int i=0;i<4;i++) {

				int nextY=nowY+dy[i];
				int nextX=nowX+dx[i];
				if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
					continue;
				//다음 번호가 현재 번호와 같다면,continue
				//(우리는 섬의 테두리만을 볼 것이다 ! 섬의 중간지점을 건너뛰기 위해서는 이 작업이 필요)
				//이 작업을 함으로써 다음 지점이 바다와 연결되어 있는 테두리만을 탐색할 수 있다.
				if(map[nextY][nextX]==number)
					continue;
				if(visited[nextY][nextX]) continue;
				
				queue.add(new Integer[] {nextY,nextX,count+1});
				visited[nextY][nextX]=true;
			}

		}



	}

	//다음 번호와 일치한다면, dfs를 계속해서 수행
	public static void dfs(int y,int x,int number) {
		visited[y][x]=true;
		map[y][x]=number;
		for(int i=0;i<4;i++) {
			int nextY=y+dy[i];
			int nextX=x+dx[i];
			if(nextY<0||nextX<0||nextX>=map.length||nextY>=map.length)
				continue;
			if(visited[nextY][nextX]==true||map[nextY][nextX]!=1)
				continue;

			dfs(nextY,nextX,number);
		}
	}

}