[백준] 23817번 - 포항항 (Java)

문제

https://www.acmicpc.net/problem/23817

23817번: 포항항

입력

출력

---

알고리즘

너비 우선 탐색 (BFS), 브루트포스, 백트래킹

 

우선 내가 틀렸던 풀이를 하나 소개해보고자 한다.

---

이 부분은 틀린 풀이입니다. 정답 풀이가 궁금하시면 밑에 봐주세요.

처음에 시도했던 방법은 아래와 같다.

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

public class Main {
    static int[][] board;
    static boolean[][][] visited;
    static int n, m, idx;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        idx = 1;
        int start_x = -1;
        int start_y = -1;

        for (int i = 0; i < n; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < m; j++) {
                char cur = tmp.charAt(j);
                if (cur == 'S') {
                    start_x = i;
                    start_y = j;
                    board[i][j] = 0;
                } else if (cur == 'X') board[i][j] = -1;
                else if (cur == '.') board[i][j] = 0;
                else if (cur == 'K') {
                    board[i][j] = idx;
                    idx++;
                }
            }
        }
        
        visited = new boolean[n][m][1 << (idx - 1) + 1];

        System.out.println(bfs(start_x, start_y));
    }

    public static int bfs(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        queue.add(new int[]{a, b, 0, 0});
        visited[a][b][0] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            int time = cur[2];
            int state = cur[3];

            if (bitcount(state) == 5) return time;

            for (int i = 0; i < 4; i++) {
                int nx = x + dirx[i];
                int ny = y + diry[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || board[nx][ny] == -1) continue;
                if (board[nx][ny] > 0) {
                    int ns = (state | (1 << (board[nx][ny] - 1)));
                    if (!visited[nx][ny][ns]) {
                        visited[nx][ny][ns] = true;
                        queue.add(new int[]{nx, ny, time + 1, ns});
                    }
                } else if (!visited[nx][ny][state]) {
                    visited[nx][ny][state] = true;
                    queue.add(new int[]{nx, ny, time + 1, state});
                }
            }
        }

        return -1;
    }

    public static int bitcount(int state) {
        int cnt = 0;
        while (state > 0) {
            cnt += (state & 1);
            state >>= 1;
        }
        return cnt;
    }
}

 

https://www.acmicpc.net/problem/17244

17244번: 아맞다우산

위 문제와 비슷하게 푸는 방법을 시도했다. 식당의 개수가 20개니깐, 각 식당을 1번부터 20번까지 번호를 부여한다. 그리고 특정 식당에 방문했는지 비트마스킹으로 체크한다. 예를들어, 전체 식당이 6개라고 가정해보자. 그리고 2번 식당을 방문했으면 비트마스킹을 10, 여기에 4번 식당을 추가로 방문했으면 1010, 또 1번을 추가로 방문했으면 1011... 이런식으로 비트마스킹을 해두고, 방문처리도 이를 기준으로 하도록 구성했다. BFS는 항상 최단 경로를 보장하므로, 이 방문한 식당의 현재 상태를 나타내는 비트마스킹의 1의 개수가 5개가 되는 시점에 BFS를 종료하고 그때 시간을 반환하도록 구성했다.

 

이 방법으로하면, 예제랑 풀이는 답이 아주 잘 나온다. 하지만, 함정이 있으니.. 위에 아맞다우산 문제는 N과 M이 50으로 매우 작고, 물건도 5개밖에 없다. 하지만 반면에 포항항문제는 N과 M이 1000으로 매우크고, 식당도 20개나 있어서 메모리 초과가 나버린다. 

 

따라서, 다른 방법으로 시도를 해야한다. 참고로, 위에 아맞다우산도 역시 포항항 문제와 동일한 아이디어로도 풀 수 있다. 

---

 

진짜 풀이를 알아보자.

 

식당의 수가 많아봐야 20개라서 그냥 각각 S와 K 사이의 모든 최단 거리를 구하고 이를 백트래킹을 돌려 최솟값을 찾으면 된다. 식당 수가 최대 20개 이므로 20P5 = 180만 머시기 이므로 브루트포스적으로 풀어도 충분히 가능하다.

 

