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

문제

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

 

풀이

시작 지점에서 각 방향(북 동 남 서)에 대한 탐색과

'/'와 '\'를 만났을 때 문제의 조건에 맞게 방향이 변경되는 점을 고려해서

가장 오래 머물렀을 때의 시간을 구하는 문제입니다.

 

사이클로 인해 멈추지 않고 연산하는 경우는 

N*M*2보다 크거나 같을 경우 탈출하는 조건을 주어 해결해줍니다.

이유는 해당 문제는 재방문이 가능하며 얼마나 오래 머물렀는지 시간을 재는 문제이기 때문입니다.

또한, 배열 내의 총 칸 수(N*M)만큼 방문하고 범위 밖으로 벗어났을 경우 등의 케이스를 넉넉하게 포함하기 위해 곱하기 2를 해주었습니다.

이 값보다 클 경우에는 사이클이 발생한 경우이므로 "Voyager"를 출력합니다.

 

개선

조건에 따른 코드 길이 줄이기

'/'와 '\'를 만났을 때 방향 바꿔주는 부분에서 코드를 간결하게 만들어 주었음

// 변경 전

if(d == 0) return 1; // 북으로 향하면 동으로 변경
else if(d == 1) return 0;
else if(d == 2) return 3;
else return 2;

// 변경 후

if(d >= 0 && d <= 1) return 1 - d;
else return 5 - d;

 

인덱스 별 방향을 지칭하는 메서드를 따로 만들었던 부분을 배열로 간결하게 만들어주었음

// 변경 전

private static char parseResD(int c) {
    if(c == 0) return 'U';
    else if(c == 1) return 'R';
    else if(c == 2) return 'D';
    else return 'L';
}

// 변경 후

static char[] dirArr = {'U', 'R', 'D', 'L'};

 

 

로직 변경

큐에 넣고 bfs 탐색을 해주었지만, 굳이 그렇게 할 필요 없이 while문으로 해결이 가능했음

이 부분을 개선하면서 공간 복잡도가 약 2배 이상 시간 복잡도가 약 1.3배 향상되었음

 

// 변경 전

private static int bfs(int sr, int sc, int sd) {
    Queue<Node> q = new ArrayDeque<>();

    int max = 1;
    q.offer(new Node(sr, sc, sd, 1));

    while(!q.isEmpty()){
        Node cur = q.poll();

        // 정답 갱신
        max = Math.max(max, cur.t);

        // 무한루프 케이스 처리
        if(cur.t >= R*C*2) return INF;

        // 현재 인덱스가 '.'일 때
        int nr = cur.r + dr[cur.d];
        int nc = cur.c + dc[cur.d];

        if(!isValid(nr, nc) || arr[nr][nc] == 'C') break;

        q.offer(new Node(nr, nc, arr[nr][nc] == '.' ? cur.d : parsingD(cur.d, arr[nr][nc]), cur.t+1));
    }

    return max;
}
    
    
// 변경 후

private static int play(int r, int c, int d) {
    int time = 1;

    while(true){

        int nr = r + dr[d];
        int nc = c + dc[d];

        // 유효성 및 블랙홀 여부 체크
        if(!isValid(nr, nc) || arr[nr][nc] == 'C') break;

        // 무한루프 케이스 처리
        if(time >= R*C*2) return INF;

        // r,c 갱신
        r = nr;
        c = nc;

        // '/' or '\'일 때
        if(arr[nr][nc] != '.')
            d = parsingD(d, arr[nr][nc]);

        time ++;
    }

    return time;
}

코드

 

변경 전

50,604 KB / 380 ms / 3141 B

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

public class Main {
    static final int INF = 1 << 30;
    static int R, C;
    static char[][] arr;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new char[R][C];

        for(int i = 0 ; i < R ; i ++){
            String s = br.readLine();
            for(int j = 0 ; j < C ; j ++)
                arr[i][j] = s.charAt(j);
        }

        st = new StringTokenizer(br.readLine());
        int sr = Integer.parseInt(st.nextToken())-1;
        int sc = Integer.parseInt(st.nextToken())-1;

        int max = 1;
        int dir = 4;

