[BOJ 17472] 다리만들기2

문제

• BOJ 17472
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

먼저 입력값을 map[][]에 담고 for문을 돌면서 땅마다 각 섬의 번호를 붙여준다. 이때 BFS를 사용해서 각 섬에 있는 땅 좌표들을 찾아주고 리스트lands에 저장한다.

코드

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;

//다리 만들기2(BFS+프림)
public class Main {
	static final int MAX_LAND = 6; // 최대 섬의 개수
	static int N, M;
	static int map[][];
	static boolean visited[][]; // 해당 땅에 방문했는지 체크
	static ArrayList<Land>[] islands; // 각 섬에서 모든 땅의 좌표들
	static ArrayList<Bridge>[] bridges; // 각 섬에서 다른 섬까지 놓은 최소 다리 길이
	static int[] di = { -1, 0, 1, 0 }; // 우, 상, 하, 좌
	static int[] dj = { 0, 1, 0, -1 };
	static int islandNum; // 섬개수
	static int Ans; // 최소 다리 길이

	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()); // 가로 크기(열)

		map = new int[N + 1][M + 1];
		visited = new boolean[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		islands = new ArrayList[MAX_LAND + 1];

		// 섬번호 표시하기
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				// 새로운 땅을 만나면 BFS로 인접 좌표 찾기
				if (!visited[i][j] && map[i][j] == 1) {
					// 해당 땅에 섬번호를 적어주고
					++islandNum;
					map[i][j] = islandNum;
					// 이 섬에 있는 모든 땅의 좌표 구하기
					ArrayList<Land> lands = bfs(i, j, islandNum);
					islands[islandNum] = new ArrayList<>();
					islands[islandNum].addAll(lands);
				}
			}
		}

		bridges = new ArrayList[islandNum + 1]; // 1번섬부터 시작
		for (int i = 1; i <= islandNum; i++)
			bridges[i] = new ArrayList<>();

		// 각 섬들의 좌표를 돌면서 다른 섬으로의 다리 만들기
		for (int i = 1; i <= islandNum; i++) {
			ArrayList<Land> lands = islands[i]; // 섬 가져오기

			for (int j = 0; j < lands.size(); j++) { // 이 섬의 땅들 가져오기
				Land l = lands.get(j);

				// 주변이 다리를 만들 수 있는 상황인지 확인
				for (int d = 0; d < 4; d++) {
					int nx = l.x + di[d];
					int ny = l.y + dj[d];

					if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && map[nx][ny] == 0) {
						makeBridge(i, nx, ny, d); // 다리 시작점으로 두고 다리 만들기
					}
				}
			}
		}
		makeMST(); // 최소신장트리 생성
		System.out.println(Ans);
	}

	//섬번호 표시함
	private static ArrayList<Land> bfs(int i, int j, int num) {
		ArrayList<Land> lands = new ArrayList<>(); // 현재 섬에 있는 땅의 좌표
		Queue<Land> queue = new LinkedList<>();
		queue.offer(new Land(i, j));
		lands.add(new Land(i, j));
		visited[i][j] = true; // 방문 표시

		while (!queue.isEmpty()) {
			Land l = queue.poll();
			for (int d = 0; d < 4; d++) {
				int nx = l.x + di[d];
				int ny = l.y + dj[d];

				if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && !visited[nx][ny] && map[nx][ny] == 1) {
					visited[nx][ny] = true; // 방문표시
					map[nx][ny] = num; // 섬번호 표시
					Land newl = new Land(nx, ny);
					queue.offer(newl);
					lands.add(newl);
				}
			}
		}
		return lands;
	}

	//각 섬의 땅에서 다리 놓기
	private static void makeBridge(int num, int x, int y, int d) { // 시작 섬 번호, x좌표, y좌표, 다리 길이
		int nx = x, ny = y;
		int dist = 1; // 다리의 길이

		while (true) {
			// 계속 다리를 놓자
			nx += di[d];
			ny += dj[d];

			if (nx < 1 || nx > N || ny < 1 || ny > M)
				break;

			if (map[nx][ny] != 0) { // 다른 섬을 만나고 다리 길이가 2이상이면
				if(dist >= 2) 
					bridges[num].add(new Bridge(map[nx][ny], dist));
				break;
			}
			dist++;
		}
	}

	//모든 섬을 연결하는 최소 다리길이 구함
	private static void makeMST() {
		PriorityQueue<Bridge> pq = new PriorityQueue<>(); // 우선순위큐 생성
		boolean[] visited = new boolean[islandNum + 1];
		int now = 1; // 섬 1번부터 출발
		visited[now] = true; // 신장트리 넣기

		// 모든 섬 돌기, 이미 방문한 섬으로 돌아가지x
		for (int cnt = 1; cnt < islandNum; cnt++) {
			ArrayList<Bridge> nowBridges = bridges[now]; // 현재 섬에서 연결된 다리 정보
			for (Bridge b : nowBridges) {
				if (!visited[b.num]) {// 연결된 섬이 아직 신장트리가 아니면
					pq.add(b); // 후보 다리로 추가
				}
			}

			while (!pq.isEmpty()) {
				Bridge bridge = pq.poll(); // 최소 간선 정점
				if (!visited[bridge.num]) { // 아직 방문하지 않은 섬이라면
					visited[bridge.num] = true; // 방문 처리
					Ans += bridge.dist; // 최소 가중치 누적 합
					now = bridge.num; // 이제 다음 섬으로 두기
					break;
				}
			}
		}
		
		//하나라도 방문 안한 섬이 있으면 -1출력
		for(int i=1; i<=islandNum; i++) {
			if(!visited[i]) {
				Ans = -1;
				break;
			}
		}
	}

	// 땅 좌표
	static class Land { 
		int x;
		int y;

		public Land(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	// 현재 섬에서 다리 정보
	static class Bridge implements Comparable<Bridge> { 
		int num;
		int dist;

		public Bridge(int num, int dist) {
			this.num = num;
			this.dist = dist;
		}

		@Override
		public int compareTo(Bridge o) {
			return Integer.compare(this.dist, o.dist);
		}
	}
}