Algorithm
[Java] BaekJoon 3197. 백조의호수(BFS) (플레5)
Per ardua ad astra !
2021. 12. 8. 14:53
문제출처: https://www.acmicpc.net/problem/3197
3197번: 백조의 호수
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
www.acmicpc.net
문제이해
목표
2마리의 백조가 호수에서 살고 있다. 이 둘을 만나게 해주자 !
- map에는 빙판과 물이 존재한다.
- 백조는 물 위로 밖에 다닐 수 없다.
- 물을 끼고 있는 빙판은 하루가 지나면 녹아 물이 된다.
며칠이 지나여 백조들이 만날 수 있는지 계산해보자 !
풀이
2개의 BFS 진행이 필요하다 !!
[1] 백조1을 기준으로 BFS(백조2를 찾기위한)를 실시 탐색
=> nowQueue: 백조1이 돌아다닐 수 있는 물 정보를 담은 큐
=> nextQueue: BFS 중에 빙판을 만나서 다음날 탐색을 할 수 있는 큐
1. 백조1 기준으로 BFS
-> 뭘 만나든 모두 방문처리 (백조1의 기준)
-> 웅덩이('.')인 경우 - 계속 탐색
-> 빙판('X')인 경우 - 빙판 노드를 다음에 탐색할 nextQueue에 저장 후 멈춤
-> 백조2('L')인경우 - 정답 처리
2. 하루가 지나면 nowQueue는 nextQueue가 되고 nextQueue는 초기화가 된다.
answer++;
[2] 얼음 녹이기 (waterQueue)
- 초기: 모든 물은 waterQueue 저장
- 반복: [1]의 BFS가 끝날 때 마다, 탐색길이 1만큼의 BFS로 물에 닿은 얼음 녹임
-> 얼음을 녹인경우, 해당 얼음자리의 Pair값을 waterQueue에 다시 넣음
-> 그리고
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class 백조의호수 {
private static Queue<Pair> nowQueue;
private static Queue<Pair> nextQueue;
private static Queue<Pair> waterQueue;
static class Pair {
int row;
int col;
public Pair(int row, int col) {
this.row = row;
this.col = col;
}
}
private static int R;
private static int C;
private static char[][] map;
private static boolean[][] visited;
public static Pair[] swans;
private static int[] dr = {-1, 1, 0, 0};
private static int[] dc = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력받고 map, Queue 만들기
String[] strArr = br.readLine().split(" ");
R = Integer.parseInt(strArr[0]);
C = Integer.parseInt(strArr[1]);
map = new char[R][C];
visited = new boolean[R][C];
swans = new Pair[2];
nowQueue = new LinkedList<>();
waterQueue = new LinkedList<>();
String str;
int swanCount = 0;
for (int row = 0; row < R; row++) {
str = br.readLine();
for (int col = 0; col < C; col++) {
map[row][col] = str.charAt(col);
if (map[row][col] == 'L') {
swans[swanCount++] = new Pair(row, col);
}
if (map[row][col] != 'X' ) {
waterQueue.add(new Pair(row, col));
}
}
}
// 큐 두개를 활용한 BFS 알고리즘
nowQueue.add(swans[0]);
visited[swans[0].row][swans[0].col] = true;
int answer = 0;
outer:
while (true) {
// 길이 1만큼 BFS 물이 빙판 녹이기
nextQueue = new LinkedList<>();
while (!nowQueue.isEmpty()) {
Pair pair = nowQueue.poll();
int row = pair.row;
int col = pair.col;
// 1칸 이동
for (int i = 0; i < 4; i++) {
int tr = dr[i] + row;
int tc = dc[i] + col;
if (tr >= 0 && tc >= 0 && tr < R && tc < C && !visited[tr][tc]) {
visited[tr][tc] = true;
if (map[tr][tc] == 'X') {
nextQueue.add(new Pair(tr, tc));
} else if(map[tr][tc] == '.'){
nowQueue.add(new Pair(tr, tc));
} else{ // 2번째 swan을 찾으면 나가자
break outer;
}
}
}
}
int waterQueueSize = waterQueue.size();
for (int i = 0; i < waterQueueSize; i++) {
Pair pair = waterQueue.poll();
int row = pair.row;
int col = pair.col;
for (int j = 0; j < 4; j++) {
int tr = dr[j] + row;
int tc = dc[j] + col;
if (tr >= 0 && tc >= 0 && tr < R && tc < C && map[tr][tc] == 'X') {
map[tr][tc] = '.';
waterQueue.add(new Pair(tr, tc));
}
}
}
nowQueue = nextQueue;
answer++;
}
System.out.println(answer);
}
}
실패한 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class 백조의호수Fail {
private static Queue<Pair> queue;
static class Pair {
int row;
int col;
public Pair(int row, int col) {
this.row = row;
this.col = col;
}
}
private static int R;
private static int C;
private static int[][] map;
private static boolean[][] visited;
private static int nodeNum;
private static int[] dr = {-1, 1, 0, 0};
private static int[] dc = {0, 0, -1, 1};
private static int swanNode1 = -1;
private static int swanNode2 = -1;
private static int[] parent;
/*
1. 물이 있는 곳에서 DFS 탐색으로 각 노드(숫자) 표기 - 다수의 그래프 만들기
2. 물이 빙판을 녹인다. (BFS)
3. 녹이고 나서 물끼리 닿았을 때, Union-Find로 각 백조가 속한 물(그래프)가
닿았는지 확인
=> 안닿았다면 2,3과정의 방복
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력받고 map, Queue 만들기
String[] strArr = br.readLine().split(" ");
R = Integer.parseInt(strArr[0]);
C = Integer.parseInt(strArr[1]);
map = new int[R][C];
visited = new boolean[R][C];
queue = new LinkedList<>();
String str;
for (int row = 0; row < R; row++) {
str = br.readLine();
for (int col = 0; col < C; col++) {
if (str.charAt(col) == 'X') {
map[row][col] = -1;
} else {
map[row][col] = str.charAt(col);
}
}
}
// DFS (단지 번호 붙이기)
nodeNum = 0;
for (int row = 0; row < R; row++) {
for (int col = 0; col < C; col++) {
if ((map[row][col] == 'L' || map[row][col] == '.')
&& !visited[row][col]) {
dfs(row, col);
nodeNum++;
} else{
}
}
}
// 그래프 형성하기
int answer = 0;
parent = new int[nodeNum];
for (int i = 0; i < nodeNum; i++) {
parent[i] = i;
}
while (true) {
if (checkAnswer()) {
break;
}
// 길이 1만큼 BFS 물이 빙판 녹이기
initVisited();
while (!queue.isEmpty()) {
Pair pair = queue.poll();
int row = pair.row;
int col = pair.col;
if (map[row][col] != -1 && !visited[row][col]) {
visited[row][col] = true;
// 1칸 이동
for (int i = 0; i < 4; i++) {
int tr = dr[i] + row;
int tc = dc[i] + col;
if (tr >= 0 && tc >= 0 && tr < R
&& tc < C && !visited[tr][tc]
&& map[tr][tc] == -1) {
map[tr][tc] = map[row][col];
visited[tr][tc] = true;
unionAdj(tr, tc);
}
}
}
}
answer++;
}
System.out.println(answer);
}
public static void queueInit(int row, int col) {
for (int i = 0; i < 4; i++) {
int tr = dr[i] + row;
int tc = dc[i] + col;
if (tr >= 0 && tc >= 0 && tr < R && tc < C
&& map[tr][tc] != -1
) {
}
}
}
public static void unionAdj(int row, int col) {
for (int i = 0; i < 4; i++) {
int tr = dr[i] + row;
int tc = dc[i] + col;
if (tr >= 0 && tc >= 0 && tr < R
&& tc < C && map[tr][tc] != -1
&& map[tr][tc] != map[row][col]) {
int p1 = find(map[row][col]);
int p2 = find(map[tr][tc]);
if (p1 != p2) {
union(p1, p2);
}
}
}
}
public static boolean checkAnswer() {
if (find(swanNode1) == find(swanNode2)) {
return true;
} else {
return false;
}
}
public static void initVisited() {
for (boolean[] booleans : visited) {
Arrays.fill(booleans, false);
}
}
public static int find(int node) {
if (node == parent[node]) {
return node;
}
return parent[node] = find(parent[node]);
}
public static void union(int p1, int p2) {
if (p1 == p2) {
return;
} else if (p1 < p2) {
parent[p2] = p1;
} else {
parent[p1] = p2;
}
}
public static void dfs(int row, int col) {
visited[row][col] = true;
if (map[row][col] == 'L') {
if (swanNode1 == -1) {
swanNode1 = nodeNum;
} else {
swanNode2 = nodeNum;
}
}
map[row][col] = nodeNum;
for (int i = 0; i < 4; i++) {
int tr = dr[i] + row;
int tc = dc[i] + col;
if (tr >= 0 && tc >= 0 && tr < R && tc < C && !visited[tr][tc] && map[tr][tc] != -1) {
dfs(tr, tc);
}
}
}
}
실패한 코드 => 메모리 초과 발생
1. 초기에 물 웅덩이 수대로 그래프를 형성하고, 단지 번호 붙이기를 통해 번호 마킹
백조가 어느 물 웅동이 그래프에 속해 있는지 기억
2. 물이 빙하를 녹이고, 물들끼리 접촉했을 때
Union-Find로 백조1의 호수와 백조2의 호수가 맞닿았는지 확인.
3. 맞 닿았으면 정답 도출. 아닌경우 2번 반복
=> 2번에서 물들끼리 접촉했는지 안햇는지를 확인하는 과정에서 비용 소모 큼
그리고 매번 visited 처리를 초기화하고 탐색하는 것도 비용소모가 큼