백준 17472 <다리 만들기 2 >

섬을 연결하는 최소 거리를 찾는 게 가장 어려웠던 문제...

 

알고리즘 순서를 말하자면

 

1. BFS를 이용해서 각지점마다 연결돼있는 섬을 만들어주고 섬의 개수 파악
2. 각 지점에서 다른 섬 까지 이동할 수 있는 2를 넘는 최소거리 구해주기
3.  크루스칼 또는 프림 알고리즘을 이용하여 총길이 구하기 (미니엄 스패닝 트리 MST)!

이렇게 총 3단계로 구성이 된다. 여러 알고리즘을 혼합했기 때문에 생각하기 좀 까다로웠던 시뮬레이션 문제!

 

1번을 구하는데 N*M 의 시간 총 100

 

2번을 구하는데 N*M*많이 해도 N*M을 한 번 더 곱한 수

 

3번을 하는데 섬의 개수가 최대 6이기 때문에 21...

 

절대 시간 초과는 날 수 없는 문제...

 

1번 구성

 

 

맵을 1에서 바꿔줬기 때문에 visit 배열을 따로 선언할 필요가 없다.

 

2번 구성

우선 최솟값을 넣어줄 것이기 때문에 연결된 거리는 전부 최댓값으로 초기화시켰다.

 

다음 위치가 자기 자신이거나 벗어나면 안 되기 때문에 저렇게 처리를 해주고 다른 섬에 도착했을 경우 2 차이가 넘게 난다면 최솟값을 넣어주었다.!

 

3번 구성

 

여기서 cnt를 해준 이유는 마지막에 값을 출력할 때 모든 섬을 연결했는지 확인해주기 위해서이다.

또한 Integer 최댓값인 경우는 넣어주면 안 되게 체크를 해주었다.

 

이렇게 생각할게 많은 문제였다.. 

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

	public static class dis implements Comparable<dis> {
		public dis(int next, int di) {
			this.next = next;
			this.di = di;
		}

		int next;
		int di;

		@Override
		public int compareTo(dis o) {
			// TODO Auto-generated method stub
			return this.di - o.di;
		}
	}

	static int link[][],cnt, n, m, result, dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, map[][], count = 2;
	static boolean visit2[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(kb.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(kb.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] != 1) {
					continue;
				}
				bfs(i, j);
				count++;
			}
		}
		link = new int[count - 2][count - 2];
		visit2 = new boolean[count - 2];
		create_line();
		findmin(0, 0);
		if(cnt==link.length) {
			System.out.println(result);
		}
		else {
			System.out.println(-1);
		}
	}

	private static void findmin(int start, int d) {
		// TODO Auto-generated method stub
		PriorityQueue<dis> pr = new PriorityQueue<dis>();
		pr.add(new dis(0, 0));
		while (!pr.isEmpty()) {
			dis de = pr.remove();
			if (visit2[de.next])
				continue;
			visit2[de.next] = true;
			result += de.di;
			cnt++;
			for (int i = 0; i < link.length; i++) {
				if (de.next == i || visit2[i]||link[de.next][i]==Integer.MAX_VALUE) {
					continue;
				}
				pr.add(new dis(i, link[de.next][i]));
			}
		}
	}

	private static void create_line() {
		// TODO Auto-generated method stub
		for(int i=0;i<link.length;i++) {
			Arrays.fill(link[i],Integer.MAX_VALUE);
		}
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map[0].length;j++) {
				if(map[i][j]>=2) {
					bfsgo(i,j,map[i][j]);
				}
			}
		}
	}

	private static void bfsgo(int x, int y, int k) {
		// TODO Auto-generated method stub
		for(int i=0;i<4;i++) {
			int count=0;
			int x1=x+dir[i][0];
			int y1=y+dir[i][1];
			while(true) {
				if(x1<0||x1>=map.length||y1<0||y1>=map[0].length||map[x1][y1]==k)
					break;
				if(map[x1][y1]!=0) {
					if(count>=2)
						link[k-2][map[x1][y1]-2]=Math.min(link[k-2][map[x1][y1]-2],count);
					break;
				}
				count++;
				x1=x1+dir[i][0];
				y1=y1+dir[i][1];
			}
		}
			
		
	}

	private static void bfs(int x, int y) {
		// TODO Auto-generated method stub
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(x, y));
		map[x][y] = count;
		while (!q.isEmpty()) {
			Point p = q.remove();
			for (int i = 0; i < 4; i++) {
				int x1 = p.x + dir[i][0];
				int y1 = p.y + dir[i][1];
				if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m || map[x1][y1] != 1) {
					continue;
				}
				map[x1][y1] = count;
				q.add(new Point(x1, y1));
			}
		}

	}

}