[BFS/DFS/MST] 백준 17472번 다리 만들기2 - JAVA

제목부터 무시무시한 문제이다.

무려 BFS / DFS / MST가 모두 쓰이는 문제!

 

 

---

1. 출처

---

 

17472번: 다리 만들기 2

드디어 맞췄다!!! 흑흑

오랜만에 알고리즘을 다시 접하니 까먹은 것도 있어서 다시 공부하고... 다시 풀어보았다.

 

 

 

---

2. 설계

---

 

 

이 문제는 많은 분들이 3step으로 푸는 문제이다.

 

step 1. 섬을 구분한다 -> BFS

step 2. 다리를 만들 수 있는 모든 가짓수를 구한다 -> DFS

step 3. 모든 섬을 연결할 수 있는 최소 길이의 다리 구하기 -> MST

 

차근히 적으며 다시 공부해보자!

 

 

step 1. 섬을 구분한다 -> BFS

//1. 섬 구분 (BFS)
count = 1;
for(int i=0;i<N;i++) {
	for(int j=0;j<M;j++) {
		if(map[i][j]==1 && visited[i][j]==false) {
			BFS(i,j,count);
			count++;
		}
	}
}

(0,0)부터 (N,M)까지 모든 칸을 확인하면서 1인 영역(섬영역)을 BFS함수로 보낸다.

 

//섬의 구분을 지어주는 함수 count는 섬의 번호 
public static void BFS(int startR, int startC, int count) { 
	Queue<Node> q = new LinkedList<Node>();
		
	q.add(new Node(startR,startC));
	visited[startR][startC]=true;
		
	while(!q.isEmpty()) {
		Node curNode = q.poll();
		map[curNode.x][curNode.y]=count;
			
		//현재 위치와 근접한 위치들 넣기 
		for(int d=0;d<4;d++) {
			int nextR = curNode.x+drc[d][0];
			int nextC = curNode.y+drc[d][1];
				
			//경계체크
			if(nextR<0||nextR>=N || nextC<0 || nextC>=M) continue;
				
			//방문하지 않은 노드, 큐에 들어가지 않은 노드 
			if(map[nextR][nextC]==1 && !visited[nextR][nextC]) {
				q.add(new Node(nextR, nextC));
				visited[nextR][nextC]=true;
			}
		}
			
	}
		
}

그러면 첫 위치를 큐에 넣고, 방문처리를 한다.

그 이후 이 큐 안의 데이터를 다 쓸 때까지 while을 돌리며, 첫 위치 근처에 있는 섬(상/하/좌/우) 요소를 다시 큐에 넣고, 빼고, 근처 섬 요소 넣고를 반복하여, 섬을 구분하는 것이다.

 

큐에 나올 때가 아닌 들어갈 때 방문처리를 해주는 이유는 똑같은 위치가 2번 이상 큐에 들어가는 것을 막기 위함이다.

시뮬레이션을 1~2번해서는 이해가 안가는데 3번부터 들어갔던 위치가 또 들어가는 현상을 볼 수 있을 것이다 ^^

 

 

 

step 2. 다리를 만들 수 있는 모든 가짓수를 구한다 -> DFS

//2. 다리 만들 수 있는 곳 모두 pq 넣기 
//0이상인 지점 선택해 다리 만들기로 보내주기 
for(int i=0;i<N;i++) {
	for(int j=0;j<M;j++) {
		if(map[i][j]>=1) {
			//하나의 섬에 대해 4방탐색 -> dfs 
			for(int d=0;d<4;d++) {
				bridge(i,j,d, map[i][j],-1);
			}
		}
	}
}

이번에도 (0,0)부터 (N,M)까지 모든 칸을 확인하면서 1인 영역(섬영역)을 bridge(DFS)함수로 보낸다.

여기서는 4방으로 다리를 만들 수 있는지 확인해야하기 때문에 한 섬의 영역에 대해 4방을 차근히 보내줄 것이다.

 

//0이 있는 곳이 상/하/좌/우 인지 따져서 그 길로 쭉 갔을 때
//경계 밖이면 다리를 만들 수 없다.
//섬을 만나면 다리를 만들 수 있다.
//4방 중 다리를 만들 수 있는 최소 거리를 구할 것 
//다리의 길이는 2 이상이다. 
public static void bridge(int r, int c, int direc, int island, int len) {
	//다른 섬을 만났다.
	if(map[r][c]!=0 && map[r][c]!=island) {
		//길이가 2이상인 것만 넣어라 -> 다른 섬 만났으니 종료 
		if(len>=2) pq.add(new Bridge(island, map[r][c],len));
		return;
	}
		
	int nextR = r+drc[direc][0];
	int nextC = c+drc[direc][1];
		
	//경계체크 
	if(nextR<0||nextR>=N||nextC<0||nextC>=M) return;
	if(map[nextR][nextC]==island) return;
	bridge(nextR, nextC, direc, island, len+1);
}

 

