알고리즘 문제 해결(PS)/[백준]

[백준] 2146번 다리 만들기 (자바 풀이)

연구소장 J 2022. 3. 4. 11:07

문제

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

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

 

풀이

나는 이 문제를 조금 복잡하게 푼 것 같다. BFS를 두 개의 함수로 만들어 해결하였다. 아래와 같은 과정으로 해결하였다.

 

1. BFS를 통해 모든 섬을 찾고, 섬을 구별하기 위해 섬의 숫자를 1,2,3,4... 등으로 바꾼다. 또한 모든 섬의 가장자리를 따로 저장한다.

 

2. 따로 저장한 섬의 가장자리에서 BFS를 통해 다른 섬 까지의 최단거릴 구해서 갱신한다.

 

3. 최단거리를 출력한다.

 

코드

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

public class Baekjoon_2146 {
	static int N,ans=Integer.MAX_VALUE;
	static int map[][];
	static ArrayList<Point> edges = new ArrayList<>();
	static boolean visited[][];
	static int dx[]= {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visited = new boolean[N][N];
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int num = 1;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j] && map[i][j]==1) {
					findIsland(i,j,num++);
				}
			}
		}
		
		for(Point edge : edges ) {
			findBridge(edge.x,edge.y,map[edge.x][edge.y]);
		}
		
		System.out.println(ans);
	}
	
	/* 섬을 모두 찾고, 가장자리를 찾는 함수 */
	public static void findIsland(int x, int y, int num) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x,y,0));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Point cur = q.poll();
			map[cur.x][cur.y] = num;	// 섬의 숫자를 1,2,3....으로 변경
			boolean flag = false;
			for(int i=0; i<4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				if(nx<0 || ny <0 || nx >=N || ny >=N) continue;
				
				/* 가장자리 추가 */
				if(!flag && map[nx][ny] == 0) {
					edges.add(cur);
					flag = true;
				}
				
				if(!visited[nx][ny] && map[nx][ny] == 1) {
					visited[nx][ny] = true;
					q.add(new Point(nx,ny,0));
				}
			}
		}
	}
	
	/* 최단거리 다리 구하기 */
	public static void findBridge(int x, int y, int num) {
		visited = new boolean[N][N];
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x,y,0));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Point cur = q.poll();
			
			if(cur.cnt >= ans) return; 
			
			for(int i=0; i<4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				if(nx<0 || ny <0 || nx >=N || ny >=N) continue;
				
				/* 다른 섬의 가장자리를 만난다면 */
				if(map[nx][ny] != num && map[nx][ny] != 0) {
					ans = Math.min(ans, cur.cnt);
					return;
				}
				
				if(!visited[nx][ny] && map[nx][ny] == 0) {
					visited[nx][ny] = true;
					q.add(new Point(nx,ny, cur.cnt+1));
				}
			}
		}
	}
		
	static class Point{
		int x;
		int y;
		int cnt;
		Point(int x, int y, int cnt){
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}

}

 

결과

백준 2146

통과하긴 했지만, 매우 비효율적이다. 차라리 섬의 가장자리를 구한다음, BFS를 한 번 더 할게 아니라 섬의 가장자리끼리의 좌표의 차이로 거리만 계산했다면 더 효율적이였을 것 같다.

 

반응형