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

1824 혁진이의 프로그램 검증

풀이)

dfs를 통해 탐색해준 문제이다.

주의할점은 ? 문자와 cycle 여부이다.

1. ? 문자일 경우, 4방향으로 바뀔 확률이 동일하니깐 4방향 모두 탐색해봄으로 해결했다.

2. sample_input의 2번 처럼, 

   (sample 2)

    2 6

    5>--v.
    .^--_@

   탐색이 끝나지 않고 계속 돌아가는 상황이 생길 수 있다. -> cycle 생성

   이는 bool visited[20][20][16][4] 4차원 배열을 통해 한 번 겪었던 상황이면 다시 겪지 않도록 해줬다.

   visited[r][c][mem][direction] == true?

   : r행 c열 번째 칸을 메모리에 mem 정수가 저장되어있고, 방향이 dir일때 방문했었다 라는 뜻.

코드)

#include <stdio.h>
#include <iostream>
#include <cstring> //memset()함수를 쓰기위해
using namespace std;
 
int T, r, c, memory, dir;
bool result;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 }; //우좌하상
char map[20][20];
bool visited[20][20][16][4];
 
void dfs(int x, int y) {
    if (result) return; //프로그램 실행 정지될 수 있다면
 
    if (visited[x][y][memory][dir]) return; //이미 겪었던 상황이라면
    else visited[x][y][memory][dir] = true;
 
 
    switch (map[x][y]) {
    
    case '>':
        dir = 0;
        break;
    case '<':
        dir = 1;
        break;
    case 'v':
        dir = 2;
        break;
    case '^':
        dir = 3;
        break;
    case '_':
        if (memory == 0) dir = 0;
        else dir = 1;
        break;
    case '|':
        if (memory == 0) dir = 2;
        else dir = 3;
        break;
    case '@':
        result = true;
        return;
    case '+':
        if (memory == 15) memory = 0;
        else memory += 1;
        break;
    case '-':
        if (memory == 0) memory = 15;
        else memory -= 1;
        break;
    }
 
    if ('0' <= map[x][y] && map[x][y] <= '9') {
        memory = map[x][y] - '0';
    }
 
    if (map[x][y] == '?') {
        for (int i = 0; i < 4; i++) {
            int nr = x + dx[i];
            int nc = y + dy[i];
 
            if (0 > nr || nr >= r || 0 > nc || nc >= c) {
                if (i == 0) nc = 0;
                else if (i == 1) nc = c - 1;
                else if (i == 2) nr = 0;
                else nr = r - 1;
            }
 
            int tmp = dir;
            dir = i;
            dfs(nr, nc);
            dir = tmp;
        }
    }
    else {
        int nr = x + dx[dir];
        int nc = y + dy[dir];
 
        if (0 > nr || nr >= r || 0 > nc || nc >= c) { //우좌하상
            if (dir == 0) nc = 0;
            else if (dir == 1) nc = c - 1;
            else if (dir == 2) nr = 0;
            else nr = r - 1;
        }
 
        dfs(nr, nc);
    }
 
}
 
int main() {
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d %d", &r, &c);
 
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                scanf(" %c", &map[i][j]);
            }
        }
 
        memory = 0;
        dir = 0;
        result = false;
        memset(visited, false, sizeof(visited));
        dfs(0, 0);
 
        if (result) printf("#%d YES\n", test_case);
        else printf("#%d NO\n", test_case);
    }
}