[백준 / BOJ] 5852 Island Travels (Java)

문제

출처 : https://www.acmicpc.net/problem/5852

5852번: Island Travels

영어 문제이므로 문제 본문 설명을 자세히??(내가해석한대로) 하도록 하겠다

 

농부 존은 소들과 바다로 여행을 갔다.

소들은 N (1 <= N <= 15)개의 섬에 있다. 각 섬들은 R*C(1 <= R,C <= 50)그리드에 위치해있으며 상하좌우로 연결되어있을수있다.

(섬들은 'X'로 표시한다.)

 

베시는 이 섬들을 모두 돌아볼려고한다. 베시는 헬기를 타고 왔기때문에, 섬들의 어느 위치에서든 내릴수있고, 한번 내린후에는 다시 헬기를 타지못한다.(헬기에 연료가 부족하다)

 

모든 섬들이 연결된것이 아니기때문에, 베시는 각 섬들을 이동할때, 수영을 해서 가야한다. 너무 깊은 바다는 수영하지못하므로 수심이 얕은곳만 수영해서 갈수있다. (한칸을 이동할때마다 수영횟수가 1씩 추가된다.)

수심이 얕은 지역은 'S'로 표시한다. 

수심이 깊은 지역 즉, 이동하지못하는 지역은 '.'으로 표시한다.

 

베시가 수영하는 횟수를 최소로하여 모든 섬들을 돌아보는 횟수를 구하는 프로그램을 만드시오.

---

풀이

푸는데 시간이 상당히 걸린 문제다.

 

사용알고리즘은, 기본적으로 비트마스킹(섬들의 갯수가 15개밖에 안되므로)을 이용한 다이나믹 프로그래밍이다. 

 

아쉽게도 위 알고리즘을 문제에 바로 적용하지못한다.

- dp[1 << 섬들의 갯수][R][C]와 같이 선언할경우 선언 가능범위를 초과해 선언 자체가 안된다.

따라서, 섬들의 위치를 그래프의 형태로 가공해줘야한다. 

(가공하는걸 생각하는게 이게 이 문제의 핵심이라고 생각한다.)

 

섬들의 위치를 가공하기위해 우선, 각 섬들에 번호을 지정해주자.

문제의 예제 1의경우 다음과 같이 섬의 번호가 지정된다.

 

X	X	.	S
.	S	.	.
S	X	S	S
S	.	S	X
.	.	S	X

1	1	0	0
0	0	0	0
0	2	0	0
0	0	0	3
0	0	0	3

 

섬들에 번호를 지정하는 코드는 다음과 같다.

    private void setIsland(){ // 섬들의 이름지정 초기 1회만실행
        for(int i = 1; i <= R; i++){
            for(int j = 1; j <= C; j++){
                if(marked[i][j] == 0 && island[i][j] == 'X'){
                    initialIsland(i,j,mark);
                    mark++;
                }
            }
        }
        mark--;
    }
    
    private void initialIsland(int y, int x, int marking){
        if(outOfBound(y,x) || island[y][x] != 'X' || marked[y][x] == marking) return;
        marked[y][x] = marking;
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(outOfBound(ny, nx) || island[ny][nx] != 'X' || marked[ny][nx] == marking) continue;
            initialIsland(ny, nx, marking);
        }
    }

 

이제 섬들의 번호를 기준으로

1번섬에서 2번섬으로 가는 최단경로,

1번섬에서 3번섬으로 가는 최단경로,

2번섬에서 1번섬으로 가는 최단경로,

2번섬에서 3번섬으로 가는 최단경로 ...

를 모두 구해놓고 경로를 저장한다. 

 

그냥 다익스트라로 모든 섬들에서 시작해서 모든 경로를 다 봐준다고 생각하면된다.

 

각 섬들의 최단 경로를 저장할 road배열은 다음과 같이 초기화 된다.

road[from][to] = 최단경로

예제 1의 경우 road배열은 다음과 같이 초기화 될것이다. (행, 열 각각 순서대로 1,2,3번 섬이라고 생각하자)