        for(int i = 0 ; i < 4 ; i ++){
            int res = bfs(sr, sc, i);

            if(res == INF){
                max = INF;
                dir = i;
                break;
            }

            if(res > max){
                max = res;
                dir = i;
            }
            else if(res == max){
                if(dir > i) dir = i;
            }
        }

        sb.append(parseResD(dir)).append("\n");
        sb.append(max == INF ? "Voyager" : max).append("\n");

        System.out.print(sb);
    }

    private static int bfs(int sr, int sc, int sd) {
        Queue<Node> q = new ArrayDeque<>();

        int max = 1;
        q.offer(new Node(sr, sc, sd, 1));

        while(!q.isEmpty()){
            Node cur = q.poll();

            // 정답 갱신
            max = Math.max(max, cur.t);

            // 무한루프 케이스 처리
            if(cur.t >= R*C*2) return INF;

            // 현재 인덱스가 '.'일 때
            int nr = cur.r + dr[cur.d];
            int nc = cur.c + dc[cur.d];

            if(!isValid(nr, nc) || arr[nr][nc] == 'C') break;

            q.offer(new Node(nr, nc, arr[nr][nc] == '.' ? cur.d : parsingD(cur.d, arr[nr][nc]), cur.t+1));
        }

        return max;
    }

    private static int parsingD(int d, char c) {
        if(c == '\\'){
            if(d == 0) return 3;
            else if(d == 1) return 2;
            else if(d == 2) return 1;
            else return 0;
        }
        else{
            if(d == 0) return 1; // 북으로 향하면 동으로 변경
            else if(d == 1) return 0;
            else if(d == 2) return 3;
            else return 2;
        }
    }

    private static char parseResD(int c) {
        if(c == 0) return 'U';
        else if(c == 1) return 'R';
        else if(c == 2) return 'D';
        else return 'L';
    }

    private static boolean isValid(int nr, int nc) {
        return (nr>=0 && nr<R && nc>=0 && nc<C);
    }

    static class Node{
        int r, c, d, t;
        public Node(int r, int c, int d, int t){
            this.r = r;
            this.c = c;
            this.d = d;
            this.t = t;
        }
    }
}

 

변경 후

19,760 KB / 252 ms / 2447 B

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

public class Main {
    static final int INF = 1 << 30;
    static int R, C;
    static char[][] arr;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static char[] dirArr = {'U', 'R', 'D', 'L'};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new char[R][C];

        for(int i = 0 ; i < R ; i ++){
            String s = br.readLine();
            for(int j = 0 ; j < C ; j ++)
                arr[i][j] = s.charAt(j);
        }

        st = new StringTokenizer(br.readLine());
        int sr = Integer.parseInt(st.nextToken())-1;
        int sc = Integer.parseInt(st.nextToken())-1;

        int max = 1;
        int dir = -1;

        for(int i = 0 ; i < 4 ; i ++){
            int res = play(sr, sc, i);

            // 무한루프 케이스
            if(res == INF){
                max = INF;
                dir = i;
                break;
            }

            // 갱신
            if(res > max){
                max = res;
                dir = i;
            }
        }

        sb.append(dirArr[dir]).append("\n");
        sb.append(max == INF ? "Voyager" : max).append("\n");

        System.out.print(sb);
    }

    private static int play(int r, int c, int d) {
        int time = 1;

        while(true){

            int nr = r + dr[d];
            int nc = c + dc[d];

            // 유효성 및 블랙홀 여부 체크
            if(!isValid(nr, nc) || arr[nr][nc] == 'C') break;

            // 무한루프 케이스 처리
            if(time >= R*C*2) return INF;

            // r,c 갱신
            r = nr;
            c = nc;

            // '/' or '\'일 때
            if(arr[nr][nc] != '.')
                d = parsingD(d, arr[nr][nc]);

            time ++;
        }

        return time;
    }

    private static int parsingD(int d, char c) {
        if(c == '\\')
            return 3 - d;
        else{
            if(d >= 0 && d <= 1) return 1 - d;
            else return 5 - d;
        }
    }

    private static boolean isValid(int nr, int nc) {
        return (nr>=0 && nr<R && nc>=0 && nc<C);
    }
}