[SWEA/D5] 7258. 혁진이의 프로그램 검증 - JAVA 자바

• 149ms
• 빡구현 BFS

문자에 따라 명령어를 실행시켰을 때, 프로그램 종료 문자인 @ 까지 도달할 수 있는가 없는가에 대해 확인하는 문제이다.

 

이 문제에서 중요하게 고려해야 할 점은

1. ? 문자는 4방향 중 어느 방향으로 갈 것인가
2. 프로그램이 종료하지 않는 케이스면 어떻게 종료하지 않은 것을 판단할 것인가

두 가지만 신경쓴다면 복잡하지만 빡구현으로 해결할 수 있다.

 

? 문자를 만났을 때, 각각의 방향에 따라 경우의 수를 따져야하므로 BFS로 구현하였다. 또한 프로그램이 종료되지 않는 케이스를 판단하기 위해 (행, 열, 방향, 메모리)의 방문체크를 해주는 4차원 배열이 필요하다. (x,y)좌표와 방향, 메모리에 방문체크가 되어있다면 계속 루프를 돌고 있는 것으로 프로그램이 종료할 수 없는 경우이다.

 

그래서 행, 열, 방향, 메모리를 저장하는 Node 클래스를 만든 후, 명령에 맞게 동작시키는 코드를 구현하였다.

 

# 소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
    static int R, C;
    static String result = "NO";
    static char[][] board;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static boolean[][][][] visited;

    static class Node {
        int x;
        int y;
        int d;
        int memory;

        public Node(int x, int y, int d, int memory) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.memory = memory;
        }
    }

    // (0,0) 부터 시작
    public static void bfs() {
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(0, 0, 3, 0));
        while (!q.isEmpty()) {
            Node now = q.poll();

            if (visited[now.x][now.y][now.d][now.memory])
                continue;

            visited[now.x][now.y][now.d][now.memory] = true;

            char c = board[now.x][now.y];

            if (c == '@') {
                result = "YES";
                break;
            } else if (c == '?') {
                for (int i = 0; i < 4; i++) {
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];

                    nx = nx == R ? 0 : nx;
                    nx = nx == -1 ? R - 1 : nx;
                    ny = ny == C ? 0 : ny;
                    ny = ny == -1 ? C - 1 : ny;

                    q.add(new Node(nx, ny, i, now.memory));
                }
                continue;
            } else if (c == '<') now.d = 2;
            else if (c == '>') now.d = 3;
            else if (c == '^') now.d = 0;
            else if (c == 'v') now.d = 1;
            else if (c == '_') now.d = now.memory == 0 ? 3 : 2;
            else if (c == '|') now.d = now.memory == 0 ? 1 : 0;
            else if (c - '0' >= 0 && c - '0' <= 9) now.memory = c - '0';
            else if (c == '+') now.memory = now.memory == 15 ? 0 : now.memory + 1;
            else if (c == '-') now.memory = now.memory == 0 ? 15 : now.memory - 1;

            now.x += dx[now.d];
            now.y += dy[now.d];

            now.x = now.x == R ? 0 : now.x;
            now.x = now.x < 0 ? R - 1 : now.x;
            now.y = now.y == C ? 0 : now.y;
            now.y = now.y < 0 ? C - 1 : now.y;

            q.add(now);
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());

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

            board = new char[R][C];
            visited = new boolean[R][C][4][16];

            // 상0 하1 좌2 우3
            for (int i = 0; i < R; i++) {
                String str = br.readLine();
                for (int j = 0; j < C; j++)
                    board[i][j] = str.charAt(j);
            }

            bfs();

            sb.append('#').append(t).append(' ').append(result).append('\n');
            result = "NO";
        }
        System.out.println(sb);
    }
}

코드에 대한 피드백은 언제나 환영입니다🧚🏻‍♀️