0	1	3
1	0	2
3	1	0

road배열을 만드는 코드는 다음과 같다. (이 문제의 핵심이다.)

코드가 이해가 안된다면, 다익스트라로 모든 섬들에서 시작해서 모든 경로를 다 봐준다고 생각하고 코드를 만들자. 

class Position implements Comparable<Position>{
    
    public int distance,y, x;
    
    public Position(int distance, int y, int x){
        set(distance, y, x);
    }
    
    public void set(int distance, int y, int x){
        this.distance = distance;
        this.y = y;
        this.x = x;
    }
    
    @Override
    public int compareTo(Position pair){
        if(distance > pair.distance) return 1;
        else if(distance < pair.distance) return -1;
        return 0;
    }
    
}

    private void setRoad(){
        boolean[] alreadyMark = new boolean[mark+5];
        for(int i = 1; i <= R; i++){
            for(int j = 1; j <= C; j++){
                if(island[i][j] == 'X' && !alreadyMark[marked[i][j]]){
                    alreadyMark[marked[i][j]] = true;
                    makeRoad(marked[i][j],i,j);
                }
            }
        }
    }

    private void makeRoad(int island, int i, int j){
        int[][] check = new int[R+5][C+5];
        boolean[][] initialCheck = new boolean[R+5][C+5];
        PriorityQueue<Position> pq = new PriorityQueue<Position>();
        pq.add(new Position(0, i, j));
        while(!pq.isEmpty()){
            int nowDistance = pq.peek().distance;
            int nowY = pq.peek().y;
            int nowX = pq.peek().x;
            pq.poll();
            if(initialCheck[nowY][nowX] && check[nowY][nowX] <= nowDistance) continue;
            if(marked[nowY][nowX] > 0){
                road[island][marked[nowY][nowX]] = Math.min(nowDistance, road[island][marked[nowY][nowX]]);
            }
            initialCheck[nowY][nowX] = true;
            check[nowY][nowX] = nowDistance;
            for(int dir  = 0; dir < 4; dir++){
                int nextY = nowY + dy[dir];
                int nextX = nowX + dx[dir];
                int nextDistance = nowDistance;
                if(outOfBound(nextY, nextX)) continue;
                if(this.island[nextY][nextX] == 'S') nextDistance++;  
                pq.add(new Position(nextDistance, nextY, nextX));
            }
        }
    }

이제 경로 생성이 끝났다.

(이제 90퍼센트는 풀었다고 생각해도된다.)

 

최소경로를 탐색해주기위해 dp 배열을 만들자.

dp[1 << 섬의갯수][섬의갯수]만큼 크기를 잡아준다. 

 

dp배열은 다음과 같이 초기화 될것이다.

dp[현재까지 탐색한 섬들의 목록][마지막으로 도착한 섬] = 최솟값

예를들어,  지금까지 1번 3번섬을 방문했고, 마지막으로 3번섬을 도착했다면 dp배열은 다음과 같이 초기화된다.

 

dp[1010][3] = 최솟값

 

이제 dp배열을 채워가며 수영을 최소로하는 경로를 찾아주면된다.

코드는 다음과 같다.

    private int[][] dp = new int[1 << 17][20]; 

    private int getSwim(int visit, int idx){
        if(dp[visit][idx] != 0) return dp[visit][idx];
        if(outMark == visit) return dp[visit][idx] = 0;
        int ret = 987654321;
        for(int next = 1; next <= mark; next++){
            if(idx == next || (visit & (1 << next)) != 0) continue;
            ret = Math.min(ret, getSwim((visit | (1 << next)), next) + road[idx][next]);
        }
        return dp[visit][idx] = ret;
    }

 

 

풀다가 찾은 반례는 다음과 같다.

 

5 5

XSXSX

SXSXS

XSXSX

SXSXS

XSXSX

출력 : 12

 

5 5

.....

.....

..X..

.....

.....

출력 : 0

 

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/5852%20Island%20Travels/Main.java

devxb/JJUNalgo