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

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

public class Solution {
    static char[][] map;

    static int[] dr = {0,1,0,-1};
    static int[] dc = {1,0,-1,0};
    static boolean flag = false;
    static int[][][][] ck;
    static int R;
    static int C;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T ;
        T = Integer.parseInt(st.nextToken());
        for(int test_case = 1; test_case <= T; test_case++)
        {
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            map = new char[R][C];

            for (int i = 0; i < R; i++) {
                st = new StringTokenizer(br.readLine());
                String str = st.nextToken();
                for (int j = 0; j < C; j++) {
                    map[i][j] = str.charAt(j);
                }
            }
            flag = false;
            int row  = 0;
            int col =0;
            int dir = 0;
            int memory  = 0;

            ck = new int[R][C][16][4];
            check(row,col,memory,dir);
            if (flag){
                System.out.println("#"+test_case + " "+"YES");
            }
            else System.out.println("#"+test_case + " "+"NO");
        }
    }
    public static void check(int row, int col, int memory,int dir){

        if(ck[row][col][memory][dir]==0){
            ck[row][col][memory][dir]=1;
        }
        else {
            return;
        }

        if(map[row][col]=='<'){
            dir = 2;
        }else if(map[row][col]=='>'){
            dir = 0;
        }else if(map[row][col]=='^'){
            dir = 3;
        }
        else if(map[row][col]=='v'){
            dir = 1;
        }
        else if(map[row][col]=='_'){
            if(memory==0){
                dir = 0;
            }
            else {
                dir = 2;
            }

        }
        else if(map[row][col]=='|'){
            if(memory==0){
                dir = 1;
            }
            else {
                dir = 3;
            }
        }
        else if(map[row][col]=='?'){
            for (int i = 0; i < 4; i++) {
                int ndir = (dir +i)%4;
                int nrow=row+dr[ndir];
                int ccol=col+dc[ndir];
                if(nrow==R) nrow = 0;
                if(nrow==-1) nrow = R-1;
                if(ccol==C) ccol = 0;
                if(ccol==-1) ccol = C-1;
                check(nrow,ccol,memory,ndir);
            }
            return;
        }
        else if(map[row][col]=='.'){

        }
        else if(map[row][col]=='@'){
            flag = true;
            return;
        }
        else if(map[row][col]=='+'){
            if(memory==15) memory = 0;
            else memory++;
        }
        else if(map[row][col]=='-'){
            if(memory==0) memory = 15;
            else memory--;
        }
        else {
            memory = map[row][col] -'0';
        }
        row=row+dr[dir];
        col=col+dc[dir];
        if(row==R) row = 0;
        if(row==-1) row = R-1;
        if(col==C) col = 0;
        if(col==-1) col = C-1;
        check(row,col,memory,dir);
    }

}

풀이방법

📢전체적인 구조는 dfs탐색을 통해 @를 만나면 flag=true;를 통해 끝낼수 있음을 체크하고, 없다면 NO를 출력한다.
이때, 무한반복 탈출조건은 같은 좌표에, 같은 메모리크기, 같은 방향이 온다면 탈출하도록 하여 끝낼 수 없음을 체크한다.

1. check 함수에 좌표와 메모리값, 방향정보를 담아 탐색을 시작한다.
2. 조건에 따라 구현하는데 이때, '?'조건은 4방향의 경우의 수를 모두 탐색해야 하므로, 각기 다른 방향으로 총 4번의 재귀호출을 수행한다.
   이때, 15 -> 0, 0 -> 15로 가는것에 주의하자.
3. '?' 문자가 아니라면 그대로 한번만 다음 좌표로 재귀호출 해준다.
4. 무한반복 탈출조건을 구현할때, 4차원 배열을 사용하여 같은 4차원 배열에 들어온다면, 탈출한다.

후기

보통 탈출조건을 만나면 system.exit(0)으로 탈출하는데, 이 문제는 특정 조건을 찾아야 하는게 까다로웠다.
또한, '?'가 어차피 4방향이라 ndir이 아니라 그냥 i를 넣어 0,1,2,3으로 진행하게 했는데, 뭔가 반례가 있는것 같다. ndir을 만들어야한다
비슷한 유형의 문제를 풀었던 기억이 있어서 4차원 배열을 통해 체크할 수 있었던것 같다.