(JAVA) 백준 2146번 : 다리 만들기

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

2146번: 다리 만들기

 

 

 

DFS와 BFS를 섞은 문제

 

하지만 필자는 DFS만 사용했다. (다른 사람들보다 성능은 조금 떨어진다..)

 

 

 

이 문제는

 

가장 짧은 다리 길이 를 구하는 문제이다.

 

그래서 필자가 푼 이 방법은

 

 

붙어있는 육지들 중 가장자리 육지들의 좌표값들만 별도 저장해뒀다가

 

붙어있는 육지 별로 1:1 매칭하여 x, y 차를 구한다.

 

x, y 차란

 

두 개의 육지 P1, P2가 존재할 때

 

 

gapX = Math.abs(P1.x - P2.x) // 절댓값 씌워야함

gapY = Math.abs(P1.y - P2.y)

 

 

이고,

 

이 gapX + gapY  가 다리의 길이가 된다.

 

위와 같은 Map이 주어졌을 때,

 

육지의 가장자리 (5, 8) 과 (4, 5) 사이에 놓을 수 있는 다리의 최소 길이는

 

 

x : 5 - 4 = 1

y : 8 - 5 = 3

x + y(gap) = 4

 

 

가 되고, 마지막 한 칸인 육지를 제외하면

 

길이가 3인 다리가 최소 길이가 된다.

 

 

 

이를 활용하여 문제를 해결했다!

 

 

매커니즘

---

  0.  입력값을 받아 2차원 int 배열에 저장(map)

 

  1.  DFS 시작. (2중 for문)

 

  2.  map에서 값이 1(육지) 인 경우 + boolean visited[][] 값이 false이면 (아직 방문하지 않은 육지) DFS로 해당 육지 방문

  

  3.  상-하-좌-우 4방향으로 좌표값 이동하며 DFS 탐색 진행.

       => 여기서 이동한 좌표의 map 값이 0인 경우에는 이동 전 육지가 바다를 끼고 있다는 뜻이고,

            이 말은 즉슨, 이 육지는 가장자리라는 뜻이다. 

       => 그랬을 때, 이 육지의 x,y 좌표를 별도의 List에 저장한다.

 

*** 연결된 육지들 덩어리 하나하나 구분지어야 한다.

그렇지 않으면 같은 덩어리 육지 내 가장자리끼리 다리를 놓을수도 있다..(?)

 

 

 

 

 

 

이해가 되지 않는 부분들은 댓글 달아주시고

 

소스코드 참고 바랍니다.

 

 

감사합니다!!

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.List;
	import java.util.StringTokenizer;
	// 2146 : 다리 만들기
	public class p2146 {
	static int[][] map;
	static boolean[][] visited;
	static List<ArrayList<Point>> list;
	static int[] moveX = { 0, 1, 0, -1 };
	static int[] moveY = { -1, 0, 1, 0 };
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.valueOf(st.nextToken());
	map = new int[n][n];
	visited = new boolean[n][n];
	list = new ArrayList<ArrayList<Point>>();
	// 맵 그리기
	for(int i = 0; i < n; i++) {
	st = new StringTokenizer(br.readLine());
	for(int j = 0; j < n; j++) {
	int place = Integer.valueOf(st.nextToken());
	map[i][j] = place;
	}
	}
	// DFS
	for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
	if(!visited[i][j] && map[i][j] == 1) {
	list.add(dfs(j, i, n, new ArrayList<Point>()));
	}
	}
	}
	// 다리 최단 길이 찾기
	int min = Integer.MAX_VALUE;
	int len = list.size();
	// for(Point p : list) {
	// System.out.println(p.x + " , " + p.y);
	// }
	// 다리 최소 길이 찾기
	for(int i = 0; i < len - 1; i++) {
	ArrayList<Point> list1 = list.get(i);
	for(int j = i + 1; j < len; j++) {
	ArrayList<Point> list2 = list.get(j);
	for(int a = 0; a < list1.size(); a++) {
	Point p1 = list1.get(a);
	for(int b = 0; b < list2.size(); b++) {
	Point p2 = list2.get(b);
	int gapX = Math.abs(p1.x - p2.x);
	int gapY = Math.abs(p1.y - p2.y);
	min = Math.min(min, Math.abs(gapX + gapY - 1));
	}
	}
	}
	}
	System.out.println(min);
	}
	// 붙어있는 육지 찾기 + 표면 찾기
	static ArrayList<Point> dfs(int x, int y, int n, ArrayList<Point> list) {
	if(visited[y][x]) {
	return null;
	}
	visited[y][x] = true;
	boolean isEdge = false;
	for(int i = 0; i < moveX.length; i++) {
	int nextX = x + moveX[i];
	int nextY = y + moveY[i];
	if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) {
	continue;
	}
	if(map[nextY][nextX] == 0) {
	isEdge = true;
	continue;
	}
	if(!visited[nextY][nextX] && map[nextY][nextX] == 1) {
	dfs(nextX, nextY, n, list);
	}
	}
	if(isEdge) {
	list.add(new Point(x, y));
	}
	return list;
	}
	}
	class Point {
	int x;
	int y;
	Point(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}

view raw p2146.java hosted with ❤ by GitHub