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

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE

* The copyright in this matter is in SWEA

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

생각보다 복잡한 구현 문제다...

우선 수행 명령에 맞게 동작시키는게 우선이다.

< 이동 방향을 왼쪽으로 바꾼다.

> 이동 방향을 오른쪽으로 바꾼다.

^ 이동 방향을 위쪽으로 바꾼다.

v 이동 방향을 아래쪽으로 바꾼다.

_ 메모리에 0이 저장되어 있으면 이동 방향을 오른쪽으로 바꾸고, 아니면 왼쪽으로 바꾼다.

| 메모리에 0이 저장되어 있으면 이동 방향을 아래쪽으로 바꾸고, 아니면 위쪽으로 바꾼다.

? 이동 방향을 상하좌우 중 하나로 무작위로 바꾼다. 방향이 바뀔 확률은 네 방향 동일하다.

. 아무 것도 하지 않는다.

@ 프로그램의 실행을 정지한다.

0~9 메모리에 문자가 나타내는 값을 저장한다.

+ 메모리에 저장된 값에 1을 더한다. 만약 더하기 전 값이 15이라면 0으로 바꾼다.

- 메모리에 저장된 값에 1을 뺀다. 만약 빼기 전 값이 0이라면 15로 바꾼다.

+

만약 다음 이동이 2차원 격자의 바깥으로 이동하는 방향이면, 반대편에 있는 위치로 이동한다.

//

구현 과정에서 key point !!

4가지의 상태를 관리하는 것이다.

(방향 + 메모리 + 행 + 열)의 상태를 모두 관리해주는 상태배열이 필요하다.

Why?!

행/열 상태만을 관리한다면? 다른 메모리 정보를 가지고 명령을 처리할 수 없게 된다.

메모리/행/열 상태만을 관리한다면? 다른 방향 정보를 가지고 명렬ㅇ을 처리할 수 없게 된다.

결과적으로.

방향, 메모리, 행, 열 상태를 모두 관리해주는 visited 배열을 사용하여

같은 상태로 방문했을 경우 pass 해주면 된다.

3차원 상태배열은 사용해봤지만

4차원 상태배열을 접해볼 수 있는 좋은 기회였다.

#. Code_dfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution1824 {
 
    static int R, C;
    static boolean visited[][][][];
    static char oper[][];
    static int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}; // 동,남,서,북
    static int res; // 1: 성공
    static class Info {
        int x, y, dir, mem;
 
        public Info(int x, int y, int dir, int mem) {
            super();
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.mem = mem;
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            oper = new char[R][C]; 
            res = -1;
            
            for (int i = 0; i < R; i++) {
                oper[i] = br.readLine().toCharArray();
                
                boolean isAno = false;
                for (int j = 0; j < C; j++) {
                    if(res != 0 && oper[i][j] == '@') isAno = true;
                }
                
                if(isAno) res = 0;
            }
            
            visited = new boolean[4][16][R][C];
            // @ 가 있으면 시작
            if(res == 0) process(new Info(0, 0, 0, 0));    
            
            System.out.println("#" + tc + " " + (res == 1 ? "YES" : "NO"));
        }
        
    }
 
    private static void process(Info info) {
        
        if(res != 0) return;
        
        // 이미 방문한 곳이면 return
        if(visited[info.dir][info.mem][info.x][info.y]) return;
        
        Info newInfo = new Info(info.x, info.y, info.dir, info.mem);
        
        char now = oper[newInfo.x][newInfo.y];
        visited[newInfo.dir][newInfo.mem][newInfo.x][newInfo.y] = true;
        
//        0~9    메모리에 문자가 나타내는 값을 저장한다.
        if(now >= '0' && now <= '9') {
            newInfo.mem = now - '0';
        } 
//        < 이동 방향을 왼쪽으로 바꾼다.
        else if(now == '<') {
            newInfo.dir = 2;
        }
//        >    이동 방향을 오른쪽으로 바꾼다.
        else if(now == '>') {
            newInfo.dir = 0;
        }
//        ^    이동 방향을 위쪽으로 바꾼다.
        else if(now == '^') {
            newInfo.dir = 3;
        }
//        v    이동 방향을 아래쪽으로 바꾼다.
        else if(now == 'v') {
            newInfo.dir = 1;
        }
//        _    메모리에 0이 저장되어 있으면 이동 방향을 오른쪽으로 바꾸고, 아니면 왼쪽으로 바꾼다.
        else if(now == '_') {
            newInfo.dir = (newInfo.mem == 0) ? 0 : 2;
        }
//        |    메모리에 0이 저장되어 있으면 이동 방향을 아래쪽으로 바꾸고, 아니면 위쪽으로 바꾼다.
        else if(now == '|') {
            newInfo.dir = (newInfo.mem == 0) ? 1 : 3;
        }
//        ?    이동 방향을 상하좌우 중 하나로 무작위로 바꾼다. 방향이 바뀔 확률은 네 방향 동일하다.
        else if(now == '?') {
            for (int d = 0; d < 4; d++) {
                int nextDir = (newInfo.dir + d) % 4;
                
                int nextX = newInfo.x + dx[nextDir];
                int nextY = newInfo.y + dy[nextDir];
                // 2차원 격자의 바깥으로 이동하는 방향이면, 반대편에 있는 위치로 이동
                if(nextX < 0) nextX = R - 1;
                else if(nextX >= R) nextX = 0;
                else if(nextY < 0) nextY = C - 1;
                else if(nextY >= C) nextY= 0;
                
                process(new Info(nextX, nextY, nextDir, newInfo.mem));
            }
            
            return;
        }
//        .    아무 것도 하지 않는다.
//        @    프로그램의 실행을 정지한다.
        else if(now == '@') {
            res = 1;
        }
//        +    메모리에 저장된 값에 1을 더한다. 만약 더하기 전 값이 15이라면 0으로 바꾼다.
        else if(now == '+') {
            newInfo.mem = (newInfo.mem == 15) ? 0 : newInfo.mem + 1;
        }
//        -    메모리에 저장된 값에 1을 뺀다. 만약 빼기 전 값이 0이라면 15로 바꾼다.
        else if(now == '-') {
            newInfo.mem = (newInfo.mem == 0) ? 15 : newInfo.mem - 1;
        }
 
        // 이동
        newInfo.x += dx[newInfo.dir];
        newInfo.y += dy[newInfo.dir];
        // 2차원 격자의 바깥으로 이동하는 방향이면, 반대편에 있는 위치로 이동
        if(newInfo.x < 0) newInfo.x = R - 1;
        else if(newInfo.x >= R) newInfo.x = 0;
        else if(newInfo.y < 0) newInfo.y = C - 1;
        else if(newInfo.y >= C) newInfo.y = 0;
        
        process(newInfo);
    }
    
}

