on
[java 백준] 골드 3/ 2146번 다리 만들기
[java 백준] 골드 3/ 2146번 다리 만들기
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;
public static int [][] arr;
public static int [][] distance;
public static int [][] group;
public static int [] dirx = { 1 , - 1 , 0 , 0 };
public static int [] diry = { 0 , 0 , 1 , - 1 };
public static class Dot {
int x;
int y;
public Dot( int x, int y) {
this .x = x;
this .y = y;
}
}
public static void grouping( int i, int j, int cnt) {
Queue < Dot > queue = new LinkedList < Dot > ();
queue. add ( new Dot(i, j));
while ( ! queue.isEmpty()) {
Dot d = queue.remove();
int x = d.x;
int y = d.y;
for ( int k = 0 ; k < 4 ; k + + ) {
int nx = x + dirx[k];
int ny = y + diry[k];
if (nx > = 0 & & nx < n & & ny > = 0 & & ny < n) {
if (arr[nx][ny] = = 1 & & group[nx][ny] = = 0 ) { // 중요!
group[nx][ny] = cnt;
queue. add ( new Dot(nx, ny));
}
}
}
}
}
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());
arr = new int [n][n];
distance = new int [n][n];
group = new int [n][n];
// input
for ( int i = 0 ; i < n; i + + ) {
st = new StringTokenizer(br.readLine());
for ( int j = 0 ; j < n; j + + ) {
arr[i][j] = Integer. parseInt (st.nextToken());
}
}
// group
int cnt = 0 ;
for ( int i = 0 ; i < n; i + + ) {
for ( int j = 0 ; j < n; j + + ) {
if (arr[i][j] = = 1 & & group[i][j] = = 0 ) {
group[i][j] = + + cnt;
grouping(i, j, cnt);
}
}
}
// distance
Queue < Dot > queue = new LinkedList < Dot > ();
for ( int i = 0 ; i < n; i + + ) {
for ( int j = 0 ; j < n; j + + ) {
distance[i][j] = - 1 ;
if (arr[i][j] = = 1 ) {
queue. add ( new Dot(i, j));
distance[i][j] = 0 ;
}
}
}
while ( ! queue.isEmpty()) {
Dot d = queue.remove();
int x = d.x;
int y = d.y;
for ( int k = 0 ; k < 4 ; k + + ) {
int nx = x + dirx[k];
int ny = y + diry[k];
if (nx > = 0 & & nx < n & & ny > = 0 & & ny < n) {
if (distance[nx][ny] = = - 1 ) {
distance[nx][ny] = distance[x][y] + 1 ;
group[nx][ny] = group[x][y];
queue. add ( new Dot(nx, ny)); // 큐 안에 넣어줘야함
}
}
}
}
int answer = Integer.MAX_VALUE;
for ( int i = 0 ; i < n; i + + ) {
for ( int j = 0 ; j < n; j + + ) {
for ( int k = 0 ; k < 4 ; k + + ) {
int x = i + dirx[k];
int y = j + diry[k];
if (x > = 0 & & x < n & & y > = 0 & y < n) {
if (group[x][y] ! = group[i][j]) {
answer = Math.min(answer, distance[i][j] + distance[x][y]);
}
}
}
}
}
System . out . println (answer);
}
}
from http://we1cometomeanings.tistory.com/172 by ccl(A) rewrite - 2021-10-13 15:27:15