다리만들기 [백준 2146][JAVA][골드3][DFS][컬러링]

 

[광고 누르면 오늘의 행운 상승!!]

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

2146번: 다리 만들기

시간초과를 조심해야하는 DFS문제. 
컬러링과 DFS로 풀었다.

1. 참고사항

- 맵의 섬을 탐색하면서 섬에 번호를 붙여주었다.
- 다른 섬으로 이동하면서 dist배열을 이동수만큼 갱신하여 이동할 곳이 자신의 cnt보다 높다면 전진했다.
- 구해진 ans보다 자신의 cnt가 같거나 높으면 전진하지 않았다.

2. 구현

- 맵을 전부 돌면서 섬에 번호를 붙인다.
- dist배열을 최대값으로 초기화한다.
- 맵을 돌면서 섬이면 그 좌표부터 dfs를 시작한다.
- 자신의 섬이거나 맵을 나가면 continue 
- 자신의 이동거리가 자신이 이동할 거리(dist 배열)보다 낮다면 이동 
- 섬에 도달하면 ans 갱신
- 구해진 ans보다 자신의 cnt가 같거나 높으면 전진하지 않는다.
- 반복
- ans 출력

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

public class Main {
	public static int map[][];
	public static boolean visit[][];
	public static int dist[][];
	public static final int[] dx = {-1,0,1,0}; //북동남서
	public static final int[] dy = {0,1,0,-1};
	public static int islandNum = 1;
	public static int N;
	public static int min = Integer.MAX_VALUE;
	public static void main(String[] args) 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];
		visit = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <N ; j++) {
				if(!visit[i][j] && map[i][j] != 0){
					SetNum(i, j); //번호바꿀 좌표
					islandNum++;
				}
			}
		}
		
		dist = new int[N][N];
		for (int land = 0; land < islandNum; land++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					dist[i][j] = Integer.MAX_VALUE;
				}
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] != 0) {
					FindLoad(map[i][j], i , j, 0); // 자기 섬 번호 전달
				}
			}
		}
		System.out.println(min);
		
	}
	public static boolean CheckIsland(int land, int nx, int ny) {
		return map[nx][ny] == land;
	}
	public static boolean Check(int nx, int ny) {
		return (nx < 0 || nx >= N  || ny < 0  || ny >= N);
	}
	public static void FindLoad(int land, int row, int col, int cnt) {
		if(min <= cnt) return;
		
		for (int i = 0; i < 4; i++) {
			
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			if(Check(nx,ny)) continue;
			if(dist[nx][ny] <= cnt+1) continue;
			
			if(map[nx][ny] == 0) { //0이면 전진
				dist[nx][ny] = cnt + 1;
				FindLoad(land , nx, ny, cnt + 1);
				continue;
			}
			if(CheckIsland(land,nx,ny)) continue;
			else {
				min = Math.min(cnt, min);
				return;
			}
		}
	}
	public static void SetNum(int row, int col) {
		visit[row][col] = true;
		map[row][col] = islandNum; //번호 붙이기;
		for (int i = 0; i < 4; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			if(Check(nx,ny)) continue; 
			if(map[nx][ny] == 0 || visit[nx][ny]) continue; 
			SetNum(nx,ny);
		}
	}
}