[백준_3987]_보이저1호

LINK

요구사항

탐사선의 위치에서 시글널을 보내어(위,아래,왼쪽,오른쪽)서 전파될 수 있는 시간의 최댓값을 출력하는 프로그램을 작성하는 것.
단, "\" || "/" 을 만나면 시그널은 방향을 전환한다.
※ 무한히 시그널이 보내질 경우 "Voyager"를 출력한다.

코드리뷰

char 2차원 배열에 값을 입력받고 탐사선의 위치에서 시그널의 4방향을 0,1,2,3 으로 표시후 깊이 우선 탐색을 이용 char 2차원 배열을 탐색하여 해당 시그널이 존재하는 시간을 측정했다.

visisted라는 2차원 배열을 시그널의 방향마다 초기화하였다. 하지만 방문만을 표시하지 않았다.

만약 시그널이 "\" || "/" 이런 문자들을 만나 무한히 순회하는 경우를 골라내기 위해 visited배열 값에는 방향을 표시해줌과 동시에 방문 처리를 하였다.

package tues_thurs_sat.simulation;

import java.util.Scanner;

public class voyagerOne {
    static int n, m;
    static char[][] map;
    static int dy[] = {-1, 0, 1, 0};
    static int dx[] = {0, 1, 0, -1};
    static int visited[][];

    // 재방문은 visited[]만이 아닌 방향도 기억하고 있어야 한다.
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new char[n][m];
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            map[i] = str.toCharArray();
        }
        int y = sc.nextInt() - 1;
        int x = sc.nextInt() - 1;


        int ans = -1;
        int dir = 0;
        for (int i = 0; i < 4; i++) {
            visited = new int[n][m];
            int t = dfs(y, x, i, 1);
            if (t == -1) {
                exchange(i);
                System.out.print("Voyager");
                return;
            } else if (ans < t) {
                ans=t;
                dir=i;
            }
        }
        exchange(dir);
        System.out.print(ans);
    }

    public static int dfs(int y, int x, int dir, int cnt) {
        visited[y][x] = dir + 1;
        if (map[y][x] == '\\') {
            if (dir == 0) {
                dir = 3;
            } else if (dir == 1) {
                dir = 2;
            } else if (dir == 2) {
                dir = 1;
            } else if (dir == 3) {
                dir = 0;
            }
        } else if (map[y][x] == '/') {
            if (dir == 0) {
                dir = 1;
            } else if (dir == 1) {
                dir = 0;
            } else if (dir == 2) {
                dir = 3;
            } else if (dir == 3) {
                dir = 2;
            }
        }

        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m || map[ny][nx] == 'C') {
            return cnt;
        } else if (visited[ny][nx] == dir + 1) {
            return -1;
        }
        int dist = dfs(ny, nx, dir, cnt + 1);
        return dist;
    }

    public static void exchange(int dir) {
        switch (dir) {
            case 0:
                System.out.println("U");
                break;
            case 1:
                System.out.println("R");
                break;
            case 2:
                System.out.println("D");
                break;
            case 3:
                System.out.println("L");
                break;
        }
    }
}