문제 링크

성능 요약

메모리: 243996 KB, 시간: 1232 ms

분류

너비 우선 탐색, 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 25일 23:59:14

문제 설명

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

풀이

느낀점

• 디버깅에 실패해서 수정할때 claude의 도움을 받았다ㅠ (union 로직 디버깅)
• 분리집합을 2차원으로 구현한건 처음이라서 복잡하고 어려웠다. 초기화와 수정부분에 유의해야 한다.
• 효율성이 좀 떨어지는 풀이 같긴 하지만 스스로 설계한 건 이정도였다ㅠ
• static 변수를 이렇게 남발하는게 맞나 싶다..

설계 : 15분

• 분리되어 있는 모든 호수의 부분을 집합으로 처리한다.
• 두 백조가 위치한 호수 집합을 저장한 후, bfs를 통해 얼음을 녹여가면서 두 집합이 만났는지 판단한다.

코드(Java)

• 구현 시간: 120분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 백조의 호수_3197
 * Date: 2025.02.25
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int[][][] p;
	static char[][] lake;
	static int[] a;
	static int[] b;
	static boolean[][] visited;
	static Queue<int[]> will;
	static int[] dr = new int[] {-1, 0, 1, 0};
	static int[] dc = new int[] {0, 1, 0, -1};

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);
		lake = new char[n+2][m+2];
		p = new int[n+2][m+2][2];

		// 호수 입력
		for (int i = 1; i<= n; i++) {
			char[] tmp = br.readLine().toCharArray();
			for (int j = 1; j <= m; j++) {
				lake[i][j] = tmp[j-1];
				p[i][j] = new int[] {i, j};
			}
		}

		will = new ArrayDeque<>();
		a = new int[2];
		b = new int[2];
		visited = new boolean[n+2][m+2];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (!visited[i][j] && (lake[i][j] == '.' || lake[i][j] == 'L')) {
					makeOne(i, j);
				}
			}
		}

		visited = new boolean[n+2][m+2];

		int day = 0;
		while (!will.isEmpty()) {

			if (isConnected()) break;

			int size = will.size();
			for (int i = 0; i < size; i++) {
				int[] curr = will.poll();

				lake[curr[0]][curr[1]] = '.';

				for (int d = 0; d < 4; d++) {
					int nr = curr[0] + dr[d];
					int nc = curr[1] + dc[d];

					if (lake[nr][nc] == '\u0000') continue;
					if (!visited[nr][nc] && lake[nr][nc] == 'X') {
						will.add(new int[] {nr, nc});
						visited[nr][nc] = true;
					}
					else if (lake[nr][nc] == '.' || lake[nr][nc] == 'L') {
						union(curr[0], curr[1], nr, nc);
					}
				}
			}

			day++;
		}

		bw.write(String.valueOf(day));
		bw.flush();
		bw.close();
		br.close();
	}

	public static void union(int r1, int c1, int r2, int c2) {
		int[] root1 = findSet(r1, c1);
		int[] root2 = findSet(r2, c2);

		if (root1[0] == root2[0] && root1[1] == root2[1]) return;

		p[root1[0]][root1[1]] = root2;
	}

	public static int[] findSet(int r, int c) {
		if (p[r][c][0] == r && p[r][c][1] == c) return p[r][c];
		return p[r][c] = findSet(p[r][c][0], p[r][c][1]);
	}

	public static boolean isConnected() {
		int[] A = findSet(a[0], a[1]);
		int[] B = findSet(b[0], b[1]);

        return A[0] == B[0] && A[1] == B[1];
    }

	public static void makeOne(int r, int c) {
		Queue<int[]> queue = new ArrayDeque<>();
		visited[r][c] = true;
		queue.add(p[r][c]);

		while (!queue.isEmpty()) {

			int[] curr = queue.poll();
			if (lake[curr[0]][curr[1]] == 'L') {
				if (a[0] == 0) a = new int[] {curr[0], curr[1]};
				else b = new int[] {curr[0], curr[1]};
			}

			for (int d = 0; d < 4; d++) {
				int nr = curr[0] + dr[d];
				int nc = curr[1] + dc[d];

				if (visited[nr][nc] || lake[nr][nc] == '\u0000') continue;

				visited[nr][nc] = true;
				if (lake[nr][nc] == 'X') will.add(new int[] {nr, nc});
				else {
					queue.add(new int[] {nr, nc});
					union(curr[0], curr[1], nr, nc);
				}
			}
		}
	}
}