[백준 24515] 히히 못가 - Java 문제 풀이

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

24515번: 히히 못가

 

문제

N x N 격자 모양의 땅에서 로미오는 가장 왼쪽 위 칸, 줄리엣은 가장 오른쪽 아래 칸에 살고 있다. 로미오는 매일 줄리엣을 만나러 가는데, 상하좌우로 인접한 칸으로 이동할 수 있고 땅 밖으로는 나갈 수 없다.

주변을 어슬렁거리던 솔로 부대 상원이는 로미오와 줄리엣의 만남이 마음에 들지 않는다. 수많은 솔로들의 후원으로 돈이 많은 상원이는 로미오와 줄리엣이 만날 수 없도록 주변 땅을 사버리기로 했다.

 

땅은 몇 개의 영역으로 구분되어있고 이 영역 단위로만 땅을 살 수 있다. 각 영역의 구분을 위해 격자 칸마다 알파벳 대문자를 적어 놓았는데, 상하좌우로 인접한 두 칸의 알파벳이 같다는 것은 같은 영역에 속한 땅이라는 뜻이다. 어떤 두 칸의 알파벳이 같더라도 연결되어 있지 않다면, 다른 영역에 속할 수 있다.

로미오가 줄리엣을 만나는 것을 막기 위해 상원이가 최소 몇 칸의 땅을 사야 하는지 구해보자.

입력

첫 번째 줄에 N 이 주어진다. (2≤ N ≤1000)

두 번째 줄부터 N개의 줄에 땅의 정보를 나타내는 알파벳 대문자 N개가 주어진다. 단, 로미오와 줄리엣의 위치는 . 으로 주어진다.

출력

상원이가 최소 몇 칸의 땅을 사야 하는지 출력한다.

 

풀이

접근법

1. 같은 알파벳이여도, 이어져있지 않으면 다른 영역으로 판단되므로, 각 공간을 알파벳이 아닌 영역의 번호로 다시 재설정하자
2. 각 영역별로 몇칸인지 저장해두고, 필요할 때 사용하자
3. bfs를 돌면서 어떠한 영역과 맞닿아 있는 부분에 대해 저장을 해두고, 칸을 이용해서 돌기보다는 저장해둔 리스트를 이용해서 구간을 구하자
4. 각 대각선 끝이 만나지 않게 하기 위해서는 / 모양(왼쪽 아래 - 오른쪽 위를 잇는 모양)으로 길을 연결해주면 된다. 따라서 왼쪽 아래(열이 0이거나 행이 N-1인 지점)에서 오른쪽 위(열이 N-1이거나 행이 0인 지점)로 그래프를 구해보자
5. 마지막으로 잇는 것은 우선순위큐를 이용해서 구하자 → 구간이 최소가 되어야 하기 때문에 !!

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        char[][] inputs = new char[N][N];
        for(int i=0;i<N;i++) {
            String str = br.readLine();
            for(int j=0;j<N;j++) inputs[i][j] = str.charAt(j);
        }
        int[][] arr = new int[N][N];
        for(int i=0;i<N;i++) Arrays.fill(arr[i], -1);
        int count = 0; // 영역 번호
        
        int[] countList = new int[1000001]; // 해당 영역이 몇 칸으로 이루어져 있는지
        Queue<int[]> queue = new LinkedList<>();
        int[] dx = new int[]{-1, 1, 0, 0, -1, -1, 1, 1};
        int[] dy = new int[]{0, 0, -1, 1, -1, 1, -1, 1};
        // 1. 같은 알파벳이어도 이어져있지 않으면 다른 영역으로 판단되므로, 각 공간을 알파벳이 아닌 영역의 번호로 다시 재설정하자
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if ((i == 0 && j == 0) || (i == N-1 && j == N-1)) continue;
                else if (arr[i][j] != -1) continue;
                count++;
                queue.clear();
                int num = 1;
                arr[i][j] = count;
                queue.add(new int[]{i, j});
                while(!queue.isEmpty()) {
                    int[] now = queue.poll();
                    for(int k=0;k<4;k++) {
                        int nx = now[0] + dx[k];
                        int ny = now[1] + dy[k];
                        if (nx < 0 || nx >= N || ny < 0 || ny >= N || inputs[i][j] != inputs[nx][ny] || arr[nx][ny] != -1) continue;
                        arr[nx][ny] = count;
                        num++;
                        queue.add(new int[]{nx, ny});
                    }
                }
                // 2. 각 영역별로 몇칸인지 저장해두고, 필요할 때 사용하자
                countList[count] = num;
            }
        }
        
        Set<Integer>[] list = new Set[count+1];
        for(int i=0;i<=count;i++) list[i] = new TreeSet<>();

        // 3. bfs를 돌면서 어떠한 영역과 맞닿아 있는 부분에 대해 저장을 해두고, 칸을 이용해서 돌기보다는 저장해둔 리스트를 이용해서 구간을 구하자
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if ((i == 0 && j == 0) || (i == N-1 && j == N-1)) continue;
                for(int k=0;k<8;k++) { // 대각선으로 이어져있어도 막힌 것이기 때문에 8방을 확인한다.
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx < 0 || nx >= N || ny < 0 || ny >= N || arr[i][j] == arr[nx][ny] || arr[nx][ny] == -1) continue;
                    list[arr[i][j]].add(arr[nx][ny]);
                }
            }
        }

        Set<Integer> answerList = new TreeSet<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        boolean[] visited = new boolean[count+1];
        int answer = 10000000;

	// 4. 각 대각선 끝이 만나지 않게 하기 위해서는 / 모양(왼쪽 아래 - 오른쪽 위를 잇는 모양)으로 길을 연결해주면 된다. 
        // 따라서 왼쪽 아래(열이 0이거나 행이 N-1인 지점)에서 오른쪽 위(열이 N-1이거나 행이 0인 지점)로 그래프를 구해보자
        
        // 시작점
        for(int i=1;i<N;i++) {
            for(int j=0;j<N-1;j++) {
                if (i != N-1 && j != 0) continue;
                if (visited[arr[i][j]]) continue;
                pq.add(new int[]{arr[i][j], countList[arr[i][j]]});
                visited[arr[i][j]] = true;
            }
        }

	// 끝나는 점
        for(int i=0;i<N-1;i++) {
            for(int j=1;j<N;j++) {
                if (i != 0 && j != N-1) continue;
                if (visited[arr[i][j]]) {
                    answer = Math.min(answer,  countList[arr[i][j]]);
                }
                answerList.add(arr[i][j]);
            }
        }

	// 5. 마지막으로 잇는 것은 우선순위큐를 이용해서 구하자 → 구간이 최소가 되어야 하기 때문에 !!
        while(!pq.isEmpty()) {
            int[] now = pq.poll();
            if (now[1] > answer) break;
            for(int nxt : list[now[0]]) {
                if (visited[nxt]) continue;
                visited[nxt] = true;
                int cost = now[1] + countList[nxt];
                if (answerList.contains(nxt)) {
                    answer = Math.min(answer, cost);
                    continue;
                }
                pq.add(new int[]{nxt, cost});
            }
        }
        System.out.println(answer);
    }
}