[SWEA] 1824. 혁진이의 프로그램 검증 (시뮬레이션/Java)

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

📌 풀이 과정

단순한 시뮬레이션 문제인줄 알았는데 무려 4차원 방문 배열이 필요한 문제였다.

dfs 재귀로 계속 탐색하니 StackOverflow 가 떠서 골치가 아픈 문제다.

 

이동 방향에 따른 인덱스 관리하기

문제에서는 이동 방향이 2차원 격자의 크기를 벗어날 경우 반대편에 있는 위치로 이동해야 한다.

이때 모듈러 연산을 통해 인덱스 관리를 해야한다.

우리가 일반적으로 사용하는 (index + 1) % size 방식은 음수 인덱스를 처리할 수 없으니

index = (index - 1 + size) % size

위 방식으로 음수 인덱스를 방지하여 순환할 수 있도록 한다.

 

4차원 방문배열이 왜 필요하지?

이 문제의 목적은 혁진이는 자신이 작성한 프로그램이 결국에는 멈출 수 있는지 확인하는 것이다.

? 명령어로 인해 이동 방향을 상하좌우 중 하나로 무작위로 변경할 수 있기 때문에 모든 방향을 탐색해야 한다.

즉, 동일한 위치를 탐색하더라도 방향과 메모리 값에 따라 완전히 다른 상태이기 때문에

특정 위치에서 특정 방향과 메모리 값으로 도달한 상태가 이전에 방문한 적이 있는지 확인해

무한 루프를 방지하고 올바르게 상태를 관리할 수 있도록 해야한다.

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution {
    static int R, C, memory;
    static boolean result;
    static boolean[][][][] visited;
    static char[][] map;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken()); // 행
            C = Integer.parseInt(st.nextToken()); // 열
            map = new char[R][C];
            visited = new boolean[R][C][4][16]; // 위치, 방향, 메모리 상태를 모두 고려한 방문 배열

            for(int i = 0; i < R; i++) {
                map[i] = br.readLine().toCharArray();
            }

            result = false;
            memory = 0;
            if (dfsLoop(0, 0, 3)) sb.append("YES\n");
            else sb.append("NO\n");
        }
        System.out.print(sb);
    }

    private static boolean dfsLoop(int x, int y, int program) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{x, y, program, memory});

        while (!stack.isEmpty()) {
            int[] curr = stack.pop();
            x = curr[0];
            y = curr[1];
            program = curr[2];
            memory = curr[3];

            if (visited[x][y][program][memory]) continue;
            visited[x][y][program][memory] = true;

            char command = map[x][y];
            switch(command) {
                case '<': program = 2; break;
                case '>': program = 3; break;
                case '^': program = 0; break;
                case 'v': program = 1; break;
                case '_': program = (memory == 0) ? 3 : 2; break;
                case '|': program = (memory == 0) ? 1 : 0; break;
                case '+': memory = (memory + 1) % 16; break;
                case '-': memory = (memory + 15) % 16; break;
                case '@': return true;
            }

            if ('0' <= command && command <= '9') {
                memory = command - '0';
            }

            // 이동하기
            if (command == '?') {
                for (int i = 0; i < 4; i++) {
                    int nx = (x + dir[i][0] + R) % R;
                    int ny = (y + dir[i][1] + C) % C;
                    if (!visited[nx][ny][i][memory]) {
                        stack.push(new int[]{nx, ny, i, memory});
                    }
                }
            } else {
                int nx = (x + dir[program][0] + R) % R;
                int ny = (y + dir[program][1] + C) % C;
                if (!visited[nx][ny][program][memory]) {
                    stack.push(new int[]{nx, ny, program, memory});
                }
            }
        }
        return false;
    }
}