Algorithm
[백준 Platinum 5] 3197 백조의 호수 - Java
Ray
2021. 12. 17. 20:08
문제링크 : https://www.acmicpc.net/problem/3197
3197번: 백조의 호수
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
www.acmicpc.net
접근 과정 :
- 접촉되어 있는 물(.)의 칸을 묶어서 영역으로 표현
- 백조 두마리의 영역이 같으면, Return!!
- 같이 않으면, 물과 접촉되어 있는 얼음을 녹임
- 초기 아이디어
- 방금 녹은 물을 나타내는 큐와 다음에 녹을 얼음을 나타내는 큐를 사용.
- 방금 녹은 물의 영역을 체크 -> 백조 두 마리의 영역을 판단 -> 다르면 얼음을 녹임
- (인접한 얼음을 Ice 큐로!!) -> ( 백조의 영역을 비교) -> (녹은 얼음을 water 큐로!!)
- 리팩토링
- 큐를 하나만 사용!!
- 초기 입력시, 물이라면 영역을 표현 (초기 영역은 좌표값으로 계산 (i*C+j+1))
- 얼음을 녹일 때, 바로 영역을 표현. => 큐에 대한 입출력 비용이 줄어듬!!
소스 코드 및 결과 :
package BOJ;
/*
백조의 호수
초기 아이디어
*/
import java.io.*;
import java.util.*;
public class BOJ3197_copy {
static int R, C, areaNum;
static int[][] lake;
static List<int[]> swan;
static int[] area;
static Queue<int[]> ice;
static Queue<int[]> water;
static int[] dr = { 0, 0, -1, 1 };
static int[] dc = { -1, 1, 0, 0 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
lake = new int[R][C];
swan = new ArrayList<>();
ice = new LinkedList<>();
water = new LinkedList<>();
areaNum = 1;
for (int i = 0; i < R; i++) {
char[] line = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
if (line[j] != 'X') {
water.add(new int[] { i, j });
if (line[j] == 'L') {
swan.add(new int[] { i, j });
}
lake[i][j] = areaNum;
areaNum++;
} else {
lake[i][j] = -1;
}
}
}
area = new int[areaNum];
int day = 0;
while (true) {
// 녹은 얼음 영역 체크
checkArea();
if (findArea(lake[swan.get(0)[0]][swan.get(0)[1]]) == findArea(
lake[swan.get(1)[0]][swan.get(1)[1]])) {
break;
}
day++;
// 접촉된 얼음 녹이기!!
meltIce();
}
System.out.println(day);
}
static void checkArea() {
boolean[][] visit = new boolean[R][C];
int size = water.size();
int a = 0;
int b = 0;
while (size-- > 0) {
int[] w = water.poll();
if (visit[w[0]][w[1]]) {
continue;
}
visit[w[0]][w[1]] = true;
a = findArea(lake[w[0]][w[1]]);
for (int i = 0; i < 4; i++) {
int nr = w[0] + dr[i];
int nc = w[1] + dc[i];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || visit[nr][nc]) {
continue;
}
if (lake[nr][nc] == -1) {
visit[nr][nc] = true;
ice.add(new int[] { nr, nc, a });
continue;
}
b = findArea(lake[nr][nc]);
if (a != b) {
area[b] = a;
}
}
}
return;
}
static void meltIce() {
int size = ice.size();
boolean[][] visit = new boolean[R][C];
while (size-- > 0) {
int[] i = ice.poll();
if (visit[i[0]][i[1]]) {
continue;
}
visit[i[0]][i[1]] = true;
lake[i[0]][i[1]] = i[2];
water.add(new int[] { i[0], i[1] });
for (int d = 0; d < 4; d++) {
int nr = i[0] + dr[d];
int nc = i[1] + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || visit[nr][nc]) {
continue;
}
if (lake[nr][nc] == -1) {
ice.add(new int[] { nr, nc, i[2] });
}
}
}
return;
}
static int findArea(int n) {
if (area[n] == 0) {
return n;
}
return area[n] = findArea(area[n]);
}
}
package BOJ;
/*
백조의 호수
리팩토링
*/
import java.io.*;
import java.util.*;
public class BOJ3197 {
static int R, C;
static char[][] lake;
static List<Integer> swan;
static int[] area;
static Queue<int[]> water;
static int[] dr = { 0, 0, -1, 1 };
static int[] dc = { -1, 1, 0, 0 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
lake = new char[R][C];
swan = new ArrayList<>();
water = new LinkedList<>();
area = new int[R * C + 2];
for (int i = 0; i < R; i++) {
String input = br.readLine();
for (int j = 0; j < C; j++) {
lake[i][j] = input.charAt(j);
if (lake[i][j] != 'X') {
if (lake[i][j] == 'L') {
swan.add(i * C + j + 1);
}
checkArea(i, j);
}
}
}
int day = 0;
while (true) {
if (findArea(swan.get(0)) == findArea(swan.get(1))) {
break;
}
day++;
// 접촉된 얼음 녹이기!!
meltIce();
}
System.out.println(day);
}
static void checkArea(int r, int c) {
lake[r][c] = '.';
water.add(new int[] { r, c });
int a = findArea(r * C + c + 1);
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
continue;
}
if (lake[nr][nc] == '.') {
int b = findArea(nr * C + nc + 1);
if (a != b) {
area[b] = a;
}
}
}
return;
}
static void meltIce() {
int size = water.size();
while (size-- > 0) {
int[] w = water.poll();
for (int i = 0; i < 4; i++) {
int nr = w[0] + dr[i];
int nc = w[1] + dc[i];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
continue;
}
if (lake[nr][nc] == 'X') {
checkArea(nr, nc);
}
}
}
return;
}
static int findArea(int n) {
if (area[n] == 0) {
return n;
}
return area[n] = findArea(area[n]);
}
}
P.S
문제는 빠르게 풀었으나, 리팩토링이 오래걸렸다....