만약 내 섬과 다른 숫자의 섬을 만났다.

다리의 길이가 2 이상일 경우에만 유효하기 때문에 2이상일 경우 pq에 넣어준다.

pq를 쓰는 이유는 이 문제에서 다리가 가장 짧은 경우를 구하기 때문이다.

 

이 파트에서 내가 삽질을 많이 했다. 그 이유는 아래처럼 코드를 짰기 때문이다.

 

[오답]

//다른 섬을 만났다.
if(map[r][c]!=0 && map[r][c]!=island && len>=2) {
	//길이가 2이상인 것만 넣어라 -> 다른 섬 만났으니 종료 
	pq.add(new Bridge(island, map[r][c],len));
	return;
}

길이가 1이더라도 다른 섬을 만나면 무조건 종료를 해주어야 하는데, 길이가 1인 섬은 종료 조건에 들어가지도 못하니... 아래에서 길이가 1이 더 추가되고 나서야 길이가 2 이상이 되어서 pq에 들어가는 현상이 보이는 것이다. (섬은 여러 위치가 모여있기 때문에...)

 

왜 틀렸는지 못찾아서 한참을 헤메다가 시뮬레이션 3번해보고 알게 되었다 ㅎㅎ;;

왜 길이가 1인 지역이 2로 들어갔는지에 대해 연구했다...

 

 

step 3. 모든 섬을 연결할 수 있는 최소 길이의 다리 구하기 -> MST

모든 다리 경우 수를 구했다면, 그 다리 중에서 싸이클이 생기지 않는 모든 섬이 연결될 수 있는 다리를 구해야 한다.

프림이라는 방법도 있겠지만, 크루스칼을 사용해볼 것이다.

 

public static void setP() {
	for(int i=1;i<count;i++) {
		p[i]=i;
		rank[i]=0;
	}
}

크루스칼은 먼저 부모를 나 자신으로 셋팅하는 과정부터 시작한다.

 

public static int find(int child) {
	if(p[child]==child) return child;
	else return p[child]=find(p[child]);
}

그 후 자식의 찐 부모를 찾아주는 함수를 이용해

 

public static void union(int c1, int c2) {
	int p1 = find(c1);
	int p2 = find(c2);
		
	if(rank[p1]>rank[p2]) {
		p[p2]=p1;
		rank[p1]++;
	}else if(rank[p1]<=rank[p2]) {
		p[p1]=p2;
		rank[p2]++;
	}
}

자식 1의 부모와 자식 2의 부모가 같지 않다면, 연결되어 있지 않은 것이기 때문에 거느린 자식이 많은 부모 밑으로 다른 부모를 넣음으로써 연결 시켜준다.

 

사실 이 부분은 출발섬 아래 도착섬을 넣는 식으로 p[p2]=p1으로만 써도 로직은 돌아간다.

 

//3. 최소값부터 확인 후 연결 확인 -> 크루스칼 
p = new int[count];
rank = new int[count];
setP();//부모셋팅 
int pick = 0;//count-1만큼 선택하면 끝 
int result = 0;
	
while(!pq.isEmpty()) {
	Bridge curB = pq.poll();
	if(find(curB.start)==find(curB.end)) {
		continue;
	}
			
	else {
		union(curB.start,curB.end);
		pick++;
		result+=curB.len;
				
		if(pick==count-2) break;
	}
}

//결과도출
if(pick<count-2) System.out.println(-1); //count는 섬 수보다 +1많은 상태 
else System.out.println(result);

또한 섬이 4개라면 다리가 3개일 때 MST가 만족한다. 그 점은 pick 변수로 체크한다.

 

 

---

3. 전체 코드

---

 