그러면, 각각 S와 K 사이의 모든 최단 거리를 어떻게 구할까? 역시 "최단 거리"를 구하고 기록해야 되므로 BFS를 사용할 것이다. 우선, 입력을 받을때 출발지 S는 0으로 기록하고, 각각의 가게에는 왼쪽 위에서 부터 1번,2번,3번.... 20번의 번호를 부여해줄 것이다. 그리고 가게와 출발지를 제외한 모든 빈칸 및 장애물들은 -1과 -2로 기록을 해둔다. 이제 거리를 기록할 배열을 만든다. dist[1][3] 이런식으로 쓰면, 1번가게부터 3번가게 까지의 최단 거리를 뜻한다. dist[6][0]이면 6번가게부터 출발지까지의 최단 거리를 뜻한다. 그리고 모든 점에 대해서 양수인 경우에만(즉, 출발지 또는 가게인 경우에만) BFS를 실행하면서 dist 배열을 기록한다. 이런식으로 모든 출발지 및 가게들에 대해서 BFS를 진행했다면 각각 가게에서 다른 가게까지의 최단 거리가 dist 배열에 기록될 것이다. 이때, 예를 들어 dist[3][6] = 0이라고 여전히 0으로 기록되어 있다면, 중간에 장애물이 있어서 도달하지 못했다는 의미이다. 또한, dist[3][3]과 같이 자기 자신을 의미하는 것은 0이 기록되있을 것이다.

 

그럼, 이제 출발지에서부터 시작해서 가게 5개에 도달할때까지 백트래킹을 돌리면 된다. 5개 방문에 성공하면 최소 시간을 갱신해주고 가지치기를 해준다. 예를들어, 처음에는(depth가 0일때) dist[0][1]이면 출발지에서 1번가게까지 가고, 두번째에서는(depth가 1일때) dist[1][2]을 써서 1번가게에서 2번가게까지 가고... 이런식으로 5개 가게에 모두 방문할때까지 (depth가 5일때) 백트래킹을 돌려서 모든 경우의 수를 따져가면서 비교하는 것이다.

 

위 과정을 코드로 구현해주면 답이 나온다.

---

코드

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

public class Main {
    static int[][] board;
    static int[][] dist;
    static boolean[] dfsvisited;
    static int n,m,min,idx;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        idx = 1;

        for(int i = 0; i<n; i++){
            String tmp = br.readLine();
            for(int j = 0; j<m; j++){
                char cur = tmp.charAt(j);
                if(cur == 'S') board[i][j] = 0;
                else if(cur == 'X') board[i][j] = -2;
                else if(cur == '.') board[i][j] = -1;
                //가계들은 제일 왼쪽 위에서부터 1,2,3,...번호를 부여해줄 것임
                else if(cur == 'K'){
                    board[i][j] = idx;
                    idx++;
                }
            }
        }

        //dist[1][2] : 1번 가게 ~ 2번가게까지 최단 거리
        //dist[5][0] : 5번 가게 ~ 출발지까지 최단 거리
        dist = new int[idx][idx];

        //dist 배열을 BFS를 이용해서 채워넣기
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(board[i][j]>=0) bfs(i,j);
            }
        }

        //최종 최단 거리
        min = Integer.MAX_VALUE;
        dfsvisited = new boolean[idx];
        dfs(0, 0, 0);

        //min이 전혀 갱신이 안됐다면 5개의 가게를 방문이 불가능하단 소리입니다
        System.out.println(min!=Integer.MAX_VALUE?min:-1);
    }

    //거리 기록
    public static void bfs(int a, int b){
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        int[] dirx = {1,-1,0,0};
        int[] diry = {0,0,1,-1};
        queue.add(new int[]{a,b,0});
        visited[a][b] = true;

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            int cnt = cur[2];

            for(int i = 0; i<4; i++){
                int nx = x + dirx[i];
                int ny = y + diry[i];
                //범위 벗어나는경우 + -2의 경우는 장애물이라 지나가기 불가능
                if(nx<0 || ny<0 || nx>=n || ny>=m || visited[nx][ny] || board[nx][ny] == -2) continue;
                visited[nx][ny] = true;
                //가게나 출발지일 경우 그때 최단 거리를 갱신해줍니다.
                if(board[nx][ny] >= 0) dist[board[a][b]][board[nx][ny]] = cnt+1;
                queue.add(new int[]{nx,ny,cnt+1});
            }
        }
    }

    //백트래킹
    public static void dfs(int start, int depth, int total){
        //5개의 가계를 방문 성공
        if(depth == 5){
            min = Math.min(min, total);
            return;
        }

        for(int i = 0; i<idx; i++){
            //dist값이 0이다? 그 말은 자기 자신을 의미하거나 도달이 불가능한 경로임을 의미함. 따라서 이 경우는 제외
            if(!dfsvisited[i] && dist[start][i] != 0){
                dfsvisited[start] = true;
                dfs(i, depth+1, total + dist[start][i]);
                dfsvisited[start] = false;
            }
        }
    }
}