[백준] 17472번 다리 만들기 2 (C++, JAVA)

17472번: 다리 만들기 2

프로그래머스 지형 이동과 비슷한 문제이다.

 

1. BFS로 섬의 번호를 매겨준다.

 

2. 섬과 섬 사이의 거리의 최솟값을 그래프에 저장한다.

1) 가로 방향 다리

모든 행을 검사하면서

A섬 끝→B섬 시작

일 때가 다리를 놓는 경우이므로

파란색 화살표일 경우에만 그래프에 저장한다.

이때 거리는 1보다 커야 하고

A섬→B섬에 이미 거리가 저장되어 있으면

그 거리와 현재 거리를 비교하여 더 작은 값을 넣어준다.

 

2) 세로 방향 다리

모든 열을 검사하는 것 빼고는

1)과 같다.

 

3. 크루스칼 알고리즘을 이용하여 최소 스패닝 트리(MST)를 구한다.

Edge 클래스를 만들어

벡터에 Edge 타입(노드 1, 노드 2, 간선)으로 그래프 값을 옮겨 담는다.

이때 벡터의 크기가 0일 땐 다리를 놓을 수 없는 경우이므로

-1을 출력한다.

 

그게 아니라면

간선을 기준으로 오름차순 한 뒤

값이 가장 작은 간선부터 result에 더해준다.

이때 사이클이 발생하면 다음 간선으로 넘어간다.

 

연산이 끝났는데도 모든 노드의 부모가 통일되지 않은 경우는 -1을 출력하고

정상적으로 MST가 만들어진 경우엔 result를 출력한다.

 

< C++ 코드 >

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, num, x, y, res;
int arr[10][10], dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 }, graph[7][7], cycle[7];
bool visited[10][10] = { false };
queue <pair<int, int>> q;

int FindParent(int parent[], int x) { //부모 찾기
	if (parent[x] == x) return x;
	return parent[x] = FindParent(parent, parent[x]);
}

void UnionParent(int parent[], int a, int b) { //부모 통일
	a = FindParent(parent, a);
	b = FindParent(parent, b);
	if (a < b) parent[b] = a; //더 작은 값을 부모로 설정
	else parent[a] = b;
}

bool Check(int parent[], int a, int b) { //같은 부모를 가지는지 확인(=사이클인 경우)
	a = FindParent(parent, a);
	b = FindParent(parent, b);
	if (a == b) return true;
	else return false;
}

class Edge {
public:
	int a, b;
	int distance;
	Edge(int a, int b, int distance) {
		this->a = a;
		this->b = b;
		this->distance = distance;
	}
	bool operator < (Edge &edge) { //오름차순 정렬하기 위해 연산자 '<' 오버로딩
		return this->distance < edge.distance;
	}
};

void Bfs(int i, int j, int cnt) {
	q.push(make_pair(i, j)), visited[i][j] = true, arr[i][j] = cnt;
	while (!q.empty()) {
		for (int k = 0; k < 4; k++) {
			x = q.front().first + dx[k], y = q.front().second + dy[k];
			if (x >= 0 && x < N && y >= 0 && y < M && !visited[x][y] && arr[x][y] == 1) {
				q.push(make_pair(x, y)), visited[x][y] = true, arr[x][y] = cnt;
			}
		}
		q.pop();
	}
}

int main() {
	cin >> N >> M;
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) cin >> arr[n][m];
	}
	for (int n = 0; n < N; n++) { //섬 번호 부여
		for (int m = 0; m < M; m++) {
			if (!visited[n][m] && arr[n][m] == 1) Bfs(n, m, ++num);
		}
	}
	fill(&graph[0][0], &graph[6][7], 1000);
	for (int i = 0; i < N; i++) { //행 전체 검색
		int group_num = 0, cnt = 1;
		for (int j = 0; j < M; j++) {
			if (arr[i][j] != 0) { //섬 시작
				if (cnt > 1) graph[group_num][arr[i][j]] = min(graph[group_num][arr[i][j]], cnt); //거리의 최솟값 저장
				group_num = arr[i][j];
				for (int k = j + 1; k < M; k++) { //섬 끝
					if (arr[i][k] != group_num || k == M - 1) {
						j = k, cnt = 1;
						break;
					}
				}
			}
			else if (group_num != 0) cnt++;
		}
	}
	for (int i = 0; i < M; i++) { //열 전체 검색
		int group_num = 0, cnt = 1;
		for (int j = 0; j < N; j++) {
			if (arr[j][i] != 0) { //섬 시작
				if (cnt > 1) graph[group_num][arr[j][i]] = min(graph[group_num][arr[j][i]], cnt); //거리의 최솟값 저장
				group_num = arr[j][i];
				for (int k = j + 1; k < N; k++) { //섬 끝
					if (arr[k][i] != group_num || k == N - 1) {
						j = k, cnt = 1;
						break;
					}
				}
			}
			else if (group_num != 0) cnt++;
		}
	}
	vector <Edge> v;
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= num; j++) {
			if (graph[i][j] != 1000) v.push_back(Edge(i, j, graph[i][j]));
		}
	}
	if (!v.size()) cout << -1;
	else {
		sort(v.begin(), v.end()); //오름차순 정렬
		for (int i = 1; i <= num; i++) cycle[i] = i; //사이클 테이블 자기 자신으로 초기화
		for (int i = 0; i < v.size(); i++) {
			if (!Check(cycle, v[i].a, v[i].b)) { //사이클이 아닐 경우
				UnionParent(cycle, v[i].a, v[i].b);
				res += v[i].distance;
			}
		}
		bool nope = false;
		for (int i = 2; i <= num; i++) {
			if (!Check(cycle, i - 1, i)) {
				nope = true;
				break;
			}
		}
		if (nope) cout << -1;
		else cout << res;
	}
	return 0;
}

 

