[삼성 sw expert 아카데미]1824. 혁진이의 프로그램 검증

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

출처 : 삼성 sw expert 아카데미 1824 문제

- '?' 경우 때문에 dp로 풀어야 함.

- 테스트케이스에 '@' 없는 경우도 있으니 미리 체크!

- x,y 랑 col, row랑 헷갈릴 수 있으니 제대로 적어놓고 진행하기.

package algorithm_practice;
 
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
 
public class sw_expert_1824 {
    
    // x, y, memory, location
    private static boolean map[][][][];
    // 끝났는지 여부 체크
    private static boolean exit = false;
    // @ 찾았는지 체크
    private static boolean isYes = false;
 
    // 메모리
    private static int memory = 0;
 
    int col=0,  row = 0;
    
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        sw_expert_1824 test = new sw_expert_1824();
        int cnt = 1;
        while(cnt <= t) {
            System.out.print("#"+cnt+" ");
            cnt++;
    
            map = new boolean [21][21][16][5];
            exit = false;
            isYes = false;
            memory = 0;
            
            int s = sc.nextInt();
            int e = sc.nextInt();
            StringBuilder input = new StringBuilder();
            
            for(int i=0;i<s;i++) {
                input.append(sc.next());
            }
            
            System.out.println(test.run(s, e,input.toString()));
        }
        
    }
    
    public String run(int row, int col, String input) {
        char command[][] = new char [row][col];
        // String -> char [][] 변경.
        if(!fill_array(row,col,command,input))
            return "NO";  // '@' 없을 경우를 확인.
        
        // row , col 값은 매개변수로 전달해줘도 되지만 일단 전역변수로 변경.
        this.col = col;
        this.row = row;
        
        // [x][y] -> [col][row]  :x가 column , y가 row !!
        int x = 0, y=0;
        
        find_move(command,x, y,0);
        
        String result = "";
        
        // '@' 이동가능한 경우, isYes = true 
        if(isYes) result = "YES";
        else result = "NO";
        
        return result;
    }
    
public void find_move(char comm[][],int x, int y, int location) {
        
        if (exit) 
            return;
        
        switch(comm[x][y]) {
        case '>':
            location = 0;
            break;
            
        case '<':
            location = 1;
            break;
        
        case 'v':
            location = 2;
            break;
        case '^':
            location = 3;
            break;
            
        case '_':
            location = memory == 0 ? 0 : 1 ;
            break;
            
        case '|':
            location = memory == 0 ? 2 : 3 ;
            break;
        
        case '?':
            // 무작위로 상하좌우로 변경.
            location = 4;
            break;
        case '.':
            
            break;
        case '@':
            exit = true;
            isYes = true;
            return;
        case '+':
            memory = memory == 15 ? 0 : memory+1;
            break;
        case '-':
            memory = memory == 0 ? 15 : memory-1;
            break;
        default:
            memory = comm[x][y] - '0';
            break;
 
        }
        
        
        // 이전에 이동했는지 확인.
        if( map[x][y][memory][location]) {
            exit = true;
            return;
        } else {
            map[x][y][memory][location]  = true;
        }
        
        // 다음 이동할 위치 가져오기.
        List<Point> list = change_next_location(x,y,location);
        for(Point p : list) {
            // 이동할 때마다 exit = false 로 변경해줘야 함.
            // 상, 하, 좌, 우 모두 이동해서 확인해줘야함.!
            if(!isYes) exit = false;
            find_move(comm, p.x,p.y,p.location);
            
        }
        
        
        return;
        
    }
    
 
    
    public List<Point> change_next_location(int x , int y, int location) {
        List<Point> list = new ArrayList<>();
        
        
        switch(location) {
        case 4: 
            // case 0,1,2,3  모두 실행하면서 
            // 상, 하, 좌, 우 모두 검사하기.
 
        case 0: // 오른쪽
            Point temp0 = new Point(x, y,0);
            temp0.y = y + 1 >= col ? 0: y + 1;
            temp0.location = 0;
            list.add(temp0);
            
            if(location!=4) break;
        case 1: // 왼쪽
            Point temp1 = new Point(x, y,0);
            temp1.y = y - 1 < 0 ? col-1: y - 1;
            temp1.location = 1;
            list.add(temp1);
            if(location!=4) break;
        case 2: // 아래쪽
            Point temp2 = new Point(x, y,0);
            temp2.x = x + 1 >= row ? 0 : x + 1;
            temp2.location = 2;
            list.add(temp2);
            if(location!=4) break;
        case 3: // 위쪽
            Point temp3 = new Point(x, y,0);
            temp3.x = x - 1 < 0 ? row -1: x - 1;
            temp3.location = 3;
            list.add(temp3);
            if(location!=4) break;
        }
        
        return list;
    }
    
    
    
 
    // String -> char [][] 로 변경
    public boolean fill_array(int row, int col, char comm[][], String input) {
        char[] input_ary = input.toCharArray();
        int cnt = 0;
        boolean isA = false; // '@' 있는지 여부 확인.
        for(int i=0;i<row;i++) {
            for(int j=0;j<col;j++) {
                if(input_ary[cnt] == '@') isA = true;
                comm[i][j] = input_ary[cnt++];
            }
        }
        return isA;
    }
    
    
}
 
// x, y 좌표, location 정보 담는 객체.
class Point{
    int x;
    int y;
    int location;
    
    public Point(int x, int y, int location) {
        this.x = x;
        this.y = y;
        this.location = location;
    }
}