[백준] 3987 보이저 1호 🚀 (Java)

문제 링크

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

문제 설명

보이저 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"를 출력한다.

구조화

char를 int로 변환해서 저장

'.' -> 0

'C' -> -1 블랙홀

'/' -> 1

'\' -> 2

또한 char 배열 {'U', 'R', 'D', 'L'} 을 통해 인덱스로 char 관리 가능

 

'/' 또는 '\'를 만난다면 방향 변환

 

boolean 삼차원 배열에 방문 처리를 저장하며, 이미 방문한곳을 재방문하면 무한히 전파하는 것을 검증

+ 이미 무한히 전파라면 뒤에는 실행 X

오답 노트

char에서 int 변환 주의

무한히 전파는 계속 반복해서 그래프 탐색하는 경우임

소스 코드

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

public class Main {
    public static int n, m, ans = Integer.MIN_VALUE;
    public static char c;
    public static char[] cs = {'U','R','D','L'};
    public static int[][] map,
    way = {{-1, 0},{0, 1},{1, 0},{0, -1}};
    public static boolean[][][] v;
    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());

        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                switch (str.charAt(j)) {
                    case '.':
                        map[i][j] = 0;
                        break;
                    case 'C':
                        map[i][j] = -1;
                        break;
                    case '/':
                        map[i][j] = 1;
                        break;
                    case '\\':
                        map[i][j] = 2;
                        break;
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken())-1;
        int y = Integer.parseInt(st.nextToken())-1;
        for (int i = 0; i < 4; i++) {
            v = new boolean[n][m][4];
            if (ans != Integer.MAX_VALUE)
                bfs(x, y, i);
        }

        System.out.println(c);
        System.out.println(ans==Integer.MAX_VALUE? "Voyager" : ans);
    }

    public static void bfs(int x, int y, int w) {
        int time = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y, w});

        while (!q.isEmpty()) {
            int s = q.size();
            time++;
            while (s-- > 0) {
                int cx = q.peek()[0];
                int cy = q.peek()[1];
                int cw = q.peek()[2];
                q.poll();

                int nx = cx + way[cw][0];
                int ny = cy + way[cw][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny] == -1) continue;
                if (v[nx][ny][cw]) {
                    ans = Integer.MAX_VALUE;
                    c = cs[w];
                    return;
                }

                v[nx][ny][cw] = true;

                if (map[nx][ny] == 1) {
                    switch (cw) {
                        case 0:
                            cw = 1;
                            break;
                        case 1:
                            cw = 0;
                            break;
                        case 2:
                            cw = 3;
                            break;
                        case 3:
                            cw = 2;
                            break;
                    }
                }
                if (map[nx][ny] == 2) {
                    cw = (3 - cw);
                }

                q.offer(new int[]{nx, ny, cw});
            }
        }

        if (time>ans) {
            ans = time;
            c = cs[w];
        }
    }

}

GitHub 링크

Algorithm/백준/Gold/3987. 보이저 1호/보이저 1호.java at main · youjiyeon/Algorithm