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

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

간단한 시뮬레이션 문제이다.

두가지 문제만 해결해주면 된다.

  1. 혁진이의 프로그램이 무한루프에 빠졌는지 확인하려면

    똑같은 좌표에 똑같은 방향을 가지고 똑같은 메모리의 상태로 들어오는 경우가 있는지 확인해주면 된다.

    이것을 체크해주기 위해 4차원배열 ck로 프로그램의 상태를 확인한다.

  2. ? 는 4방향 모두 가보는 것으로 체크하고, dfs로 탐색한다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
import java.util.Scanner;

public class Solution {
	static char[][] cmd;
	static int dir;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,-1,1};
	static boolean[][][][] ck;
	// 0 : -> // 1 : <- // 2 : 위 // 3 : 아래 // 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1;tc<=T;tc++) {
			int C = sc.nextInt();
			int R = sc.nextInt();
			int memory = 0;
			dir = 0;
			cmd = new char[C][R];
			ck = new boolean[C][R][4][16];
			// i좌표값 j좌표값 방향 메모리 
			for(int i=0; i<C; i++) {
				cmd[i] = sc.next().toCharArray();
			}
			
			// C 세로 R 가로
			if (go(0,0,true,0,R,C,memory,0) ) {
				System.out.println("#"+tc+" YES");
			} else {
				System.out.println("#"+tc+" NO");
			}
		}
	}
	public static boolean go(int i,int j,boolean check,int dir,int R,int C,int memory,int depth) {
		if ( depth == 2 ) {
			return false;
		}
		while ( check ) {
			switch ( cmd[i][j] ) {
				case '<':
					dir = 1;
					break;
				case '>':
					dir = 0;
					break;
				case '^': 
					dir = 2;
					break;
				case 'v':
					dir = 3;
					break;
				case '_': 
					if(memory == 0) {
						dir = 0;
					} else {
						dir = 1;
					}
					break;
				case '|': 
					if(memory == 0) {
						dir = 3;
					} else {
						dir = 2;
					}
					break;
				case '?': 
					if ( j+1 < R && go(i,j+1,true,0,R,C,memory,depth+1) ) {
						check = false;
					} 
                    if ( j-1 >= 0 && go(i,j-1,true,1,R,C,memory,depth+1) ) {
						check = false;
					} 
                    if ( i-1 >= 0 && go(i-1,j,true,2,R,C,memory,depth+1)) {
						check = false;
					} 
                    if ( i+1 < C && go(i+1,j,true,3,R,C,memory,depth+1 )) {
						check = false;
					}
					break;
				case '.':
					break;
				case '@': 
					check = false;
					break;
				case '+': 
					if (memory == 15) {
						memory = 0;
					} else {
						memory++;
					}
					break;
				case '-': 
					if (memory == 0) {
						memory = 15;
					} else {
						memory--;
					}
					break;
				default:
					memory = cmd[i][j]-'0';
					break;
			}
			
			
			if ( ck[i][j][dir][memory] ) {
				return false;
			}
			ck[i][j][dir][memory] = true;
		
			i = i + dy[dir];
			j = j + dx[dir];
			
			if ( i >= C ) {
				i = 0;
			} else if ( i < 0 ) {
				i = C-1;
			} else if ( j >= R ) {
				j = 0;
			} else if ( j < 0 ) {
				j = R-1;
			}
			
		}
		if (!check) {
			return true;
		} else {
			return false;
			
		}
	}
}