[백준, JAVA]5827번, What's Up With Gravity

문제 링크

5827번: What's Up With Gravity

---

주의사항

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

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

---

문제 설명

---

접근 방법

 

주관적인 문제 해석!

 

선장 보비디안은 그녀의 동료 버팔로씨를 구하기 위해 모험을 하고 있습니다. 이 이야기는 2차원 공간(N×M)에서 이루어지고 있습니다. 공간의 셀들은 일부 비어있지만 나머지 셀들은 차단되어 이동할 수 없습니다.

 

불행하게도 보비디안은 점프를 할 수 없습니다. 그녀는 여행하는 동안 해당 세계에 물리적 법칙에 따라 여행해야 합니다.

 

1)보비디안 아래가 셀이 존재하지 않는 경우 그녀는 우주로 날아가고 미션은 실패한다.2)만약 그녀 밑에 빈 셀이 존재하는 경우 해당 셀로 떨어진다.3) a. 그녀 밑에 차단된 셀이 존재하는 경우 왼쪽과 오른쪽으로 이동이 가능하다.b. 그녀는 중력을 바꿀 수 있습니다.

 

그녀가 중력의 방향을 바꿀 때, 1~N-1사이에 존재할 때에만 변경이 가능하다.초기 중력은 아래방향으로 설정된다.

 

버팔로는 해당 세계 어딘가에서 길을 잃어버렸다. 최소의 중력의 방향을 교체하면서  버팔로씨를 찾아라.만약 버팔로씨에게 도달하지 못한다면 -1을 결과로 출력해라

 

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

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

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

 

이 문제에 핵심

1. 공간에 대한 정보를 받습니다.

2. '.'은 빈 셀, '#'은 차단된 셀, 'C'은 보비디안 위치, 'D' 버팔로의 위치입니다.

3. 중력을 바꿀수 있으며 바로 아래에 차단된 셀이 있는 경우 왼쪽, 오른쪽으로 이동이 가능하다.

4. 중력을 최소로 변경하면서 보비디안이 버팔로로 가는 중력 변경횟수를 결과로 출력한다.

5. 보비디안이 버팔로에게 가지 못할 경우 -1을 결과로 출력한다.

 

알고리즘 진행 순서.

 

1. 초기 공간에서 중력의 방향으로 보비디안의 위치를 조정합니다.

 

2. 다익스트라 BFS탐색으로 왼쪽, 오른쪽으로 이동하거나 중력을 바꾸는 것을 탐색하여 최소 변경 횟수를 구합니다.

 

예제입력 1.

 

초기 중력 : ↓

#	#	#	#	#
#	.	.	.	#
#	.	.	.	D
#	C	.	.	.
#	#	.	#	#

1. 초기 공간에서 중력의 방향으로 보비디안의 위치를 조정합니다.

#	#	#	#	#
#	.	.	.	#
#	.	.	.	D
#	C	.	.	.
#	#	.	#	#

중력 방향 ↓로 내려가도 바로 막혀있기 때문에 초기 상태와 동일합니다.

 

2. 다익스트라 BFS탐색으로 왼쪽, 오른쪽으로 이동하거나 중력을 바꾸는 것을 탐색하여 최소 변경 횟수를 구합니다.

#	#	#	#	#
#	.(중력 변경)	.	.	#
#	.	.	.	D
#	.(→)	.	.	.
#	#	.	#	#

탐색중...

#	#	#	#	#
#	.(→)	.	.	#
#	.	.	.	D
#	.	.	.	.
#	#	.	#	#

탐색중...

#	#	#	#	#
#	.	.(→)	.	#
#	.	.	.	D
#	.	.	.	.
#	#	.	#	#

탐색중...

#	#	#	#	#
#	.	.	.	#
#	.	.	.	D
#	.	.	.(중력 변경)	.
#	#	.	#	#

탐색중...

#	#	#	#	#
#	.	.	.	#
#	.	.	.	D
#	.	.	.(→)	.
#	#	.	#	#

탐색중...

#	#	#	#	#
#	.	.	.	#
#	.	.	.	D(중력 변경, 도착)
#	.	.	.	.
#	#	.	#	#

 

