[백준 Platinum 5] 3197 백조의 호수 - Java

문제링크 : https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

접근 과정 : 

• 접촉되어 있는 물(.)의 칸을 묶어서 영역으로 표현
• 백조 두마리의 영역이 같으면, Return!!
• 같이 않으면, 물과 접촉되어 있는 얼음을 녹임

• 초기 아이디어
  1. 방금 녹은 물을 나타내는 큐와 다음에 녹을 얼음을 나타내는 큐를 사용.
  2. 방금 녹은 물의 영역을 체크 -> 백조 두 마리의 영역을 판단 -> 다르면 얼음을 녹임
  3. (인접한 얼음을 Ice 큐로!!)  -> ( 백조의 영역을 비교)  -> (녹은 얼음을 water 큐로!!)
• 리팩토링
  1. 큐를 하나만 사용!!
  2. 초기 입력시, 물이라면 영역을 표현 (초기 영역은 좌표값으로 계산 (i*C+j+1))
  3. 얼음을 녹일 때, 바로 영역을 표현. => 큐에 대한 입출력 비용이 줄어듬!! 

 

소스 코드 및 결과 :

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

문제는 빠르게 풀었으나, 리팩토링이 오래걸렸다....