(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에 저장한다.

 

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

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

 

 

 

 

 

 

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

 

소스코드 참고 바랍니다.

 

 

감사합니다!!

 

소스코드

---