[알고리즘] 백준 다리만들기 2146번 JAVA(자바)

[알고리즘] 백준 다리만들기 2146번 JAVA(자바)

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

import java.util.*; import java.io.*; public class Main_2146 { static int N; static int [][]map; static boolean [][]mapVisited; static boolean [][]groupVisited; static int [][]group; static int mapStart; public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub //File file = new File("./input.txt"); ///FileReader fr = new FileReader(file); //BufferedReader br = new BufferedReader(fr); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); map = new int[N][N]; group = new int [N][N]; groupVisited = new boolean[N][N]; int []d_x = {1,-1,0,0}; int []d_y = {0,0,-1,1}; int routeMin =0; //초기화 for(int i=0; i q = new LinkedList(); if(map[i][j] == 1) { //육지와 바다가 연결된 부분을 찾았을 경우 다른 섬이랑 최단 거리를 찾는다. mapVisited = new boolean[N][N]; findSea(d_y,d_x,i,j,q); if(q.isEmpty() == false ) { while(q.isEmpty() == false) { Info info = q.poll(); int y = info.y; int x = info.x; int route = info.route; if(routeMin != 0 && route>=routeMin)continue; // System.out.println("now y : "+ y+" x :" +x); for(int k=0; k<4; k++) { int next_y = y + d_y[k]; int next_x = x + d_x[k]; if(next_y<0 || next_y >=N || next_x <0 || next_x >=N) continue; if(map[next_y][next_x] == 0 && mapVisited[next_y][next_x] == false) { q.add(new Info(next_y,next_x,route+1)); mapVisited[next_y][next_x] = true; } else if(map[next_y][next_x] == 1 && group[next_y][next_x] != mapStart) { //System.out.println("find route "+next_y+ " " + next_x); if(routeMin == 0)routeMin = route; else routeMin = Math.min(routeMin, route); } } } } } } } System.out.println(routeMin); br.close(); } public static void groupIsland(int[] d_y, int[] d_x) { Queue q; int color = 1; for(int i=0; i(); q.add(new Info(i,j,0)); group[i][j] = color; groupVisited[i][j] = true; while(q.isEmpty() == false) { Info info = q.poll(); int y = info.y; int x = info.x; for(int k=0; k<4; k++) { int next_y = y + d_y[k]; int next_x = x + d_x[k]; if(next_y<0 || next_y >=N || next_x <0 || next_x >=N) continue; if(map[next_y][next_x] == 1 && groupVisited[next_y][next_x] == false) { q.add(new Info(next_y,next_x,0)); group[next_y][next_x] = color; groupVisited[next_y][next_x] = true; } } }//while end color++; } } } } //매개변수로 받은 x,y 주변에 바다가 있는지 탐색한다. public static void findSea(int[] d_y, int[] d_x, int y, int x, Queue q) { int next_y; int next_x; for(int i=0; i<4; i++) { next_y = y + d_y[i]; next_x = x + d_x[i]; if(next_y<0 || next_y >=N || next_x <0 || next_x >=N) continue; if(map[next_y][next_x] == 0) { mapStart = group[y][x]; //시작 섬의 그룹 id를 지정해준다. q.add(new Info(next_y,next_x,1)); mapVisited[next_y][next_x] = true; } } } public static void printIslandGroup() { for(int i=0; i

주어진 N개의 섬 중에서 2개를 이어주는 가장 짧은 다리를 찾는 문제이다.

과정 1.

다리를 연결할때 같은 섬을 연결하면 안되기 때문에

groupIsland(d_y,d_x)

함수로 섬 별로 번호를 매겼다.

printIslandGroup() 로 확인 가능하다.

과정 2.

findSea(d_y,d_x,i,j,q) 를 통해 x,y의 상하좌우에 육지와 바다가 만나는 곳의 위치를 찾아서 q 변수에 저장해둔다.

과정3.

q가 비어있지 않다면 다른 섬과 연결된 최단 경로를 찾는다.

느낀점

코드를 작성할 당시엔 가독성이 좋다고 생각했지만 시간이 지나고 다시 봤을 땐 함수명이라던지 흐름이 좋지 않았던거 같다.

다음엔 좀 더 신경을 쓰며 코드를 작성해야 할 것 같다.

from http://yourknow.tistory.com/23 by ccl(S) rewrite - 2021-11-04 21:01:17