Java - [SWEA] 1824 - 혁진이의 프로그램 검증

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx

SW Expert Academy

 

문제

 

한개의 메모리를 가지고, 주어진 명령 집합을 돌아다니면서 명령을 수행할 때 이 프로그램이 끝나는지, 끝나지 않고 무한히 실행하는지 판별하는 문제이다.

 

풀이

이 문제에서 핵심은 어떻게 무한히 실행되는지를 판별하는 것이라고 생각한다. 단순히 2차원 배열로 방문 여부를 따지기에는 방향을 바꾸어 그냥 한번 지나칠 수 도 있고, 지나칠때 메모리의 값이나 방향이 다르면 다 다르기 때문에 불가능 하다.

 

따라서 방문여부를 판별할때는 방향, 메모리의 값을 모두 포함하여 4차원 배열을 사용하여 판별하도록 하였다.

-> visited[x좌표][y좌표][방향][메모리]

 

방문 여부를 확인할 수 있다면, 그 뒤 방향에 맞게 명령을 수행하는 것을 DFS 또는 BFS로 구현하면 되는데, 필자의 경우 DFS로 해결하였다.

 

이 외에도, @가 애초에 주어지지 않는다면 종료할 수 없다는 의미이기 때문에 검증을 거치도록 하였고, ?의 경우 네 방향 모두 확률이 동일하다고 하였기 때문에 네 방향으로 모두 dfs를 진행시켰다.

코드

package D4;

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

class swea1824 {

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static boolean[][][][] visited;
    static char[][] command;
    static int result, R, C;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        T = Integer.parseInt(br.readLine());

        for(int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            visited = new boolean[R][C][4][16];
            command = new char[R][C];
            result = -1;

            for (int i = 0; i < R; i++) {
                String str = br.readLine();
                for (int j = 0; j < C; j++) {
                    command[i][j] = str.charAt(j);
                    if (command[i][j] == '@') {
                        result = 0;
                    }
                }
            }

            if (result == 0)
                dfs(0, 0, 0, 0);

            if (result == 1) {
                System.out.println("#" + tc + " " + "YES");
            } else {
                System.out.println("#" + tc + " " + "NO");
            }
        }
    }

    static void dfs(int x, int y, int dir, int memory) {
        if (result != 0) {
            return;
        }
        if (visited[x][y][dir][memory]) {
            return;
        }

        visited[x][y][dir][memory] = true;
        char oper = command[x][y];

        if (oper >= '0' && oper <= '9') {
            memory = oper - '0';
        } else if (oper == '<') {
            dir = 2;
        } else if (oper == '>') {
            dir = 0;
        } else if (oper == 'v') {
            dir = 1;
        } else if (oper == '^') {
            dir = 3;
        } else if(oper == '_') {
            dir = (memory == 0) ? 0 : 2;
        } else if(oper == '|') {
            dir = (memory == 0) ? 1 : 3;
        }
        else if (oper == '?') {
            for (int i = 0; i < 4; i++) {
                int nextDir = (dir + i) % 4;
                int nx = x + dx[nextDir];
                int ny = y + dy[nextDir];

                if (nx < 0) nx = R - 1;
                else if (nx >= R) nx =  0;
                else if (ny < 0) ny = C - 1;
                else if (ny >= C) ny =  0;

                dfs(nx, ny, nextDir, memory);
            }
            return ;
        } else if (oper == '@') {
            result = 1;
        } else if(oper == '+') {
            memory = (memory == 15) ? 0 : memory + 1;
        } else if(oper == '-') {
            memory = (memory == 0) ? 15 :memory - 1;
        }

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx < 0) nx = R - 1;
        else if (nx >= R) nx =  0;
        else if (ny < 0) ny = C - 1;
        else if (ny >= C) ny =  0;

        dfs(nx, ny, dir, memory);
    }


}