백준 2146 / 다리 만들기 / BFS / JAVA / 골드 3

오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다.

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

2146번: 다리 만들기

 

 

이 문제는 엄청 어렵게 느껴지진 않았다. BFS를 익숙하게 쓸 수 있으면 큰 문제 없이 풀 수 있는 문제로 보인다. 다만 BFS를 여러 차례 써야 하는 풀이가 있어서 조금 복잡하게 느껴질 수도 있을 것 같다.

BFS에 대해서 간단하게 설명을 하면, 너비 우선 탐색 방법으로 그래프나 트리를 완전 탐색할 수 있는 방법 중 하나이다. 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 자료구조는 큐를 사용하며 선입선출(FIFO)을 원칙으로 탐색한다. 구체적인 구현 방법에 대해 알고 싶으신 분들은 아래 링크를 하나 걸어놓고 갈테니 참고하시기 바란다.

https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

Breadth First Search or BFS for a Graph - GeeksforGeeks

이제 문제를 보도록 하자. N X N의 배열이 주어지고 섬이 있는 곳은 1, 없는 곳은 0으로 input 값이 들어온다. 나는 이 값을 받는 inputArr 행렬을 하나 만들고, 각 섬들을 그룹화한 groupArr, 섬으로부터의 거리를 나타낸 distArr 이렇게 세 개의 배열을 만들어서 문제를 풀었다. groupArr는 섬을 한 그룹씩 순서대로 인덱싱을 해서 1,2,3, .. 이런식으로 같은 섬은 같은 숫자를 입력해 주었다. 그리고 distArr는 섬인 경우는 초기값을 0으로 나머지는(섬이 아닌 곳) -1로 해서 구분을 해 주었다. (그림에서 빈 칸은 모두 초기값 0이며 생략했다)

 

 

이렇게 만들고 나서 distArr에서 BFS를 통해 모든 점에 대해 섬에서부터 거리가 얼마나 되는지를 계산한다. 섬 위에 있다면 당연히 그 값은 0이다. 그리고 그 섬에서 인접한 값들은 1이고 그 값에서 인접한 값은 2일 것이다. 그런식으로 -1로 초기에 설정된 점들은 섬들로부터 최단거리를 계산해서 그 값을 넣어 준다.

 

 

이렇게 거리를 계산하다보면 인접한 점의 distArr 배열값이 이미 자연수로 정해진 경우가 있다. 그 경우는 값을 갱신해 주지 않는다. 즉, distArr에서 모든 점을 탐색하고 나면 각각의 점은 섬으로부터의 최단 거리가 되는 것이다. 그렇게 계산을 마치면, distArr에서 임의의 한 점과 그 인접한 점의 합이 최소가 되는 점을 찾는다. 그 값이 최단거리가 되는 것이다.

 

 

물론 BFS로 계산을 하는 것이니, 거리가 1인 점들을 다 찾고 그 다음 거리가 2인 점을 찾을 것이다. 즉 값을 입력하는 순서가 거리 오름차순이라는 의미이다. 따라서 인접한 두 점이 발견되면 바로 그 순간 두 섬 사이의 거리를 계산해서 리턴해 주어도 된다.

 

 

내가 제출한 자바 소스코드는 다음과 같다.

BFS를 연습해 보기 좋은 문제다. 자주 나오는 유형이므로 꼭 익숙하게 만들고 넘어가도록 하자!