[백준] 단계별로 풀어보기(단계:31, 최소 신장 트리,JAVA)17472번, 다리 만들기 2

문제 링크

17472번: 다리 만들기 2

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

최소 신장 트리

신장 트리 : 어떤 그래프에 대하여 모든 꼭짓점을 포함하는부분 그래프입니다.

 

최소 신장 트리 : 신장 트리에서 최소의 가중치를 가지는 부분 그래프입니다. 

Minimum spanning tree - Wikipedia

이 문제에 핵심은

1. 다리의 방향은 가로, 세로가 될 수 밖에 없다.

2. 다리의 방향은 중간의 바꿀 수 없다.

3. 다리로 모든 구역을 연결하며 다리는 최소 길이가 2이상이어야 한다.

4. 모든 다리의 길이의 합을 출력하며, 모든 구역을 연결할 수 없으면 -1을 출력합니다.

 

최소 신장 트리를 구하기 위해서 Union-Find와 Greedy알고리즘을 이용하여 구현하였습니다.

Union Find - 나무위키

 

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

 

Greedy알고리즘을 이용하여 가중치가 낮은 선분부터 탐색을 시작합니다.

 

선분을 탐색할 때 Union-Find를 이용하여 사이클이 발생하는지 확인하여 최소 신장 트리를 완성하였습니다.

 

입력받은 지도에 대하여 BFS탐색을 통해서 구역을 나누었습니다.

 

구역을 나눈 후 브루트 포스로 중복되는 다리는 제외한 후 모든 가로, 세로형 다리를 구하였습니다.

 

Union-Find를 하기 위해서 구한 다리의 길이를 기준으로 오름차순으로 정렬하였습니다.

 

Union-Find를 이용하여 최소 신장 트리를 구현하여 가중치의 합을 출력하였습니다.

 

만약 최소 신장 트리 만들어지지 않으면 -1을 결과로 출력하였습니다.

 

 

예제입력1

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

 

BFS를 통해서 구역을 나누면

0	0	0	0	0	0	1	1
2	2	0	0	0	0	1	1
2	2	0	0	0	0	0	0
2	2	0	0	0	3	3	0
0	0	0	0	0	3	3	0
0	0	0	0	0	0	0	0
4	4	4	4	4	4	4	4

 

해당 구역에서 중복되는 다리를 제외한 모든 다리를 표현하면

0	0	0	0	0	0	1	1
2	2	0	0	0	0	1	1
2	2	0	0	0	0	0	0
2	2	0	0	0	3	3	0
0	0	0	0	0	3	3	0
0	0	0	0	0	0	0	0
4	4	4	4	4	4	4	4

다리

1 ↔ 2 , 길이 : 4

1 ↔ 4 , 길이 : 4

2 ↔ 3 , 길이 : 3

2 ↔ 4 , 길이 : 2

 

Union-Find를 위한 길이 기준 오름차순 정렬

2 ↔ 4 , 길이 : 2

2 ↔ 3 , 길이 : 3

1 ↔ 2 , 길이 : 4

1 ↔ 4 , 길이 : 4

 

Union-Find에 사용할 Root Node

구역 1	구역 2	구역 3	구역 4
1	2	3	4

 

2 ↔ 4 탐색

2와 4의 Root Node는 다르기 때문에 사이클 형성 X, 선분을 이용

구역 1	구역 2	구역 3	구역 4
1	2	3	2

 

2 ↔ 3 탐색

2와 3의 Root Node는 다르기 때문에 사이클 형성 X, 선분을 이용

구역 1	구역 2	구역 3	구역 4
1	2	2	2

 

1 ↔ 2 탐색

1과 2의 Root Node는 다르기 때문에 사이클 형성 X, 선분을 이용

구역 1	구역 2	구역 3	구역 4
1	1	2	2

 

1 ↔ 4 탐색

1과 4의 Root Node는 같기 때문에 사이클 형성 O, 선분을 이용X

구역 1	구역 2	구역 3	구역 4
1	1	1	1

 

사용되는 다리 2 ↔ 4, 2 ↔ 3, 1 ↔ 2 의 가중치의 합 : 2 + 3 + 4 = 9

 

최소 신장 트리의 가중치의 합(9)을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 지도에 대한 정보를 저장합니다.
• 지도의 정보를 이용하여 각 구역을 나누는 bfs함수를 실행하였습니다.
• 각 구역을 기준으로 중복을 제외한 다리를 구하는 horizontality/vertical 함수를 실행하였습니다.
• root[]와 union함수를 이용하여 최소 신장 트리의 가중치 합과 모든 섬이 연결되는지 확인하였습니다.
• BufferedWriter에 다리가 없거나 모든 섬을 지나지 않으면 -1, 최소 신장 트리를 만족하면 최소합을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 BFS(너비 우선 탐색)을 이용하여 각 구역의 번호를 저장하였습니다.
• horizontality/vertical함수는 브루트 포스와 width[]을 이용하여 중복을 제외한 모든 경우의 다리를 구하였습니다.
• find함수는 루트 노드의 값을 구하는 재귀 함수입니다.
• union함수는 루트 노드가 같은지 확인 및 변경하는 함수입니다.

 

결과 코드

import java.io.*;
import java.util.*;

