문제
섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.
섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.
다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.
다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.
섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.
아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.
 |
 |
| 다리의 총 길이: 13 D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다. |
다리의 총 길이: 9 (최소) |
다음은 올바르지 않은 3가지 방법이다
 |
 |
 |
| C의 방향이 중간에 바뀌었다 | D의 길이가 1이다. | 가로 다리인 A가 1과 가로로 연결되어 있지 않다. |
다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.
 |
 |
| A의 길이는 4이고, B의 길이도 4이다. 총 다리의 총 길이: 4 + 4 + 2 = 10 |
다리 A: 2와 3을 연결 (길이 2) 다리 B: 3과 4를 연결 (길이 3) 다리 C: 2와 5를 연결 (길이 5) 다리 D: 1과 2를 연결 (길이 2) 총 길이: 12 |
나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.
https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
출력
모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.
제한
- 1 ≤ N, M ≤ 10
- 3 ≤ N×M ≤ 100
- 2 ≤ 섬의 개수 ≤ 6
접근
여러 풀이 전략이 결합된 문제이다.
1) 먼저 깊이/너비 탐색을 통해 구역번호를 지정하고, 같은 섬은 같은 구역번호로 지정한다.
2) 주변 섬과의 거리를 측정하고, 거리가 1 이상이면 간선 정보(섬1, 섬2, 거리)를 저장하고 list에 넣는다.
3) MST를 이용하여 최소 신장 트리의 길이를 출력한다.
만약 선택된 간선이 섬 개수 -1 보다 작으면 적절하지 않음으로 -1을 출력한다.
구현
1) 입력
static int N,M; //행,열 크기
static int[][] Board; //주어진 데이터를 저장할 2차원 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken()); //행 크기
M=Integer.parseInt(st.nextToken()); //열 크기
Board=new int[N][M]; //데이터 저장을 위한 배열 선언
//주어진 값 입력
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
Board[i][j]=Integer.parseInt(st.nextToken());
}
}
//최소 신장 트리의 간선 합 길이 출력
System.out.println(minBridge());
br.close();
}주어진 N과 M, 섬의 정보를 입력한다.
2) 최소 간선의 길이
public static int minBridge() {
//각 구역에 구역번호 지정하고 최대 구역번호 리턴(구역은 2부터 시작)
int maxDivision = islandDivision();
//division 개수
int countDivision = maxDivision-1;
//kruskal 알고리즘으로 최소 신장 트리 길이 출력
return kruskalMst(maxDivision, countDivision);
}
최소 간선 길이 출력을 위해
먼저 섬의 구역을 지정하고, 최대 구역 번호와 구역 개수를 이용하여 최소 신장 길이를 구한다.
3) 섬 구역 지정
//방향
static int[][] D = {{0,1},{-1,0},{1,0},{0,-1}};
//섬 구역 지정
public static int islandDivision() {
//구역 번호, 1은 미지정, 2부터 시작하여 증가함
int division = 2;
//bfs 를 위한 큐
Queue<int[]> q = new LinkedList<int[]>();
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
//1이면 섬이 존재
if(Board[i][j]==1) {
//큐에 추가하여 주변 탐색
q.add(new int[] {i,j});
while(!q.isEmpty()) {
int[] curr = q.poll();
int r = curr[0];
int c = curr[1];
//구역 표시
Board[r][c]=division;
//상하좌우 탐색
for(int d=0;d<4;d++) {
int nr = r+D[d][0];
int nc = c+D[d][1];
//범위 이탈시 continue
if(nr<0||nr>=N||nc<0||nc>=M) continue;
//1이면 아직 미지정이므로 큐에 넣어 탐색
if(Board[nr][nc]==1) {
q.add(new int[] {nr,nc});
}
}
}
//다른 구역 지정을 위해 1 증가
division++;
}
}
}
//최대 division 출력
return division-1;
}너비 우선 탐색을 통해 섬의 구역마다 번호를 지정한다.
같은 섬이라면 같은 구역 번호를 가지게 되며
1은 미지정된 섬이라는 의미로 사용하여 2부터 구역번호를 지정하였다.
4) 크루스칼 MST
4-1) Edge 클래스
//간선 정보 저장
static class Edge implements Comparable<Edge>{
int node1,node2;
int length;
//생성자
public Edge(int node1, int node2, int length) {
this.node1=node1;
this.node2=node2;
this.length=length;
}
//pq를 이용하기 위한 정렬, length가 적은 순
@Override
public int compareTo(Edge o) {
if(this.length<o.length) return -1;
if(this.length>o.length) return 1;
return 0;
}
@Override
public String toString() {
return node1+" "+node2+" "+length;
}
}간선 정보를 저장할 클래스이다.
node(섬) 과 다른 node의 정보와 이를 연결하는 간선 길이 정보를 가지고 있다.
정렬을 위해 Comparable을 상속받고 길이가 짧은 순으로 정렬하도록 하였다.
4-2) Union Find를 위한 메서드
static int[] Parents; //부모 배열
//부모 찾기
public static int getParent(int node) {
if(Parents[node]==node) return node;
return Parents[node]=getParent(Parents[node]);
}
//부모 세팅, 작은 수가 부모
public static void setParent(int node1, int node2) {
int p1 = getParent(node1);
int p2 = getParent(node2);
if(p1<p2) Parents[p2]=p1;
else Parents[p1]=p2;
}
//같은 부모 판별
public static boolean isSameParent(int node1, int node2) {
return getParent(node1)==getParent(node2);
}간선의 부모를 지정/탐색하기 위한 세트 메서드이다.
4-3) 크루스칼 MST (1)
//최소 신장 길이 탐색, kruskal MST 사용
public static int kruskalMst(int maxDivision, int countDivision) {
//부모 초기화, 자기 자신이 부모
Parents = new int[maxDivision+1];
for(int i=2;i<=maxDivision;i++) {
Parents[i]=i;
}
//length가 적은순으로 poll되는 우선순위 큐
PriorityQueue<Edge> pq = new PriorityQueue<>();
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
//0이면 비어있음으로 continue
if(Board[i][j]==0) continue;
//현재 구역 번호
int no = Board[i][j];
//완전 탐색할 것임으로 오른쪽과 아래만 탐색
for(int d=0;d<2;d++) {
//구역과의 거리
int length = 0;
//이동한 행과 열
int r = i+D[d][0];
int c = j+D[d][1];
//범위를 벗어날때까지 반복
while(r>=0&&c>=0&&r<N&&c<M) {
//본인 번호를 만나면 break
if(Board[r][c]==no) break;
//다른 섬에 다다르면
if(Board[r][c]!=0) {
//거리가 1 이상일 경우에만 간선 정보를 pq에 추가
if(length>1) {
pq.add(new Edge(no, Board[r][c], length));
}
//더이상 탐색할 필요가 없음으로 종료
break;
}
//아직 섬을 만나지 못했음으로 한칸 더 이동
r+=D[d][0];
c+=D[d][1];
//거리 1 증가
length++;
}
}
}
}
//----------------------------크루스칼 MST (2)----------------------------//먼저 부모를 자신의 번호로 초기화한다. 이 때, 구역번호는 2부터 사용하였음으로 2부터 초기화하였다.
완전탐색을 통해 인접 섬과의 거리를 측정하였다.
이 때 방향은 오른쪽과 아래방향만 탐색하였다.
(위와 왼쪽 방향을 포함시키면 완전탐색이기에 같은 간선 정보가 2번 탐색하게 된다.)
거리 측정은 자신과 같은 번호를 만나거나 배열 범위를 벗어나면 break하고,
다른 섬을 만났을 때, 거리가 2 이상일 경우에만 우선순위 큐에 추가한다.
4-3) 크루스칼 MST (2)
//----------------------------크루스칼 MST (1)----------------------------//
//트리 간선 개수
int count = 0;
//간선의 길이 합
int sumLength = 0;
//간선 탐색
while(!pq.isEmpty()) {
Edge edge = pq.poll();
//같은 부모가 아니면 간선 채택
if(!isSameParent(edge.node1, edge.node2)) {
//두 구역의 부모 설정
setParent(edge.node1, edge.node2);
//간선 개수 1 증가
count++;
//간선 길이 추가
sumLength+=edge.length;
//간선의 개수가 N-1이라면 리턴
if(count==countDivision-1) return sumLength;
}
}
//간선 개수가 충분하지 않음으로 구성 불가
return -1;
}크루스칼 알고리즘을 통해
길이가 짧은 간선순으로 검사를 한다.
간선끼리 부모가 다른 경우,
간선을 선택하고 (count 증가), 부모를 동일하게 세팅하고 (setParent()), 간선 길이를 추가한다.
만약 선택한 간선 개수가 섬의 개수-1 이라면 간선 길이 합을 출력하고,
모두 탐색했음에도 간선 개수가 부족하면 모두 연결할 수 없음으로 -1을 출력한다.
5) 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N,M; //행,열 크기
static int[][] Board; //주어진 데이터를 저장할 2차원 배열
static int[][] D = {{0,1},{-1,0},{1,0},{0,-1}}; //방향
static int[] Parents; //부모 배열
//간선 정보 저장
static class Edge implements Comparable<Edge>{
int node1,node2;
int length;
//생성자
public Edge(int node1, int node2, int length) {
this.node1=node1;
this.node2=node2;
this.length=length;
}
//pq를 이용하기 위한 정렬, length가 적은 순
@Override
public int compareTo(Edge o) {
if(this.length<o.length) return -1;
if(this.length>o.length) return 1;
return 0;
}
@Override
public String toString() {
return node1+" "+node2+" "+length;
}
}
//부모 찾기
public static int getParent(int node) {
if(Parents[node]==node) return node;
return Parents[node]=getParent(Parents[node]);
}
//부모 세팅, 작은 수가 부모
public static void setParent(int node1, int node2) {
int p1 = getParent(node1);
int p2 = getParent(node2);
if(p1<p2) Parents[p2]=p1;
else Parents[p1]=p2;
}
//같은 부모 판별
public static boolean isSameParent(int node1, int node2) {
return getParent(node1)==getParent(node2);
}
//섬 구역 지정
public static int islandDivision() {
//구역 번호, 1은 미지정, 2부터 시작하여 증가함
int division = 2;
//bfs 를 위한 큐
Queue<int[]> q = new LinkedList<int[]>();
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
//1이면 섬이 존재
if(Board[i][j]==1) {
//큐에 추가하여 주변 탐색
q.add(new int[] {i,j});
while(!q.isEmpty()) {
int[] curr = q.poll();
int r = curr[0];
int c = curr[1];
//구역 표시
Board[r][c]=division;
//상하좌우 탐색
for(int d=0;d<4;d++) {
int nr = r+D[d][0];
int nc = c+D[d][1];
//범위 이탈시 continue
if(nr<0||nr>=N||nc<0||nc>=M) continue;
//1이면 아직 미지정이므로 큐에 넣어 탐색
if(Board[nr][nc]==1) {
q.add(new int[] {nr,nc});
}
}
}
//다른 구역 지정을 위해 1 증가
division++;
}
}
}
//최대 division 출력
return division-1;
}
//최소 신장 길이 탐색, kruskal MST 사용
public static int kruskalMst(int maxDivision, int countDivision) {
//부모 초기화, 자기 자신이 부모
Parents = new int[maxDivision+1];
for(int i=2;i<=maxDivision;i++) {
Parents[i]=i;
}
//length가 적은순으로 poll되는 우선순위 큐
PriorityQueue<Edge> pq = new PriorityQueue<>();
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
//0이면 비어있음으로 continue
if(Board[i][j]==0) continue;
//현재 구역 번호
int no = Board[i][j];
//완전 탐색할 것임으로 오른쪽과 아래만 탐색
for(int d=0;d<2;d++) {
//구역과의 거리
int length = 0;
//이동한 행과 열
int r = i+D[d][0];
int c = j+D[d][1];
//범위를 벗어날때까지 반복
while(r>=0&&c>=0&&r<N&&c<M) {
//본인 번호를 만나면 break
if(Board[r][c]==no) break;
//다른 섬에 다다르면
if(Board[r][c]!=0) {
//거리가 1 이상일 경우에만 간선 정보를 pq에 추가
if(length>1) {
pq.add(new Edge(no, Board[r][c], length));
}
//더이상 탐색할 필요가 없음으로 종료
break;
}
//아직 섬을 만나지 못했음으로 한칸 더 이동
r+=D[d][0];
c+=D[d][1];
//거리 1 증가
length++;
}
}
}
}
//트리 간선 개수
int count = 0;
//간선의 길이 합
int sumLength = 0;
//간선 탐색
while(!pq.isEmpty()) {
Edge edge = pq.poll();
//같은 부모가 아니면 간선 채택
if(!isSameParent(edge.node1, edge.node2)) {
//두 구역의 부모 설정
setParent(edge.node1, edge.node2);
//간선 개수 1 증가
count++;
//간선 길이 추가
sumLength+=edge.length;
//간선의 개수가 N-1이라면 리턴
if(count==countDivision-1) return sumLength;
}
}
//간선 개수가 충분하지 않음으로 구성 불가
return -1;
}
public static int minBridge() {
//각 구역에 구역번호 지정하고 최대 구역번호 리턴(구역은 2부터 시작)
int maxDivision = islandDivision();
//division 개수
int countDivision = maxDivision-1;
//kruskal 알고리즘으로 최소 신장 트리 길이 출력
return kruskalMst(maxDivision, countDivision);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
Board=new int[N][M];
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
Board[i][j]=Integer.parseInt(st.nextToken());
}
}
System.out.println(minBridge());
br.close();
}
}
'알고리즘' 카테고리의 다른 글
| [백준] 25044번: 에어컨 Java (0) | 2022.05.02 |
|---|---|
| [백준] 10163번: 색종이 Java (0) | 2022.04.29 |
| [백준] 4386번: 별자리 만들기 Java (0) | 2022.04.27 |
| [백준] 1774번: 우주신과의 교감 Java (0) | 2022.04.26 |
| [백준] 1197번: 최소 스패닝 트리 Java (0) | 2022.04.25 |
댓글