문제출저 : https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
문제 조건
- 그래프 문제(MST 최소신장트리 문제)
- 문제에 대한 자세한 설명은 위에 출처 참조
풀이 과정
1. x축(col)과 y축(row)의 좌표 값을 나타내는 객체 pair가 필요하다고 생각, 나중엔 다리객체도 필요 했음
2. 붙어있는 섬끼리 하나의 묶음으로 만들어야 되는데, 그것을 labeling 이라고 했음
(1) BFS로 labeling
(2) DFS로 labeling
3. 섬과 섬을 연결하는 다리를 찾는 알고리즘을 만들어야됨
4. 만들 수 있는 모든 다리를 다리길이(length)를 이용한 우선순위 큐에 넣었음. (자동정렬됨)
5. Union-Find로 다리길이를 최소화 하여 연결할 수 있는 kruskal 알고리즘을 만들어냄
코드 구현
(1) BFS
package 백준;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Ex_17472_Refactoring {
// 백준 17472, 다리만들기 2 (bfs풀이)(골드3) https://www.acmicpc.net/problem/17472
// pair 좌표 객체
class pair {
int row;
int col;
private pair(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "pair [row=" + row + ", col=" + col + "]";
}
}
class bridge implements Comparable<bridge> {
int FirstIsland;
int SecondIsland;
int length;
public bridge(int FirstIsland, int SecondIsland, int length) {
this.FirstIsland = FirstIsland;
this.SecondIsland = SecondIsland;
this.length = length;
}
@Override
public int compareTo(bridge o) {
return this.length - o.length;
}
}
// 필드
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int[][] map;
int N;
int M;
Queue<bridge> BridgeQue = new PriorityQueue<bridge>();
Queue<pair> IslandQue = new LinkedList<pair>();
int[] parent;
int rowDirect[] = { -1, 1, 0, 0 }; // 상하
int colDirect[] = { 0, 0, -1, 1 }; // 좌우
int answer = 0;
int count = 0; // kruskal의 2번째 조건. 노드가 n개면 MST를 위한 최소 간선개수는 n-1개
int label = 0;
// 주메인 메소드
void myMain() throws IOException {
// 지도 만들기
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int row = 0; row < N; row++) {
st = new StringTokenizer(br.readLine(), " ");
for (int col = 0; col < M; col++) {
if (Integer.parseInt(st.nextToken()) == 1) {
map[row][col] = -1;
}
}
}
// 섬 labeling (bfs)
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
if (map[row][col] == -1) {
IslandQue.offer(new pair(row, col));
labeling(row, col, ++label); // bfs로 구현
}
}
}
// 다리 찾기
findBridge();
// union-find로 kruskal 구현
findMST();
// 정답 출력
if (answer == 0 || count != label - 1) {
bw.write(-1 + "");
} else {
bw.write(answer + "");
}
bw.flush();
br.close();
bw.close();
} // end of myMain
void findMST() {
parent = new int[label + 1];
for (int i = 1; i < label + 1; i++) {
parent[i] = i;
}
while (!BridgeQue.isEmpty()) {
bridge temp = BridgeQue.poll();
union(temp.FirstIsland, temp.SecondIsland, temp.length);
}
} // end of findMST
int find(int i) {
if (parent[i] == i) {
return i;
}
return parent[i] = find(parent[i]);
} // end of find
void union(int FirstIsland, int SecondIsland, int length) {
int FirstParent = find(FirstIsland);
int SecondParent = find(SecondIsland);
if (FirstParent == SecondParent) {
return;
} else if (FirstParent < SecondParent) {
parent[SecondParent] = FirstParent;
} else {
parent[FirstParent] = SecondParent;
}
count++;
answer += length;
}
void findBridge() {
while (!IslandQue.isEmpty()) {
pair temp = IslandQue.poll();
int landlabel = map[temp.row][temp.col];
for (int i = 0; i < 4; i++) {
int tr = temp.row + rowDirect[i];
int tc = temp.col + colDirect[i];
int length = 0;
while (tr >= 0 && tc >= 0 && tr < N && tc < M) {
if (map[tr][tc] != 0) {
if (landlabel < map[tr][tc] && length >= 2) {
BridgeQue.add(new bridge(map[temp.row][temp.col],
map[tr][tc], length));
}
break;
}
tr += rowDirect[i];
tc += colDirect[i];
length++;
} // end of inner while
}// end of for
}// end of while
}
void labeling(int row, int col, int label) { // bfs로 처리
Queue<pair> q = new LinkedList<pair>();
map[row][col] = label;
q.offer(new pair(row, col));
while (!q.isEmpty()) {
pair temp = q.poll();
// 상하 좌우 검사
for (int i = 0; i < 4; i++) {
int tr = temp.row + rowDirect[i]; // tempRow로 바꾸면 배열에 들어오는 변수의 길이가 길어져 보기 불편함.
int tc = temp.col + colDirect[i];
if (tr >= 0 && tc >= 0 && tr < N && tc < M && map[tr][tc] == -1) { // 맵 안에 들어오고
map[tr][tc] = label;
q.offer(new pair(tr, tc));
IslandQue.offer(new pair(tr, tc));
}
}
}
} // end of labeling method
public static void main(String[] args) throws IOException {
Ex_17472_Refactoring my = new Ex_17472_Refactoring();
my.myMain();
}
}
- 좌표 class, pair를 만들었다. pair에는 row와 col이 각각 필드로 있다. (1.)
- 다리를 나타내는 class, bridge를 만들었다. brdige의 필드는 처음에 다리를 연결하는 좌표 2개로 생각했어서
필드에 pair 2개로 설정했었는데, 그럴 필요가 없었다. 왜냐하면 섬과 섬 사이를 연결해야 해서 섬의 좌표값이
아닌 그 섬의 대표 label을 입력해주면 되었기 때문이다. (1.)
그리고 섬들을 우선순위 큐 형태에 저장해야 했기에 length로 오름차순 정렬되도록 compateTo를 override 해줬다.
- 섬의 labeling이 중요했다. labeling 개념을 몰랐을 땐 HashMap을 만들고 Key엔 알파벳, 값엔 ArrayList로 pair들을
저장하고 이런 굉장히 복잡한 짓을 했었는데, 이렇게 할 필요 없이 map의 섬 값에 1로 통일하는 것이 아닌
섬 1111, 섬 222222, 섬 33333... 이런 식으로 map에 label을 붙여주면 되었었다. 예를 들면 아래 그림처럼(2.)
- bfs는 링크드 리스트로 만든 큐 객체 q에 저장하고 꺼내서 검사하는 방법으로 했고, 섬들의 모든 pair들을
islandQue라는 큐 객체에 모두 저장했다. (2.)
- islandQue를 모두 꺼내면서 다리를 만들 수 있는지 검사(findBridge 메서드)한다. 다리 검사 알고리즘은.. 설명생략(3.)
- 만들 수 있는 모든 다리를 우선순위 큐인 pq에 모두 저장했으면(4.), 그것을 하나씩 꺼내면서 union-find 한다.(5)
이때 주의할 점은 kruskal 알고리즘에서 cycle이 돌면 안 되고 다리개수는 항상 노드개수 - 1 이어야한다.
count변수를 만들어서 다리 개수가 섬의 개수 - 1 인지 검사해주자 !!
(2) DFS
package 백준;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Ex_17472 {
// 백준 17472, 다리만들기 2 (dfs풀이)(골드3) https://www.acmicpc.net/problem/17472
// pair 좌표 객체
class pair {
int row;
int col;
private pair(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "pair [row=" + row + ", col=" + col + "]";
}
}
class bridge implements Comparable<bridge> {
int FirstIsland;
int SecondIsland;
int length;
public bridge(int FirstIsland, int SecondIsland, int length) {
this.FirstIsland = FirstIsland;
this.SecondIsland = SecondIsland;
this.length = length;
}
@Override
public int compareTo(bridge o) {
return this.length - o.length;
}
}
// 필드
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int[][] map;
boolean[][] visited;
int N;
int M;
Queue<bridge> BridgeQue = new PriorityQueue<bridge>();
Queue<pair> IslandQue = new LinkedList<pair>();
int[] parent;
int rowDirect[] = { -1, 1, 0, 0 }; // 상하
int colDirect[] = { 0, 0, -1, 1 }; // 좌우
int answer = 0;
int count = 0; // kruskal의 2번째 조건. 노드가 n개면 MST를 위한 최소 간선개수는 n-1개
int label = 0;
// 주메인 메소드
void myMain() throws IOException {
// 지도 만들기
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
for (int row = 0; row < N; row++) {
st = new StringTokenizer(br.readLine(), " ");
for (int col = 0; col < M; col++) {
if (Integer.parseInt(st.nextToken()) == 1) {
map[row][col] = -1;
}
}
}
// 섬 labeling (dfs)
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
if (map[row][col] == -1) {
IslandQue.offer(new pair(row, col));
labeling(row, col, ++label); // dfs로 구현
}
}
}
// 다리 찾기
findBridge();
// union-find로 kruskal 구현
findMST();
// 정답 출력
if (answer == 0 || count != label - 1) {
bw.write(-1 + "");
} else {
bw.write(answer + "");
}
bw.flush();
br.close();
bw.close();
} // end of myMain
void findMST() {
parent = new int[label + 1];
for (int i = 1; i < label + 1; i++) {
parent[i] = i;
}
while (!BridgeQue.isEmpty()) {
bridge temp = BridgeQue.poll();
union(temp.FirstIsland, temp.SecondIsland, temp.length);
}
} // end of findMST
int find(int i) {
if (parent[i] == i) {
return i;
}
return parent[i] = find(parent[i]);
} // end of find
void union(int FirstIsland, int SecondIsland, int length) {
int FirstParent = find(FirstIsland);
int SecondParent = find(SecondIsland);
if (FirstParent == SecondParent) {
return;
} else if (FirstParent < SecondParent) {
parent[SecondParent] = FirstParent;
} else {
parent[FirstParent] = SecondParent;
}
count++;
answer += length;
}
void findBridge() {
while (!IslandQue.isEmpty()) {
pair temp = IslandQue.poll();
int landlabel = map[temp.row][temp.col];
for (int i = 0; i < 4; i++) {
int tr = temp.row + rowDirect[i];
int tc = temp.col + colDirect[i];
int length = 0;
while (tr >= 0 && tc >= 0 && tr < N && tc < M) {
if (map[tr][tc] != 0) {
if (landlabel < map[tr][tc] && length >= 2) {
BridgeQue.add(new bridge(map[temp.row][temp.col],
map[tr][tc], length));
}
break;
}
tr += rowDirect[i];
tc += colDirect[i];
length++;
} // end of inner while
}// end of for
}// end of while
}
void labeling(int row, int col, int label) { // dfs로 구현
if (row < 0 || row >= map.length || col < 0 || col >= map[0].length) {
return;
}
if (visited[row][col] || map[row][col] == 0) { // 방문했거나 0이면
return;
}
visited[row][col] = true;
map[row][col] = label;
IslandQue.offer(new pair(row, col));
for (int i = 0; i < 4; i++) {
int tr = row + rowDirect[i];
int tc = col + colDirect[i];
labeling(tr, tc, label);
}
} // end of dfs
public static void main(String[] args) throws IOException {
Ex_17472 my = new Ex_17472();
my.myMain();
}
}
이 알고리즘 에서는 위 BFS와 별 차이가 없었는데, 딱 섬을 labeling하는 과정의 메소드만 딱 다르다.
dfs에서는
(1) 탈출 조건 2개를 이해하고 사용하는 것 !
(2) 탈출하지 않았으면 들어온거니까, 방문처리 그리고 맵에서는 labeling, 섬들의 객체인 islandQue에 저장 한다.
(3) 저장을 다했으면 상하좌우로 연결된 섬이 없는 지 살펴봐야했는데, 이때 dfs의 핵심인 재귀함수가 사용된다.
bfs에서는
(1) 이미 main의 for문에서 검사를 하고 들어왔기 때문에, 방문처리와 labeing, 큐에 인큐를 먼저 시행한다.
(2) 큐에 섬이 없을 때까지를 반복하며 상하좌우를 찾고 저장하고 디큐하면서 검사하고 .. 를 반복한다.
끝으로..
너무 설명이 구어체적이라 저 말고는 이해 못하실 수 있다고 생각합니다.. 더 설명 잘 할 수 있도록 노력하겠습니다.
그래도 이 문제를 끝까지 포기하지 않고 몇 날 몇 시간을 걸쳐서라고 풀어낸 제 자신에게 칭찬은 해주고 싶습니다.
항상 발전하는 개발자가 되자. 화이팅.