[백준, JAVA]5852번, Island Travels

문제 링크

5852번: Island Travels

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

 

주관적인 문제 해석!

 

농부 존의 소들은 바다에서 휴식을 취하고 있습니다! 소들은 N개의 섬에서 지내고 있습니다. 그 섬들은 R×C 구역 안에 위치하고 있습니다. 섬의 위치는 'X'로 표현되고 있으며 인접한 'X'끼리는 연결되어 있습니다. 섬끼리는 모서리를 공유하지는 않습니다.

 

베시는 지각을 해서 헬기를 타고 농부 존에게 오고있습니다. 베시의 첫번째 착륙할 섬은 그녀가 선택할 수 있습니다. 그녀는 소들이 휴식하는 모든 섬을 한 번씩은 지나야 합니다.

 

베시의 헬기는 연료가 충분하지 않아서 섬들 사이를 이동할 때에는 사용하지 않을 것입니다. 운좋게도 이 구역은 몇개의 얕은 물이 존재합니다. 얕은 물은 'S'로 표현됩니다. 그녀는 얕은 물을 수영으로 이동이 가능합니다. 동서남북 4가지 방향으로 이동이 가능하며 얕은 물을 통해서 각 섬들을 방문할 것입니다.

 

베시가 모든 섬을 방문할 때 얕은 물에서 수영을 하는 최소 횟수를 찾아야한다.

주어지는 지도를 살펴보면 항상 얕은 물의 수영을 통해서 모든 섬의 방문이 가능하다.

 

BFS

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

외판원 순회

DP와 비트마스크를 이용해서 각 구역을 방문 확인 및 최소 비용을 구하는 알고리즘입니다.

출처: https://namu.wiki/w/%EC%99%B8%ED%8C%90%EC%9B%90%20%EC%88%9C%ED%9A%8C%20%EB%AC%B8%EC%A0%9C

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

 

외판원 순회 문제 - 나무위키

 

이 문제에 핵심

1. 지도에 대한 정보들을 입력받습니다.

2. '.'은 수영 불가능한 물, 'X'은 섬, 'S'은 수영 가능한 얕은 물입니다.

3. 베시의 시작위치의 섬은 자유롭게 선택이 가능하며 모든 섬을 방문했을 때 최소 수영 횟수를 결과로 출력합니다.

4. 베시는 'S' 얕은 물에서만 수영이 가능하며 동서남북으로 수영이 가능합니다.

 

알고리즘 진행 순서.

 

1. BFS탐색으로 지도에서 연결된 섬들에게 번호를 부여하였습니다.

 

2. 다익스트라 BFS탐색으로 각 번호의 섬들에 최단 수영 횟수를 구하였습니다.

 

3. 외판원 순회 알고리즘을 이용해서 모든 섬을 방문하는 최소 수영 횟수를 구하여 결과로 출력하였습니다.

 

예제입력 1에 진행되는 것을 보면 쉽게 이해가 가능하실 것입니다.

 

 

예제입력 1.

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

 

1. BFS탐색으로 지도에서 연결된 섬들에게 번호를 부여하였습니다.

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

 

2. 다익스트라 BFS탐색으로 각 번호의 섬들에 최소 수영 횟수를 구하였습니다.

섬 번호	1	2	3
1	0	1	3
2	1	0	2
3	3	2	0

 

3. 외판원 순회 알고리즘을 이용해서 모든 섬을 방문하는 최소 수영 횟수를 구하여 결과로 출력하였습니다.

 

DP[섬 방문 관련 비트][현재 섬]

 

Ex)

모든 섬을 방문하였을 때 비트 : 111

1, 3번 섬을 방문하였을 때 비트 : 101

1번섬 방문하였을 때 비트 : 001

 

DP[][]와 재귀를 이용해서 모든 섬을 방문하였을 때에 최소 값을 구합니다.

※재귀에서 각 섬의 최단 경로를 이용해서 최소값을 구하도록 하였습니다.

 

최소값을 구한 결과 3이 결과로 출력됩니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• String.charAt()을 이용해서 구역에 대한 정보를 나누었습니다.
• 섬들의 번호를 지정하기 위해서 setIsland함수를 실행하였습니다.
• 섬들의 최단 경로를 구하기 위해서 setRoute함수를 실행하였습니다.
• 모든 섬을 방문한 비트값을 구하는 setVisitedCount함수를 실행하였습니다.
• swimmingStart함수을 실행하여 모든 섬을 방문하는 최소 수영 횟수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• setIsland는 구역의 섬에 대하여 번호를 구하는 searchIsland함수를 실행하는 함수입니다.
• searchIsland는 BFS탐색으로 주어진 섬을 기준으로 번호를 저장하는 함수입니다.
• setRoute는 각 섬에 대하여 최단 경로를 구하는 searchRoute함수를 실행하는 함수입니다.
• searchRoute는 다익스트라 BFS탐색으로 두 섬의 최단 수영 횟수를 구하는 함수입니다.
• inMapBound는 좌표가 구역의 벗어나는지 확인하는 함수입니다.
• setVisitedCount는 모든 섬을 방문하였을 때 비트값을 구하는 함수입니다.
• swimmingStart는 외판원 순회(DP + 재귀 + 비트)로 모든 섬을 방문하는 최소 수영 횟수를 구하는 함수입니다.

 

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