package BJ17472;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class 다리만들기2 {
	
	static int N,M;
	static int[][] map;
	static boolean[][] visited;
	static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};//상하좌우 
	static boolean[] connection;
	static int[][] minDistance;
	static PriorityQueue<Bridge> pq = new PriorityQueue<>();
	static int count;
	static int[] p, rank;

	
	public static class Node{
		int x;
		int y;
		
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static class Bridge implements Comparable<Bridge>{
		int start;
		int end;
		int len;
		
		public Bridge(int start, int end, int len) {
			this.start = start;
			this.end = end;
			this.len = len;
		}

		@Override
		public int compareTo(Bridge o) {
			return this.len>o.len?1:-1;
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt(); //세로길이
		M = sc.nextInt(); //가로길이 
		
		//초기화
		map = new int[N][M];
		visited = new boolean[N][M];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				map[i][j]=sc.nextInt();
			}
		}
		
		//입력 받기 끝 
		
		//1. 섬 구분 (BFS)
		count = 1;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]==1 && visited[i][j]==false) {
					BFS(i,j,count);
					count++;
				}
			}
		}
		
		
		//2. 다리 만들 수 있는 곳 모두 pq 넣기 
		//0이상인 지점 선택해 다리 만들기로 보내주기 
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]>=1) {
					//하나의 섬에 대해 4방탐색 -> dfs 
					for(int d=0;d<4;d++) {
						bridge(i,j,d, map[i][j],-1);
					}
				}
			}
		}
		
		//3. 최소값부터 확인 후 연결 확인 -> 크루스칼 
		p = new int[count];
		rank = new int[count];
		setP();//부모셋팅 
		int pick = 0;//count-1만큼 선택하면 끝 
		int result = 0;
	
		while(!pq.isEmpty()) {
			Bridge curB = pq.poll();
			if(find(curB.start)==find(curB.end)) {
				continue;
			}
			
			else {
				union(curB.start,curB.end);
				pick++;
				result+=curB.len;
				
				if(pick==count-2) break;
			}
		}

		
		if(pick<count-2) System.out.println(-1); //count는 섬 수보다 +1많은 상태 
		else System.out.println(result);

	}
	
	//섬의 구분을 지어주는 함수 count는 섬의 번호 
	public static void BFS(int startR, int startC, int count) { 
		Queue<Node> q = new LinkedList<Node>();
		
		q.add(new Node(startR,startC));
		visited[startR][startC]=true;
		
		while(!q.isEmpty()) {
			Node curNode = q.poll();
			map[curNode.x][curNode.y]=count;
			
			//현재 위치와 근접한 위치들 넣기 
			for(int d=0;d<4;d++) {
				int nextR = curNode.x+drc[d][0];
				int nextC = curNode.y+drc[d][1];
				
				//경계체크
				if(nextR<0||nextR>=N || nextC<0 || nextC>=M) continue;
				
				//방문하지 않은 노드, 큐에 들어가지 않은 노드 
				if(map[nextR][nextC]==1 && !visited[nextR][nextC]) {
					q.add(new Node(nextR, nextC));
					visited[nextR][nextC]=true;
				}
			}
			
		}
		
	}
	
	//0이 있는 곳이 상/하/좌/우 인지 따져서 그 길로 쭉 갔을 때
	//경계 밖이면 다리를 만들 수 없다.
	//섬을 만나면 다리를 만들 수 있다.
	//4방 중 다리를 만들 수 있는 최소 거리를 구할 것 
	//다리의 길이는 2 이상이다. 
	public static void bridge(int r, int c, int direc, int island, int len) {
		//다른 섬을 만났다.
		if(map[r][c]!=0 && map[r][c]!=island) {
			//길이가 2이상인 것만 넣어라 -> 다른 섬 만났으니 종료 
			if(len>=2) pq.add(new Bridge(island, map[r][c],len));
			return;
		}
		
		int nextR = r+drc[direc][0];
		int nextC = c+drc[direc][1];
		
		//경계체크 
		if(nextR<0||nextR>=N||nextC<0||nextC>=M) return;
		if(map[nextR][nextC]==island) return;
		bridge(nextR, nextC, direc, island, len+1);
	}
	
	public static void setP() {
		for(int i=1;i<count;i++) {
			p[i]=i;
			rank[i]=0;
		}
	}
	
	public static int find(int child) {
		if(p[child]==child) return child;
		else return p[child]=find(p[child]);
	}
	
	public static void union(int c1, int c2) {
		int p1 = find(c1);
		int p2 = find(c2);
		
		if(rank[p1]>rank[p2]) {
			p[p2]=p1;
			rank[p1]++;
		}else if(rank[p1]<=rank[p2]) {
			p[p1]=p2;
			rank[p2]++;
		}
	}
	
}

끝!