https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
🏗️ 설계
- 입력 받을 때 섬인 부분은 -1로 설정해 두고, 이후 BFS를 이용해 섬의 인덱스를 채워주는 방식으로 섬에 번호를 매겨줍니다.
- 섬 이후 바다가 나오는 지점부터 바다가 2개 이상 연결되어 있고, 이후 다시 섬이 나오는 경우들을 탐색하며, 인접 행렬로 섬과 섬 사이의 다리의 길이를 저장하였습니다.
- 다리의 길이를 저장해 둔 인접 행렬을 이용하여 Prim 알고리즘을 이용해 모든 섬들을 연결할 수 있는 최소 신장트리를 구함으로써 다리를 놓을 수 있는 최소 값을 구했습니다.
📋 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_17472 {
private static int rowLen;
private static int colLen;
private static int[][] board;
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private static int[][] bridges;
private static class Pair {
int first;
int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
rowLen = Integer.parseInt(st.nextToken());
colLen = Integer.parseInt(st.nextToken());
board = new int[rowLen][colLen];
// 섬을 입력 받을 때 섬인 부분은 값을 -1로 하여 추후 BFS를 이용해 섬의 번호를 매겨주기
for (int i = 0; i < rowLen; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < colLen; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
if (board[i][j] == 1)
board[i][j] = -1;
}
}
// BFS를 이용해 섬의 번호를 매겨주는 작업
int islandIdx = 0;
for (int i = 0; i < rowLen; i++) {
for (int j = 0; j < colLen; j++) {
if (board[i][j] == -1) {
bfs(i, j, ++islandIdx);
}
}
}
bridges = new int[islandIdx + 1][islandIdx + 1];
// bridge를 구하는 함수
findBridge();
prim(1);
}
private static void findBridge() {
// 각 행별로 탐색
for (int i = 0; i < rowLen; i++) {
// bridgeFlag : 현재 탐색을 시작한 섬의 번호를 저장
// bridgeLength : 탐색을 시작한 섬으로부터 다리의 길이를 저장
int bridgeFlag = 0;
int bridgeLength = 0;
for (int j = 1; j < colLen; j++) {
if (bridgeFlag == 0) {
// 섬에서 바다가 시작되는 지점이라면 bridgeFlag 값을 섬의 번호로 설정 후
// bridgeLength 할당
if (board[i][j - 1] != 0 && board[i][j] == 0) {
bridgeFlag = board[i][j - 1];
bridgeLength = 1;
}
// bridgeFlag 가 0이라면 다리에 관련된 탐색을 진행할 필요가 없으므로 continue;
continue;
}
// 탐색 중인 지점이 바다라면 bridgeLength를 증가
if (board[i][j] == 0) {
bridgeLength++;
} else {
// 섬을 만났을 경우 bridgeLength가 2 이상일 경우에 bridges 행렬에 추가
if (bridgeLength >= 2) {
// 추가할 경우 기존의 값과 비교하여 최솟 값으로 갱신
// 다만 bridges 행렬에 아직 값이 초기화 되지 않은 경우를 방지하기 위해
// 0일 때는 Integer.MAX_VALUE값과 비교하도록 함
bridges[bridgeFlag][board[i][j]] = Math.min(
bridges[bridgeFlag][board[i][j]] == 0 ? 0x7fffffff : bridges[bridgeFlag][board[i][j]],
bridgeLength);
bridges[board[i][j]][bridgeFlag] = Math.min(
bridges[board[i][j]][bridgeFlag] == 0 ? 0x7fffffff : bridges[board[i][j]][bridgeFlag],
bridgeLength);
}
// 다리에 대한 탐색이 끝났으므로 bridgeFlag, bridgeLength값 초기화
bridgeFlag = 0;
bridgeLength = 0;
}
}
}
// 각 열에 대해서도 위와 동일하게 수행
for (int i = 0; i < colLen; i++) {
int bridgeFlag = 0;
int bridgeLength = 0;
for (int j = 1; j < rowLen; j++) {
if (bridgeFlag == 0) {
if (board[j - 1][i] != 0 && board[j][i] == 0) {
bridgeFlag = board[j - 1][i];
bridgeLength = 1;
}
continue;
}
if (board[j][i] == 0) {
bridgeLength++;
} else {
if (bridgeLength >= 2) {
bridges[bridgeFlag][board[j][i]] = Math.min(
bridges[bridgeFlag][board[j][i]] == 0 ? 0x7fffffff : bridges[bridgeFlag][board[j][i]],
bridgeLength);
bridges[board[j][i]][bridgeFlag] = Math.min(
bridges[board[j][i]][bridgeFlag] == 0 ? 0x7fffffff : bridges[board[j][i]][bridgeFlag],
bridgeLength);
}
bridgeFlag = 0;
bridgeLength = 0;
}
}
}
}
/**
* Prim 알고리즘
*
* 한 정점부터 시작하여 현재 그래프에서 이동할 수 있는 가장 거리가 짧은 간선들을 골라가며
* 최소 신장트리를 구하는 알고리즘
*
* start부터 시작하여 start에서 이동할 수 있는 (다른 섬의 번호, 다른 섬까지의 거리)를
* 다른 섬까지의 거리의 오름차순으로 PriorityQueue에 넣고
* 방문하지 않은 정점들에 대해서 계속해서 탐색해 나가도록 설계
*/
private static void prim(int start) {
Queue<Pair> pq = new PriorityQueue<>((o1, o2) -> o1.second - o2.second);
boolean[] visited = new boolean[bridges.length];
pq.add(new Pair(start, 0));
int weight = 0;
int sumCnt = 0;
while (!pq.isEmpty()) {
Pair tmp = pq.poll();
int curPos = tmp.first;
int curCost = tmp.second;
if (visited[curPos]) continue;
weight += curCost;
sumCnt++;
visited[curPos] = true;
for (int i = 1; i < bridges[curPos].length; i++) {
if (bridges[curPos][i] != 0) {
pq.add(new Pair(i, bridges[curPos][i]));
}
}
}
if (sumCnt == bridges.length - 1)
System.out.println(weight == 0 ? -1 : weight);
else
System.out.println(-1);
}
private static void bfs(int row, int col, int cnt) {
Queue<Pair> q = new ArrayDeque<>();
q.add(new Pair(row, col));
board[row][col] = cnt;
while (!q.isEmpty()) {
Pair tmp = q.poll();
int curRow = tmp.first;
int curCol = tmp.second;
for (int i = 0; i < 4; i++) {
int nextRow = tmp.first + dir[i][0];
int nextCol = tmp.second + dir[i][1];
if (check(nextRow, nextCol)) {
board[nextRow][nextCol] = cnt;
q.add(new Pair(nextRow, nextCol));
}
}
}
}
private static boolean check(int row, int col) {
return row >= 0 && row < rowLen && col >= 0 && col < colLen && board[row][col] == -1;
}
}
👎 어려웠던 점
- BFS, MST 등 다양한 알고리즘을 복합적으로 사용해야 하는 구현 문제이다 보니, 해당 알고리즘들에 대한 이해도가 부족할 경우에 코드를 작성하면서 헷갈리는 현상이 발생할 수 있었습니다.
⏰ 사용한 메모리 / 시간
- Memory : 14280KB
- Time : 132ms
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[BOJ_5972] 택배 배송 (0) | 2023.04.04 |
---|---|
[BOJ_14890] 경사로 (0) | 2023.04.04 |
[BOJ_2157] 여행 (0) | 2023.04.04 |
[BOJ_1939] 중량제한 (0) | 2023.04.03 |
[BOJ_23059] 리그 오브 레게노 (0) | 2023.04.03 |