< JAVA 코드 >

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_17472_다리만들기2 {
	static class Edge implements Comparable<Edge>{
		int a, b, weight;
		Edge(int a, int b, int weight) {this.a = a; this.b = b; this.weight = weight;}
		@Override
		public int compareTo(Edge o) {
			return this.weight - o.weight; // 가중치 기준 오름차순 정렬 위해
		}
	}
	static int N, M, num = 1, res = 0;
	static int parentOf[], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	static int map[][];
	static ArrayList<Edge> graph = new ArrayList<>();
	static Queue<int[]> q = new LinkedList<>();
	
	public static void bfs(int X, int Y) {
		q.offer(new int[] {X, Y});
		map[X][Y] = ++num; // 섬 번호 갱신
		while(!q.isEmpty()) {
			for(int i = 0; i < 4; i++) {
				int x = q.peek()[0] + dx[i], y = q.peek()[1] + dy[i];
				if(x < 0 || x >= N || y < 0 || y >= M || map[x][y] != 1) continue; // 범위를 벗어나거나 섬이 아니면 넘김
				map[x][y] = num; // 섬 번호 부여
				q.offer(new int[] {x, y}); // 탐색을 위해 큐에 추가
			}
			q.poll();
		}
	}
	
	static void makeGraph(int X, int Y, int num) {
		for(int i = 0; i < 4; i++) {
			int x = X, y = Y, length = 0;
			while(true) {
				x += dx[i]; y += dy[i];
				if(x < 0 || x >= N || y < 0 || y >= M || map[x][y] == num) break; // 범위를 벗어나거나 자기 섬 만나면 나오기
				if(map[x][y] > 0) { // 다른 섬을 만난다면
					if(length < 2) break; // 다리의 길이가 2 미만이면 그냥 나오기
					graph.add(new Edge(num, map[x][y], length)); // 다리 길이가 2 이상이면 그래프에 추가
					break;
				}
				length++; // 다리 길이 + 1
			}
		}
	}
	
	static int findParent(int x) { // 부모 찾기
		if(parentOf[x] == x) return x;
		return parentOf[x] = findParent(parentOf[x]);
	}
	
	static boolean unionParent(int a, int b) { // 부모 합치기
		int parentOfA = findParent(a), parentOfB = findParent(b);
		if(parentOfA == parentOfB) return false; // 부모가 같으면 false 반환
		parentOf[Math.min(parentOfA, parentOfB)] = Math.max(parentOfA, parentOfB); // 더 큰 값을 부모로 설정
		return true;
	}
	
	public static void main(String[] args) {
		// 0. 입력 및 초기화
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt();
		map = new int[N][M]; parentOf = new int[8];
		for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) map[i][j] = sc.nextInt();
		for(int i = 2; i < 8; i++) parentOf[i] = i; // 부모 배얼이 자기 자신을 가리키도록 초기화
		
		// 1. BFS로 섬 번호 부여
		for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) if(map[i][j] == 1) bfs(i, j);
		
		// 2. 섬을 정점, 다리를 간선으로 여기고 인접행렬로 그래프 생성
		for(int k = 2; k <= num; k++) {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(map[i][j] == k) makeGraph(i, j, k); // 현재 번호를 가진 섬만 체크
				}
			}
		}
		
		// 3. MST - 크루스칼 이용하여 정점을 모두 잇는 간선의 최솟값 찾기
		Collections.sort(graph); // 가중치 기준 오름차순 정렬
		for(int i = 0; i < graph.size(); i++) {
			if(unionParent(graph.get(i).a, graph.get(i).b)) { // 부모가 같으면 사이클이 생기므로 다른 경우에만 res 갱신
				res += graph.get(i).weight;
			}
		}
		
		boolean completeMST = true; // MST 성공 여부 체크
		for(int i = 3; i <= num; i++) if(unionParent(i - 1, i)) completeMST = false; // 모든 부모가 통합되지 않았다는 건 MST 실패라는 뜻 
		
		// 4. 결과 출력
		System.out.println(completeMST ? res : -1); // MST가 만들어지면 결과, 아니면 -1 출력
	}
}