제목부터 무시무시한 문제이다.
무려 BFS / DFS / MST가 모두 쓰이는 문제!
1. 출처
드디어 맞췄다!!! 흑흑
오랜만에 알고리즘을 다시 접하니 까먹은 것도 있어서 다시 공부하고... 다시 풀어보았다.
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]++;
}
}
}
끝!
'알고리즘 > 백준' 카테고리의 다른 글
[트리] 백준 3584번 가장 가까운 공통 조상 - JAVA (0) | 2023.07.01 |
---|---|
[문자열] 백준 1593번 문자 해독 - JAVA (0) | 2023.06.25 |
[재귀] 백준 2775번 부녀회장이 될테야 - JAVA (2) | 2023.06.21 |
[구현] 백준 2564번 경비원 - JAVA (0) | 2023.06.20 |
[그리디] 백준 26099번 설탕 배달2 - JAVA (3) | 2023.06.20 |