[BOJ] 17472 다리 만들기 2.java
1.문제
https://www.acmicpc.net/problem/17472
2.코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* Author : YoungSeo Jeon
* Date : 2021-09-17
* Description : 백준 17472
*/
public class Main{
static int N,M;
static int[][] leng;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] board = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
//섬의 번호 붙이기
int num = 2;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(board[i][j] == 1) {
numbering(board, i, j, num);
num++;
}
}
}
num-=2;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(board[i][j] !=0) {
board[i][j]--;
}
}
}
//섬 연결시킬수 있는 다리 길이 저장해보자
//만들수 있는 다리 길이 저장
leng = new int[num+1][num+1];
for(int i=1; i<=num ; i++) {
Arrays.fill(leng[i], 987654321);
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(board[i][j] != 0) {
measure(board,i,j);
}
}
}
//전부 갈수있는지 확인
//갈수있는 배열, 몇번째 섬인지, 현재까지 길이, 누적 연결섬갯수
for(int i=0; i<=num; i++) {
for(int j=0; j<=num; j++) {
if(leng[i][j] == 987654321) leng[i][j] = 0;
}
}
//임시 출력
// for(int[] line : leng) {
// for(int n : line) {
// bw.write(n+" ");
// }
// bw.newLine();
// }
// bw.newLine();
int result = visitCheck(leng);
// //임시 출력확인
// for(int[] line : board) {
// for(int n : line) {
// bw.write(n+" ");
// }
// bw.newLine();
// }
// bw.newLine();
if(result!=987654321) {
bw.write(result+"\n");
}else {
bw.write("-1\n");
}
bw.flush();
bw.close();
br.close();
}
static int[] move_y = {1,-1,0,0};
static int[] move_x = {0,0,1,-1};
public static void numbering(int[][] board,int y, int x, int num) {
board[y][x] = num;
for(int i=0; i<4; i++) {
int new_y = y+move_y[i];
int new_x = x+move_x[i];
if(new_y < 0 || new_y>=N || new_x<0 || new_x>=M) continue;
if(board[new_y][new_x] == 1) {
numbering(board,new_y,new_x,num);
}
}
}
//다리 최소 길이 측정
public static void measure(int[][] board, int y, int x) {
//4방향 0 인지 탐색
for(int i=0; i<4; i++) {
int new_y = y+move_y[i];
int new_x = x+move_x[i];
int len = 0;
if(new_y < 0 || new_y>=N || new_x<0 || new_x>=M || board[new_y][new_x]!=0) continue;
while(true) {
new_y += move_y[i];
new_x += move_x[i];
len++;
if(new_y < 0 || new_y>=N || new_x<0 || new_x>=M) break;
if(board[new_y][new_x]!=0) {
if(len==1) break;
leng[board[y][x]][board[new_y][new_x]] = Math.min(len, leng[board[y][x]][board[new_y][new_x]]);
leng[board[new_y][new_x]][board[y][x]] = Math.min(len, leng[board[y][x]][board[new_y][new_x]]);
break;
}
}
}
}
//갈수있는 배열
public static int visitCheck(int[][] leng) {
int N = leng.length-1;
int[] len = new int[N+1];
Arrays.fill(len,987654321);
boolean[] visited = new boolean[N+1];
len[1] = 0;
int result = 0;
for(int i=0; i<N; i++) {
//최솟값 찾기
int min = 987654321;
int curr = 0;
for(int j=1; j<=N; j++) {
if(!visited[j] && min>len[j]) {
min = len[j];
curr = j;
}
}
if(min == 987654321) return min;
result += min;
visited[curr] = true;
for(int j=1; j<=N; j++) {
if(!visited[j] && leng[curr][j]!=0 && len[j] > leng[curr][j]) {
len[j] = leng[curr][j];
}
}
}
return result;
}
}
3.Review
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* Author : YoungSeo Jeon
* Date : 2021-09-17
* Description : 백준 17472
*/
public class Main{
static int N,M;
static int[][] leng;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] board = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
//섬의 번호 붙이기
int num = 2;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(board[i][j] == 1) {
numbering(board, i, j, num);
num++;
}
}
}
num-=2;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(board[i][j] !=0) {
board[i][j]--;
}
}
}
//섬 연결시킬수 있는 다리 길이 저장해보자
//만들수 있는 다리 길이 저장
leng = new int[num+1][num+1];
for(int i=1; i<=num ; i++) {
Arrays.fill(leng[i], 987654321);
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(board[i][j] != 0) {
measure(board,i,j);
}
}
}
//전부 갈수있는지 확인
//갈수있는 배열, 몇번째 섬인지, 현재까지 길이, 누적 연결섬갯수
for(int i=0; i<=num; i++) {
for(int j=0; j<=num; j++) {
if(leng[i][j] == 987654321) leng[i][j] = 0;
}
}
//임시 출력
// for(int[] line : leng) {
// for(int n : line) {
// bw.write(n+" ");
// }
// bw.newLine();
// }
// bw.newLine();
int result = visitCheck(leng);
// //임시 출력확인
// for(int[] line : board) {
// for(int n : line) {
// bw.write(n+" ");
// }
// bw.newLine();
// }
// bw.newLine();
if(result!=987654321) {
bw.write(result+"\n");
}else {
bw.write("-1\n");
}
bw.flush();
bw.close();
br.close();
}
static int[] move_y = {1,-1,0,0};
static int[] move_x = {0,0,1,-1};
public static void numbering(int[][] board,int y, int x, int num) {
board[y][x] = num;
for(int i=0; i<4; i++) {
int new_y = y+move_y[i];
int new_x = x+move_x[i];
if(new_y < 0 || new_y>=N || new_x<0 || new_x>=M) continue;
if(board[new_y][new_x] == 1) {
numbering(board,new_y,new_x,num);
}
}
}
//다리 최소 길이 측정
public static void measure(int[][] board, int y, int x) {
//4방향 0 인지 탐색
for(int i=0; i<4; i++) {
int new_y = y+move_y[i];
int new_x = x+move_x[i];
int len = 0;
if(new_y < 0 || new_y>=N || new_x<0 || new_x>=M || board[new_y][new_x]!=0) continue;
while(true) {
new_y += move_y[i];
new_x += move_x[i];
len++;
if(new_y < 0 || new_y>=N || new_x<0 || new_x>=M) break;
if(board[new_y][new_x]!=0) {
if(len==1) break;
leng[board[y][x]][board[new_y][new_x]] = Math.min(len, leng[board[y][x]][board[new_y][new_x]]);
leng[board[new_y][new_x]][board[y][x]] = Math.min(len, leng[board[y][x]][board[new_y][new_x]]);
break;
}
}
}
}
//갈수있는 배열
public static int visitCheck(int[][] leng) {
int N = leng.length-1;
int[] len = new int[N+1];
Arrays.fill(len,987654321);
boolean[] visited = new boolean[N+1];
len[1] = 0;
int result = 0;
for(int i=0; i<N; i++) {
//최솟값 찾기
int min = 987654321;
int curr = 0;
for(int j=1; j<=N; j++) {
if(!visited[j] && min>len[j]) {
min = len[j];
curr = j;
}
}
if(min == 987654321) return min;
result += min;
visited[curr] = true;
for(int j=1; j<=N; j++) {
if(!visited[j] && leng[curr][j]!=0 && len[j] > leng[curr][j]) {
len[j] = leng[curr][j];
}
}
}
return result;
}
}
여러가지 기법들이 적용된다...
처음에는 프림이 아니라 플로이드를 적용했었는데
모든것을 지나가는 길을 체크할 방법이 없었다.
그래서 프림으로 재구현하였다.
Author And Source
이 문제에 관하여([BOJ] 17472 다리 만들기 2.java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hakka_ame/BOJ-17472-다리-만들기-2.java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)