[백준] 17472 다리만들기2

1. 문제

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

2. 접근방법

bfs or dfs 와 MST를 이용한 시뮬레이션 문제

삼성 기출문제라 그런지 구현하기가 복잡~하다.

우선 모든 맵을 돌면서 땅을 만나면 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 

요런식으로?

 

 

이후 모든 땅에서 4방으로 쭉쭉 퍼져 나가면서 

다른 숫자땅을 만나면 출발점 도착점 거리 저장

 

이렇게 하면 연결 가능한 모든 간선이 이어진 그래프가 만들어진다.

 

요거를 가져다 크루스칼로 MST를 구하면 끝이난다.

3. 풀이

1. 맵과 그룹화 할 때 쓸 visit생성

2. 0,0 부터 끝까지 다 돌면서 아직 그룹화 안된 땅을 발견하면 그룹화 고고

3. bfs돌면서 모든 연결된 땅들을 같은 숫자로 바꿔주기

4. 그룹화가 끝나면 인접행렬을 만들어서 모든 땅에서 출발해 

4-1. 벽을 만나거나 자기자신과 같은 땅을 만나면 끝내고

4-2. 다른 숫자 땅을 만나면 출발번호와 도착번호 그리고 도착하기까지 거리를 저장해둔다.

4-3. 만약 똑같은 땅에 또 도착하면 더 짧은 거리를 저장한다.

5. Node클래스 만들어서 모든 노드들의 시작점, 끝점, 거리를 저장하여 List에 넣기

6. 거리 기준 오름차순 정렬해서 하나씩 빼가면서 순환이 안생기면 연결  //union find 사용

7. 연결된 거리들 다 더해서 결과 출력

4. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class P17472다리만들기2 {

	static int N, M, Map[][];
	static int groupNum = 1;
	static boolean visit[][];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	static int Matrix[][];

	public static void main(String[] args) throws Exception {

		// 일단 bfs로 모든 땅 그룹화
		// 땅에서 갈수 있는 모든길 탐색?
		// 끝에 도달하면 길 삭제 다른 땅 만나면 인접행렬에 거리랑 땅 추가
		// 같은 땅이면 거리 더 작은걸로 추가
		// 크루스칼 고고
		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][M];
		visit = new boolean[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());
			}
		}

		for (int i = 0; i < N; i++) { // 모든점 검사해서 bfs로 그룹핑 해보자
			for (int j = 0; j < M; j++) {
				if (Map[i][j] == 0)
					continue;
				if (visit[i][j])
					continue;
				grouping(i, j);
				groupNum++;
			}
		}
		
		Matrix = new int[groupNum][groupNum]; // 인접 행렬 마지막 그룹숫자 +1 되어있음
		// 각 땅에서 갈 수 있는 방향으로 다 펼쳐서 인접행렬 완성하자
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) { // 땅이라면 모든 방향으로 펼쳐보자
				if (Map[i][j] == 0)
					continue;
				spread(i, j);

			}
		}
		//크루스칼 귀찮다아아아
		ArrayList<Node> nodelist = new ArrayList<Node>();
		//인접행렬 꺼내다 노드리스트에 ㄱㄱ 안겹치게 넣어야지
		for(int i = 1 ; i < groupNum ; i++) {
			for(int j = i+1 ; j < groupNum ; j++) {
				if(Matrix[i][j] == 0)
					continue;
				nodelist.add(new Node(i, j, Matrix[i][j]));
			}
		}
		
		Collections.sort(nodelist);
		int result = 0;
		parents = new int [groupNum];
		for(int i = 0 ; i < groupNum ; i++)
			parents[i] = i;
		int cnt = 0;
		for(Node node : nodelist) {
			if(find(node.from) == find(node.to))
				continue;
			union(node.from,node.to);
			cnt++;
			result += node.dist;
			if(cnt == groupNum -2)
				break;
		}
		if(cnt < groupNum -2)
			result = -1;
		System.out.println(result);
		


	}
	static int parents[];
	static void union(int i, int j) {
		int px = find(i);
		int py = find(j);
		
		parents[px] = py;
		
	}
	static int find(int i) {
		
		if(i == parents[i])
			return i;
		
		return parents[i] = find(parents[i]);
	}
	
	static class Node implements Comparable<Node> {
		int from;
		int to;
		int dist;
		public Node(int from, int to, int dist) {
			super();
			this.from = from;
			this.to = to;
			this.dist = dist;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.dist - o.dist;
		}
		
		
	}

	static void grouping(int i, int j) {
		Queue<Point> que = new LinkedList<Point>();
		que.offer(new Point(i, j));
		visit[i][j] = true;
		Map[i][j] = groupNum;
		while (!que.isEmpty()) {
			Point now = que.poll();
			for (int d = 0; d < 4; d++) {
				int row = now.x + dr[d];
				int col = now.y + dc[d];
				if (row < 0 || col < 0 || row >= N || col >= M)
					continue;
				if (Map[row][col] == 0)
					continue;
				if (visit[row][col])
					continue;
				visit[row][col] = true;
				Map[row][col] = groupNum;
				que.offer(new Point(row, col));
			}
		}
	}

	static void spread(int i, int j) {
		for (int d = 0; d < 4; d++) {
			int row = i;
			int col = j;
			int me = Map[i][j];
			int dist = 0;
			while (true) {
				row = row + dr[d];
				col = col + dc[d];
				if (row < 0 || col < 0 || row >= N || col >= M)
					break;
				if (Map[row][col] == me)
					break;
				if (Map[row][col] != 0) {
					if(dist == 1)
						break;
					int target = Map[row][col];
					
					if (Matrix[me][target] == 0 || Matrix[me][target] > dist) { //안채워 졌거나 원래 거리보다 더 짧은 다리 일때만
						Matrix[me][target] = Matrix[target][me] = dist;
					}
					break;
				}
				dist++;
			}

		}

	}
}

5. 마치며

짜고 보니 코드가 너무 긴거 같기도 하고 ..

삼성 기출은 정말 체력기르기에는 좋은 문제들 같다;;