중력을 바꾼 최소값 4을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• String.charAt()을 이용해서 공간에 대한 정보를 나누었습니다.
• 보비디안의 초기 위치를 중력 방향에 맞게 조정하도록 moveGravity를 실행하였습니다.
• 첫 위치 조정시 버팔로를 만나면 0, 우주로 빠지면 -1을 BufferedWriter 저장하였습니다.
• 조정된 위치에서 BFS탐색으로 버팔로를 만나는 최소 중력 변경횟수를 구해서 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• moveGravity는 중력방향에 맞게 위치를 조정하는 함수입니다.
• bfs는 다익스트라 BFS탐색으로 보비디안이 버팔로에 도착할 때 최소 중력 변경횟수를 구하는 함수입니다.

 

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

public class Main {
    //PriorityQueue에 사용될 보비디안 위치 관련 클래스
    static class position implements Comparable<position>{
        int x, y, count, gravity;
        public position(int x, int y, int count, int gravity) {
            this.x = x;
            this.y = y;
            this.count = count;	//중력 변경 횟수
            this.gravity = gravity;	//중력 방향
        }

        //중력 변경 횟수에 따른 오름차순 정렬
        @Override
        public int compareTo( position o) {
            return this.count-o.count;
        }
    }
    static int N,M, startX, startY;
    static int[] dx = {-1, 1};	//왼쪽, 오른쪽 x값 변경
    static char[][] space;	//공간에 대한 정보 저장 배열
    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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        space = new char[N][M];
        //공간에 대한 정보 저장
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<M;j++){
                space[i][j] = str.charAt(j);
                //보비디안 첫 위치 저장
                if(space[i][j] == 'C'){
                    startX = j;
                    startY = i;
                }
            }
        }
        //초기 중력 ↓로 인한 보비디안 위치 조정(1.)
        startY = moveOfGravity(startX,startY,0);
        if(startY==-1)	//위치 조정할 때 바로 버팔로씨 만난 경우
            bw.write("0");
        else if(startY==Integer.MIN_VALUE)	//위치 조정할 때 우주로 떨어질 때
            bw.write("-1");
        else 		//위치 조정 후 최소값 찾는 bfs 함수 결과 BufferedWriter 저장
            bw.write(bfs() + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라 BFS탐색으로 최소 중력 변경으로 버팔로(D)까지 도달하는 값을 탐색하는 함수
    static int bfs(){
        PriorityQueue<position> pq = new PriorityQueue<>();
        boolean[][][] visited = new boolean[N][M][2];
        visited[startY][startX][0] = true;
        pq.add(new position(startX,startY,0, 0));
        while(!pq.isEmpty()){
            position cur = pq.poll();
            int x = cur.x;
            int y = cur.y;
            int count = cur.count;
            int gravity = cur.gravity;
            //좌우 이동
            for(int i=0;i<2;i++){
                int tempX = x + dx[i];
                if(tempX>=0 && tempX<M){
                    if(space[y][tempX]!='#'){	//빈 셀인 경우
                        int tempY = moveOfGravity(tempX,y,gravity);
                        if(tempY==-1)		//버팔로씨 만난 경우
                            return count;
                        //왼쪽, 오른쪽 이동 후 중력으로 위치 조정된 자리 확인
                        if(tempY!=Integer.MIN_VALUE && !visited[tempY][tempX][gravity]){
                            visited[tempY][tempX][gravity] = true;
                            pq.add(new position(tempX, tempY, count, gravity));
                        }
                    }
                }
            }
            int tempGravity = (gravity+1) % 2;	// 중력 변경
            int tempY = moveOfGravity(x,y,tempGravity);	//중력 변경으로 위치 조정
            if(tempY==-1)	//중력 변경으로 버팔로씨 만난 경우
                return count+1;
            //중력 변경으로 위치 조정된 자리 확인
            if(tempY != Integer.MIN_VALUE && !visited[tempY][x][tempGravity]){
                visited[tempY][x][tempGravity] = true;
                pq.add(new position(x,tempY,count+1, tempGravity));
            }

        }
        return -1;		//버팔로씨에게 도달하지 못할 경우
    }
    //중력방향에 따른 보비디안 위치 조정 함수
    static int moveOfGravity(int x, int y, int gravity){
        if(gravity == 0){		//중력 방향 ↓
            for(int i=y;i<N;i++){
                if(space[i][x]=='#')	//차단된 셀을 만날 때
                    return i-1;
                else if(space[i][x] == 'D')	//버팔로 만날 때
                    return -1;
            }
        }else{		//중력 방향 ↑
            for(int i=y;i>=0;i--){
                if(space[i][x] == '#')	//차단된 셀을 만날 때
                    return i+1;
                else if(space[i][x] == 'D')	//버팔로 만날 때
                    return -1;
            }
        }
        return Integer.MIN_VALUE;		//우주로 날아갈 때
    }
}