[백준] 3987 보이저 1호 - JAVA //le_effort//

보이저 1호

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	2620	575	415	20.185%

문제

보이저 1호는 1977년에 발사된 NASA의 태양계 무인 탐사선이다. 현재 보이저 1호는 태양권덮개 (헬리오시스)에 있다.

보이저 1호와 같이 오랜 기간동안 활동하는 탐사선은 경로를 항성계를 만날 때 마다 라디오 시그널 메시지를 이용해서 기록하고 있다.

항성계를 N * M개의 직사각형으로 나누어져 있는 N행 M열의 직사각형 그리드라고 생각해보자. 각 칸은 행성, 블랙홀을 포함할 수 있으며, 비어있을 수도 있다. 탐사선은 인접한 네 칸(위, 아래, 오른쪽, 왼쪽)중에서 하나를 골라서 시그널을 보낸다.

시그널은 항상 일직선으로 전파되며, 행성을 만났을 경우에는 전파되는 방향이 90도로 바뀌게 된다. 행성은 '/'와 ''로 표현되는 두 종류가 있으며, 반사되는 법칙은 아래 그림과 같다.

시그널이 블랙홀이 있는 칸을 만나거나 항성계를 벗어날 때 까지 계속 전파된다. 시그널이 인접한 칸으로 이동하는데 걸리는 시간은 1초이다.

탐사선이 어느 방향으로 시그널을 보내면, 시그널이 항성계 내부에 있는 시간이 최대가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 500)

다음 N개 줄에는 M개의 문자가 주어지며, '/'와 ''는 행성을, C는 블랙홀을, '.'는 빈 칸을 나타낸다.

마지막 줄에는 탐사선이 있는 위치 PR과 PC가 주어진다. (1 ≤ PR ≤ N, 1 ≤ PC ≤ M)

출력

첫째 줄에 시그널을 보내는 방향을 출력한다. (U: 위, R: 오른쪽, D: 아래, L: 왼쪽)

만약, 방향이 여러 가지가 존재한다면, U, R, D, L의 순서 중 앞서는 것을 출력한다.

둘째 줄에는 가장 긴 시간을 출력한다. 만약, 시그널이 항성계 내에서 무한히 전파될 수 있다면 "Voyager"를 출력한다.

예제 입력 1 복사

5 5
../.\
.....
.C...
...C.
\.../
3 3

예제 출력 1 복사

xxxxxxxxxx
U
17

힌트

초기 상태	위(U) 방향	오른쪽(R) 방향	아래(D) 방향	왼쪽(L) 방향
../.\ ..... .CS.. ...C. \.../	*.*** *.*.* *C*.* *..C* *****	../.\ ..... .C*** ...C. \.../	../.\ ..... .C*.. ..*C. \.*./	../.\ ..... .C*.. ...C. \.../
	17초	3초	3초	1초

 

전체코드

사용 알고리즘 : 구현 + bfs

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static int max = -1;
    static char map[][];
    static boolean visited[][][];
    static int dx[] = {-1,0,1,0};
    static int dy[] = {0,1,0,-1};
    static boolean flag;
    static int bfs_max;
    static String ans_dir;
    static boolean voyage_flag;
    public static void main(String[] args) throws IOException {
        
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        
        map = new char[n+1][m+1];
        visited = new boolean[n+1][m+1][4];
        
        for(int i=1; i<=n; i++) {
            String map_input = br.readLine();
            for(int j=1; j<=m; j++) {
                map[i][j] = map_input.charAt(j-1);
            }
        }
        
        String[] dest = br.readLine().split(" ");
        int end_x = Integer.parseInt(dest[0]);
        int end_y = Integer.parseInt(dest[1]);
        
        for(int i=0; i<4; i++) {
            visited = new boolean[n+1][m+1][4];
            bfs(end_x,end_y,i);
            if(voyage_flag) {
                if(i==0) {
                    System.out.println("U");
                }
                else if(i==1) {
                    System.out.println("R");
                }
                else if(i==2) {
                    System.out.println("D");
                }
                else {
                    System.out.println("L");
                }
                System.out.println("Voyager");
                return;
            }
        }
        bfs(end_x,end_y,1);
        System.out.println(ans_dir);
        System.out.println(max);
        
    }
    public static void bfs(int r, int c, int dir) {
        bfs_max=0;
        flag = false;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(r,c,dir,1));
        //visited[r][c][dir]=true;
        while(!q.isEmpty()) {
            Node a= q.poll();
            int nx = a.x;
            int ny = a.y;
            int d = a.d;
            bfs_max=Math.max(bfs_max, a.time); 
            if(nx+dx[d]>=1 && nx+dx[d]<=n && ny+dy[d]>=1 && ny+dy[d]<=m) {
                nx+=dx[d];
                ny+=dy[d];
                if(map[nx][ny]=='C') {
                    break;
                }
                if(visited[nx][ny][d]) {
                    voyage_flag= true;
                    flag=true;
                    break;
                }
                
                if(map[nx][ny]=='/') {
                    d = dir_change_first(d);
                }
                else if(map[nx][ny] == '\\') {
                    d = dir_change_second(d);
                }
                    q.add(new Node(nx,ny,d,a.time+1));
                    visited[nx][ny][d]=true;
            }
        }
        if(!flag && max<bfs_max) {
            if(dir ==0) {
                ans_dir = "U";
            }
            if(dir ==1) {
                ans_dir = "R";
            }
            if(dir ==2) {
                ans_dir = "D";
            }
            if(dir==3) {
                ans_dir = "L";
            }
            max = bfs_max;
        }
        else if(max == bfs_max) {
            ans_dir = dir_compare(dir);
        }
    }
    public static String dir_compare(int dir) {
        if(ans_dir.equals("U")) {
            return ans_dir;
        }
        if(ans_dir.equals("R")) {       //R이면 숫자로 치면 1
            if(dir>=1) {    // 1,2,3 방향은 R방향 그대로
                return ans_dir;
            }
            else {
                return "U";
            }
        }
        if(ans_dir.equals("D")) {
            if(dir >=2) {
                return ans_dir;
            }
            else if(dir==0) {
                return "U";
            }
            else if(dir ==1) {
                return "R";
            }
        }
        if(ans_dir.equals("L")) {
            if(dir ==0) {
                return "U";
            }
            else if (dir==1) {
                return "R";
            }
            else if(dir ==2) {
                return "D";
            }
            else {
                return "L";
            }
        }
        return "don'care";  // 어차피 위의 if문에서 return 다 되니 이건 상관없다.
    }
    public static int dir_change_second(int dir) {  // "\" 모양일때 방향 바꾸기
        int change_dir=dir;
        if(dir==0) {
            change_dir = 3;
        }
        else if(dir==1) {
            change_dir=2;
        }
        else if(dir==2) {
            change_dir=1;
        }
        else if(dir==3) {
            change_dir=0;
        }
        return change_dir;
    }
    public static int dir_change_first(int dir) {   // "/" 모양일때 방향바꾸기
        int change_dir=dir;
        if(dir==0) {
            change_dir = 1;
        }
        else if(dir==1) {
            change_dir=0;
        }
        else if(dir==2) {
            change_dir=3;
        }
        else if(dir==3) {
            change_dir=2;
        }
        return change_dir;
    }
}
class Node{
    int x,y,d,time;
    Node(int x, int y,int d,int time){
        this.x=x;
        this.y=y;
        this.d=d;
        this.time=time;
    }
}