#. Code_bfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution1824_bfs {
 
    static int R, C;
    static char oper[][];
    static int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}; // 동,남,서,북
    static class Info {
        int x, y, dir, mem;
 
        public Info(int x, int y, int dir, int mem) {
            super();
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.mem = mem;
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            oper = new char[R][C]; 
            
            for (int i = 0; i < R; i++) {
                oper[i] = br.readLine().toCharArray();
            }
 
            System.out.println("#" + tc + " " + (process() ? "YES" : "NO"));
        }
        
    }
 
    private static boolean process() {
        
        boolean[][][][] visited = new boolean[4][16][R][C];
        Queue<Info> q = new LinkedList<>();
        q.add(new Info(0, 0, 0, 0));
        
        while(!q.isEmpty()) {
            
            Info now = q.poll();
            
            // 이미 방문한 곳이면 pass
            if(visited[now.dir][now.mem][now.x][now.y]) continue;
            // 현재 명령
            char c = oper[now.x][now.y];
            visited[now.dir][now.mem][now.x][now.y] = true;
            
            // 0~9    메모리에 문자가 나타내는 값을 저장한다.
            if(c >= '0' && c <= '9') {
                now.mem = c - '0';
            } 
            // < 이동 방향을 왼쪽으로 바꾼다.
            else if(c == '<') {
                now.dir = 2;
            }
            // >    이동 방향을 오른쪽으로 바꾼다.
            else if(c == '>') {
                now.dir = 0;
            }
            // ^    이동 방향을 위쪽으로 바꾼다.
            else if(c == '^') {
                now.dir = 3;
            }
            // v    이동 방향을 아래쪽으로 바꾼다.
            else if(c == 'v') {
                now.dir = 1;
            }
            // _    메모리에 0이 저장되어 있으면 이동 방향을 오른쪽으로 바꾸고, 아니면 왼쪽으로 바꾼다.
            else if(c == '_') {
                now.dir = (now.mem == 0) ? 0 : 2;
            }
            // |    메모리에 0이 저장되어 있으면 이동 방향을 아래쪽으로 바꾸고, 아니면 위쪽으로 바꾼다.
            else if(c == '|') {
                now.dir = (now.mem == 0) ? 1 : 3;
            }
            // ?    이동 방향을 상하좌우 중 하나로 무작위로 바꾼다. 방향이 바뀔 확률은 네 방향 동일하다.
            else if(c == '?') {
                for (int d = 0; d < 4; d++) {
                    int nextX = now.x + dx[d];
                    int nextY = now.y + dy[d];
                    // 2차원 격자의 바깥으로 이동하는 방향이면, 반대편에 있는 위치로 이동
                    if(nextX < 0) nextX = R - 1;
                    else if(nextX >= R) nextX = 0;
                    else if(nextY < 0) nextY = C - 1;
                    else if(nextY >= C) nextY= 0;
                    
                    q.add(new Info(nextX, nextY, d, now.mem));
                }
                
                continue;
            }
            // @    프로그램의 실행을 정지한다.
            else if(c == '@') {
                return true;
            }
            // +    메모리에 저장된 값에 1을 더한다. 만약 더하기 전 값이 15이라면 0으로 바꾼다.
            else if(c == '+') {
                now.mem = (now.mem == 15) ? 0 : now.mem + 1;
            }
            // -    메모리에 저장된 값에 1을 뺀다. 만약 빼기 전 값이 0이라면 15로 바꾼다.
            else if(c == '-') {
                now.mem = (now.mem == 0) ? 15 : now.mem - 1;
            }
            // .    아무 것도 하지 않는다.
            // 이동
            now.x += dx[now.dir];
            now.y += dy[now.dir];
            // 2차원 격자의 바깥으로 이동하는 방향이면, 반대편에 있는 위치로 이동
            if(now.x < 0) now.x = R - 1;
            else if(now.x >= R) now.x = 0;
            else if(now.y < 0) now.y = C - 1;
            else if(now.y >= C) now.y = 0;
            
            q.add(now);
        }
        
        return false;
    }
}