SWEA 1824. 혁진이의 프로그램 검증 :: 돼지개발자

출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx

"DFS와 가지치기"

DFS를 이용해 해당 위치의 명령을 수행한다. 이 때, '?' 명령의 경우 4방향 dx,dy 에 대해 모두 탐색해 준다. 가능한 경우가 나왔을 때는 boolean 변수 find를 true 설정해주어 더이상 탐색하지 않도록 한다.

범위가 벗어날 경우 문제에서 제시한 예외처리를 해주는 것도 중요하다. 일일이 x,y 좌표가 범위를 벗어난 경우를 체크하자.

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution {     static int T;     static int r,c;     static char[][] map;     static boolean[][][][] visited;    // x좌표, y좌표, 방향, 메모리 종류     static boolean find;     static int[] dx = {-1,0,1,0};    // 동서남북 1320     static int[] dy = {0,1,0,-1};          public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  T = Integer.parseInt(br.readLine());         int t = 1;                  while(T-- > 0) {                          StringTokenizer 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];             find = false;             boolean hasEnd = false;                          for (int i = 0; i < r; i++) {                 map[i] = br.readLine().toCharArray();                 for (int j = 0; j < c; j++) {                     if(map[i][j] == '@')                         hasEnd = true;                 }             }             // '@' 가 있는 테스트 케이스만 탐색한다.             if(hasEnd) {                 solve(0,0,1,0);             }             System.out.printf("#%d %s\n",t++,find ? "YES" : "NO");         }     }          static void solve(int x, int y, int d, int mem) {         if(find) return ;                  if(map[x][y] == '@') {             find = true;             return ;         }                  // 방문한 노드라면 패스         if(visited[x][y][d][mem]) return ;                  // 방문 처리         visited[x][y][d][mem] = true;                  int nd = d;         int nm = mem;                  switch(map[x][y]) {         case '<': nd = 3; break;         case '>': nd = 1; break;         case '^': nd = 0; break;         case 'v': nd = 2; break;         case '_': nd = (mem == 0 ? 1 : 3); break;         case '|': nd = (mem == 0 ? 2 : 0); break;         case '+': nm = (mem == 15 ? 0 : mem+1); break;         case '-': nm = (mem == 0 ? 15 : mem-1); break;         case '0':case '1':case '2':case '3':case '4':          case '5':case '6':case '7':case '8':case '9':             nm = map[x][y] -'0';             break;         }                  // 물음표면 네 방향 체크         if (map[x][y] == '?') {             for (int i = 0; i < 4; i++) {                 if(x+dx[i] < 0 ) {                     solve(r-1,y+dy[i],i,nm);                 }                 else if(x+dx[i] >= r) {                     solve(0,y+dy[i],i,nm);                 }                 else if ( y+dy[i] < 0) {                     solve(x+dx[i],c-1,i,nm);                 }                 else if ( y+dy[i] >= c) {                     solve(x+dx[i],0,i,nm);                 }                 else {                     solve(x+dx[i],y+dy[i],i,nm);                     }             }         }         else {             if(x+dx[nd] < 0 ) {                 solve(r-1,y+dy[nd],nd,nm);             }             else if(x+dx[nd] >= r) {                 solve(0,y+dy[nd],nd,nm);             }             else if ( y+dy[nd] < 0) {                 solve(x+dx[nd],c-1,nd,nm);             }             else if ( y+dy[nd] >= c) {                 solve(x+dx[nd],0,nd,nm);             }             else {                 solve(x+dx[nd],y+dy[nd],nd,nm);                 }         }     } } Colored by Color Scripter

cs