※ 백준 (Baekjoon)/[Java] 문제 풀이 ( Solve the problems)
[골드1] 17472. 다리 만들기 2(Java)
J 크
2023. 10. 8. 22:00
728x90
반응형
https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
다리 다 뿌셔
※ 문제를 요약하면 아래와 같습니다.
▶ 맵에 0과 1의 정보가 주어지며, 1이 상하좌우로 연결 되어 있는 곳은 섬으로 판정
▶ 다리는 섬들 사이에 연결할 수 있으며 가로 혹은 세로로만 연결 가능
▶ 섬들 사이에 다리를 연결 할 때, 모든 섬을 연결하는 다리 길이의 최소값 탐색
▶ 구역에 대한 정보가 주어졌을 때, 인구 차이의 최소값 탐색
▶ Input : 첫째 줄에 세로 크기 N과 가로 크기 M이 입력, 이후 N 줄에 섬의 정보 입력
▶ Output : 모든 섬을 연결하는 다리 길이의 최솟값 출력
◈ Input - 1
7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1◈ Output - 1
9◈ Input - 2
7 8
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1◈ Output - 2
10◈ Input - 3
7 8
1 0 0 1 1 1 0 0
0 0 1 0 0 0 1 1
0 0 1 0 0 0 1 1
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0◈ Output - 3
9◈ Input - 4
7 7
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1◈ Output - 4
-1
◎ 코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.
▶ DFS로 섬을 탐색하며 번호를 지정 ( 코드 내 narrIsland )
ex) 첫번째로 탐색된 섬의 구역은 1로 지정, 두번째로 탐색된 섬의 구역은 2로 지정
▶ BFS로 가로 탐색, 각 섬의 최소 가로 길이 저장, 세로 탐색으로 각 섬의 최소 세로 길이 저장
▶ 섬의 번호를 노드 번호, 섬 간의 거리를 가중치를 적용하여 prim 알고리즘 적용 하여 최소 스패닝 트리 생성
▶ 최소 스패닝 트리에서 가중치 값을 전부 더하여 == 섬들간의 최소 다리값 출력
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Point {
int m_nRow;
int m_nCol;
int m_nDistance;
public Point(int m_nRow, int m_nCol, int m_nDistance) {
this.m_nRow = m_nRow;
this.m_nCol = m_nCol;
this.m_nDistance = m_nDistance;
}
}
class Node {
int m_nEnd;
int m_nDistance;
public Node(int m_nEnd, int m_nDistance) {
this.m_nEnd = m_nEnd;
this.m_nDistance = m_nDistance;
}
@Override
public String toString() {
return "Node [m_nEnd=" + m_nEnd + ", m_nDistance=" + m_nDistance + "]";
}
}
public class Main {
static int N, M, nIsland;
static boolean[][] barrMap, barrVisit;
static int[][] narrIsland;
static boolean[] barrPrim;
static ArrayList<Node>[] listIsland;
static int dr[] = { 0, 0, 1, -1 };
static int dc[] = { 1, -1, 0, 0 };
static int[] narrPrim;
public static void main(String[] args) throws IOException {
BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// 노드 입력 받고
StringTokenizer st = new StringTokenizer(bReader.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
barrMap = new boolean[N][M];
barrVisit = new boolean[N][M];
narrIsland = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(bReader.readLine());
for (int j = 0; j < M; j++) {
if (st.nextToken().equals("1"))
barrMap[i][j] = true;
}
}
nIsland = 0;
// 우선, 섬들을 탐색해보자
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (barrMap[i][j] && !barrVisit[i][j]) {
nIsland++;
// 섬이 하나 있다.
// 이 섬의 시작 땅을 추가해주고 탐색하여
narrIsland[i][j] = nIsland;
// 이 섬의 모든 땅 좌표를 추가해주자
DFS(i, j);
}
}
}
// 인접 리스트 초기화
listIsland = new ArrayList[nIsland + 1];
for (int i = 0; i < nIsland + 1; i++)
listIsland[i] = new ArrayList<>();
// 각 섬간의 최소 길이를 BFS로 찾아보자
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int nIslandNum = narrIsland[i][j];
if (nIslandNum > 0) {
// 각 섬간의 최소 길이를 탐색해보자
// 가로 탐색
barrVisit = new boolean[N][M];
BFS(i, j, nIslandNum, true);
// 세로 탐색
barrVisit = new boolean[N][M];
BFS(i, j, nIslandNum, false);
}
}
}
bWriter.write(String.valueOf(prim()));
bWriter.close();
}
// 섬들간의 최소 거리를 탐색해보자
private static void BFS(int nRow, int nCol, int nIslandNum, boolean bVertical) {
Queue<Point> queueBFS = new LinkedList<>();
queueBFS.add(new Point(nRow, nCol, 0));
while (!queueBFS.isEmpty()) {
Point p = queueBFS.poll();
int nNum = narrIsland[p.m_nRow][p.m_nCol];
// continue;
// 가로 탐색
int nStartD = 0;
int nEndD = 2;
// 세로 탐색
if(!bVertical) {
nStartD = 2;
nEndD =4;
}
for (int i = nStartD; i < nEndD; i++) {
int nSearchRow = p.m_nRow + dr[i];
int nSearchCol = p.m_nCol + dc[i];
// 범위 밖이면 넘어가줘유
if (nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= M)
continue;
nNum = narrIsland[nSearchRow][nSearchCol];
// 방문했던 곳이면 넘어가줘유
// 이전에 이미 본 섬들은 볼 필요가 읎다
if (barrVisit[nSearchRow][nSearchCol])
continue;
barrVisit[nSearchRow][nSearchCol] = true;
// 어떠한 섬에 도달 했을 경우 현재까지의 거리와 저장되어 있는 거리를 비교하여
// 더 작은 거리를 넣어준다.
// 그리고 탐색을 끝낸당
if(nNum != 0) {
if(p.m_nDistance > 1) {
listIsland[nIslandNum].add(new Node(nNum, p.m_nDistance));
}
continue;
}
queueBFS.add(new Point(nSearchRow, nSearchCol, p.m_nDistance + 1));
}
}
}
// 섬들의 정보를 탐색해보자
private static void DFS(int nRow, int nCol) {
barrVisit[nRow][nCol] = true;
for (int i = 0; i < dr.length; i++) {
int nSearchRow = nRow + dr[i];
int nSearchCol = nCol + dc[i];
// 범위 밖이면 넘어가줘유
if (nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= M)
continue;
// 섬이 아니거나 방문했던 곳이면 넘어가줘유
if (!barrMap[nSearchRow][nSearchCol] || barrVisit[nSearchRow][nSearchCol])
continue;
// 이 땅 좌표를 저장해줘유
// 다음 땅으로 넘어가유
narrIsland[nSearchRow][nSearchCol] = nIsland;
DFS(nSearchRow, nSearchCol);
}
}
// 최소 다리 연결값을 찾자
private static int prim() {
narrPrim = new int[nIsland];
barrPrim = new boolean[nIsland];
Arrays.fill(narrPrim, Integer.MAX_VALUE);
narrPrim[0] = 0;
for(int i = 1; i <listIsland.length; i++) {
if(listIsland[i].isEmpty())
return -1;
}
int nResult = 0;
for(int i = 0 ; i < nIsland; i++) {
int nIndex = -1;
int nMin = Integer.MAX_VALUE;
// 탐색할 노드 번호를 정하자
for(int j = 0; j < nIsland; j++) {
if(nMin > narrPrim[j] && !barrPrim[j]) {
nMin = narrPrim[j];
nIndex = j;
}
}
if(nIndex == -1) {
nResult = -1;
break;
}
nResult += narrPrim[nIndex];
barrPrim[nIndex] = true;
for(int j = 0; j < listIsland[nIndex+1].size(); j++) {
int nNextNode = listIsland[nIndex+1].get(j).m_nEnd-1;
int nDistance = listIsland[nIndex+1].get(j).m_nDistance;
if(narrPrim[nNextNode] > nDistance && !barrPrim[nNextNode])
narrPrim[nNextNode] = nDistance;
}
}
//System.out.println(Arrays.toString(narrPrim));
if(nResult == 0)
nResult = -1;
return nResult;
}
}Good Luck! (피드백 감사합니다!)