public class Main{
		//지도 구역 관련 생성자
	static class position{
		int x,y;
		public position(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
    	//다리 관련 생성자
	static class line{
		int p1, p2, width;
		public line(int p1, int p2, int width) {
			super();
			this.p1 = p1;
			this.p2 = p2;
			this.width = width;
		}	
	}
	static int N,M;
	static int[][] map,location, width;		//지도, 구역, 다리 길이 저장 배열
	static int[] root;		//루트 노드 저장 배열
	static int[] dx = {0, 0, -1, 1};	//상, 하, 좌, 우 x값 변경값
	static int[] dy = {-1, 1, 0, 0};	//상, 하, 좌, 우 y값 변경값
	static ArrayList<line> bridge = new ArrayList<>();	//다리 관련 리스트
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		location = new int[N][M];
        	//지도 관련 정보 저장
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<M;j++) 
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		int locationIdx = 1;	
        	//지도에 표시된 구역 나누기
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(location[i][j]!=0 || map[i][j]==0)
					continue;
				bfs(j,i, locationIdx++);	//구역 나누는 BFS 함수 실행
			}
		}
		width = new int[locationIdx][locationIdx];
		root = new int[locationIdx];
        	//다리 길이 관련 배열 초기화
		for(int i=0;i<width.length;i++)
			Arrays.fill(width[i], 101);
            	//루트 노드 관련 배열 초기화
		for(int i=0;i<root.length;i++) 
			root[i] = i;
            	//중복을 제외한 모든 다리 구하기
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]==0)
					continue;
				if(j<M-1 && map[i][j+1]==0)	//가로형 다리
					horizontality(j+1,i);
				if(i<N-1 && map[i+1][j] == 0)	//세로형 다리
					vertical(j,i+1);
			}
		}
		if(bridge.isEmpty()) {		//다리가 존재하지 않을 때
			bw.write("-1\n");
		}else {
        		//Union-Find를 위한 다리 길이 기준 오름차순 정렬
			Collections.sort(bridge, new Comparator<line>() {
				@Override
				public int compare(line o1, line o2) {
					return o1.width - o2.width;
				}
			});
				//최소 신장 트리의 가중치 합 구하기
			int result = 0;
			for(int i=0;i<bridge.size();i++) {
				if(!union(bridge.get(i).p1,bridge.get(i).p2))
					result += bridge.get(i).width;
			}
            		//모든 섬이 연결되었는지 확인하기
			boolean check = false;
			for(int i=1;i<root.length;i++) {
				if(find(i) != 1) {
					check = true;
					break;
				}
			}
			if(check)		//모든 섬이 연결되지 않았을 때
				bw.write("-1\n");
			else		//모든 섬이 연결되었을 때
				bw.write(result + "\n");
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//가로형 다리 구하는 함수
	static void horizontality(int x, int y) {
		int count = 0;
		int curX = x;
		int curY = y;
		boolean check = false;
		while(curX<M) {
			if(map[curY][curX] == 1) {
				check = true;
				break;
			}
			count++;
			curX++;
		}
		x-=1;
        	//중복되는 다리 제외하기 위해서 Width[]을 이용
		if(count>=2 && check) {
			if(width[location[y][x]][location[curY][curX]]>count) {
				width[location[curY][curX]][location[y][x]] = count;
				width[location[y][x]][location[curY][curX]] = count;
				bridge.add(new line(location[y][x],location[curY][curX],count));
			}
		}
	}
    	//세로형 다리 구하는 함수
	static void vertical(int x, int y) {
		int count=0;
		int curX = x;
		int curY = y;
		boolean check = false;
		while(curY<N) {
			if(map[curY][curX] == 1) {
				check = true;
				break;
			}
			count++;
			curY++;
		}
		y-=1;
        	//중복되는 다리 제거하기 위해 Width[] 이용
		if(count>=2 && check) {
			if(width[location[y][x]][location[curY][curX]]>count) {
				width[location[curY][curX]][location[y][x]] = count;
				width[location[y][x]][location[curY][curX]] = count;
				bridge.add(new line(location[y][x],location[curY][curX],count));
			}
		}
	}
    	//루트 노드 같은지 확인 및 변경하는 함수
	static boolean union(int a, int b) {
		int x = find(a);
		int y = find(b);
		if(x!=y) {
			if(x<y)
				root[y] = x;
			else
				root[x] = y;
			return false;
		}
		return true;
	}
    	//루트 노드 찾는 함수
	static int find(int n) {
		if(n == root[n])
			 return n;
		return root[n] = find(root[n]);
	}
    	//BFS탐색으로 지도에 있는 섬에 대하여 구역을 나누는 함수
	static void bfs(int x, int y, int idx) {
		Queue<position> queue = new LinkedList<>();
		queue.add(new position(x, y));
		location[y][x] = idx;
		while(!queue.isEmpty()) {
			position cur = queue.poll();
			for(int i=0;i<4;i++) {
				int tempX = cur.x + dx[i];
				int tempY = cur.y + dy[i];
				if(tempX>=0 && tempX<M && tempY>=0 && tempY<N) {
					if(location[tempY][tempX]==0 && map[tempY][tempX]==1) {
						location[tempY][tempX] = idx;
						queue.add(new position(tempX, tempY));
					}
				}
			}
		}
	}
}