오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다.
https://www.acmicpc.net/problem/2146
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
이 문제는 엄청 어렵게 느껴지진 않았다. 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
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
이제 문제를 보도록 하자. 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를 연습해 보기 좋은 문제다. 자주 나오는 유형이므로 꼭 익숙하게 만들고 넘어가도록 하자!
'Computer Sci. > Algorithms' 카테고리의 다른 글
| [킥스타트] Google Kick Start 2020 Round A 문제 풀이 (0) | 2020年10月07日 |
|---|---|
| 백준 3012 / 올바른 괄호 문자열 / DP, 분할 탐색 / JAVA / 플레티넘 3 (0) | 2020年09月15日 |
| 백준 1701 / Cubeditor / 문자열, KMP / JAVA (1) | 2020年08月14日 |
| 백준 1202 / 보석 도둑 / 그리디, 우선순위 큐 / JAVA (0) | 2020年07月06日 |
| 백준 1507 / 플로이드 와셜(Floyd Warshall) 알고리즘 / JAVA (0) | 2020年06月24日 |