[백준] 2146 다리 만들기 - BFS(너비우선탐색) JAVA

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

2146번: 다리 만들기

코드설명

BFS 문제입니다.

 

문제로직입니다.

1. 섬을 번호 매깁니다. 지도를 순회하며 육지를 발견하면 해당 섬에 번호를 매깁니다. 이때, BFS를 사용하여 같은 섬에 속하는 모든 육지에 같은 번호를 부여합니다.
2. 섬 간의 최단 다리 길이를 구합니다. 한 섬에서 시작하여 BFS를 사용하여 다른 섬을 찾습니다. 이때, 방문한 섬은 다시 방문하지 않도록 visited 배열을 사용합니다. 다른 섬을 찾으면 최단 다리 길이를 갱신하고 종료합니다.

 

처음에는 단순히 이렇게 BFS를 실행하여 찾을경우 시간초과가 나지 않을까하여 더 고민해보았지만, 떠오르즈 읺아 그냥 BFS로 구현했습니다 N의 범위가 100까지이기에 시간초과가 걸리지 않습니다.

코드

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 {
	
	public static int N, M;
	public static int[][] map;
	public static int[][] Indexing;
	public static boolean[][] visited;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int idx = 1;
	public static int answer = Integer.MAX_VALUE;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());

    	N = Integer.parseInt(st.nextToken());
    	map = new int[N][N];
    	Indexing = new int[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(map[i][j]== 1 && Indexing[i][j] == 0) {
    				indexIngMap(new Node(i, j, 0));
    				idx += 1;
    			}
    		}
    	}
    	
    	for(int i=0;i<N; i++) {
    		for(int j=0;j<N;j++) {
    			if(Indexing[i][j] > 0) {
    				connect(new Node(i,  j, 0), Indexing[i][j]);
    			}
    		}
    	}
    	
    	System.out.println(answer - 1);
	}
	public static void indexIngMap(Node start) {
		Queue<Node> q = new LinkedList<>();
		q.offer(start);
		Indexing[start.r][start.c] = idx;
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			for(int dir = 0; dir< 4; dir++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				if(map[nr][nc] != 1) continue;
				if(Indexing[nr][nc] == idx) continue;
				
				Indexing[nr][nc] = idx;
				q.offer(new Node(nr, nc, temp.cnt + 1));
			}
		}
	}
	
	public static void connect(Node start, int currentIdx) { //이미 Indexing인 곳에서 시작한다. 반드시 0 인곳만 거치고 방문처리하며 이동한다.
		Queue<Node> q = new LinkedList<>();
		q.offer(start);
		visited = new boolean[N][N];
		visited[start.r][start.c]= true; 
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			if(Indexing[temp.r][temp.c] > 0 && Indexing[temp.r][temp.c] != currentIdx ) { //만약에 찾았다면 최소거리로 갱신한다. 또한 BFS 이기에 한번 나온경우 더이상 최단거리가 나올 수 없다.
				answer = Math.min(answer, temp.cnt);
				return ;
			}
			for(int dir = 0; dir< 4; dir++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				if(Indexing[nr][nc] == currentIdx) continue; //만약 시작했던 섬이라면 해당 방향으로 이동하지않음.
				if(visited[nr][nc] == true) continue; //만약 이미 방문한곳이라면 중단.
				
				visited[nr][nc] = true;
				q.offer(new Node(nr, nc, temp.cnt + 1));
			}
		}
	}
	
}

class Node{
	int r;
	int c;
	int cnt;
	public Node(int r, int c, int cnt) {
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
}