public class Main {
	//islandIndex : 섬의 개수, allVisitedCount : 모든 섬을 방문했을 때 비트값
    static int R,C, islandIndex = 1, allVisitedCount=0;
    static char[][] map;
    static int[][] DP = new int[1<<17][16];	//DP 초기화
    static int[][] island, islandRoute;	//섬 번호 저장 배열, 섬 최단 경로 저장 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x값 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y값 변경값
    //구역에 대한 정보 관련 클래스
    static class position implements Comparable<position>{
        int x, y, count;
        public position(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
        //수영 횟수 기준 오름차순 정렬
        @Override
        public int compareTo( position o) {
            return this.count - o.count;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        island = new int[R][C];
        //구역 관련 정보 저장
        for(int i=0;i<R;i++){
            String str = br.readLine();
            for(int j=0;j<C;j++)
                map[i][j] = str.charAt(j);
        }
        setIsland();	//섬의 번호 BFS 탐색
        setRoute();		//섬끼리 최단 경로 BFS탐색
        setVisitedCount();	//모든 섬 방문시 비트값 설정
        bw.write(swimmingStart(0, 0) + "");	//외판원 순회로 최소값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //외판원 순회로 모든 섬을 방문하는 최소 수영 횟수를 구하는 함수
    static int swimmingStart(int visited, int idx){
        if(DP[visited][idx] != 0)	//방문 했을 경우
            return DP[visited][idx];
        if(visited == allVisitedCount)	//모두 방문했을 때
            return DP[visited][idx] = 0;
        int min = Integer.MAX_VALUE;
        for(int i=1;i<=islandIndex;i++){
            if(idx == i || (visited & (1 << (i-1))) != 0)	//동일한 섬일 때
                continue;
            //작은 값으로 변경
            min = Math.min(min, swimmingStart((visited | (1 << (i-1))),i) + islandRoute[idx][i]);
        }
        return DP[visited][idx] = min;
    }
    //모든 섬 방문 비트값 구하는 함수
    static void setVisitedCount(){
        for(int i=0;i<islandIndex;i++)
            allVisitedCount = allVisitedCount | (1 << i);
    }
    //각 섬끼리의 최단 경로를 구하기 위해 BFS 함수 호출하는 함수
    static void setRoute(){
        islandRoute = new int[islandIndex+1][islandIndex+1];
        islandIndex = 1;
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(island[i][j] == islandIndex){
                    searchRoute(j,i,islandIndex);
                    islandIndex++;
                }
            }
        }
        islandIndex--;
    }
    //섬들의 번호 설정하기 위해 BFS 함수 호출하는 함수
    static void setIsland(){
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(island[i][j]==0 && map[i][j]=='X'){
                    searchIsland(j,i);
                    islandIndex++;
                }
            }
        }
        islandIndex--;
    }
    //다익스트라 BFS탐색으로 각 섬들의 최단 경로를 구하는 함수
    static void searchRoute(int x, int y, int index){
        PriorityQueue<position> pq = new PriorityQueue<>();
        boolean[][] visited = new boolean[R][C];
        visited[y][x] = true;
        pq.add(new position(x,y,0));
        while(!pq.isEmpty()){
            position cur = pq.poll();
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(inMapBound(tempX,tempY) && !visited[tempY][tempX]){
                    visited[tempY][tempX] = true;
                    if(map[tempY][tempX] == 'X'){	//인접한 섬일 때
                        if(island[tempY][tempX]!=index && islandRoute[index][island[tempY][tempX]] == 0)
                            islandRoute[index][island[tempY][tempX]] = cur.count;
                        pq.add(new position(tempX,tempY, cur.count));
                    }else if(map[tempY][tempX]=='S')	//인접한 얕은 물일 때
                        pq.add(new position(tempX,tempY, cur.count+1));
                }
            }
        }
    }
    //BFS탐색으로 각 섬들의 번호를 설정하는 함수
    static void searchIsland(int x, int y){
        Queue<position> queue = new LinkedList<>();
        boolean[][] visited = new boolean[R][C];
        visited[y][x] = true;
        island[y][x] = islandIndex;
        queue.add(new position(x,y,islandIndex));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(inMapBound(tempX,tempY) && !visited[tempY][tempX]){
                    if(island[tempY][tempX] == 0 && map[tempY][tempX]=='X'){
                        visited[tempY][tempX] = true;
                        island[tempY][tempX] = cur.count;
                        queue.add(new position(tempX,tempY, cur.count));
                    }
                }
            }
        }
    }
    //좌표가 구역안에 존재하는지 확인하는 함수
    static boolean inMapBound(int x, int y){
        if(x>=0 && y>=0 && x<C && y<R)	// 구역 안에 존재시
            return true;
        return false;
    }
}