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

https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AV4yLUiKDUoDFAUx

문제를 읽어보면 상당히 복잡한듯 해보이지만 원리는 간단하다 .

방향으로 진행하다가 특정 조건을 만나면 방향을 변경해준다. 

처음에 visit 배열없이 DFS로 풀려다가 스택 오버플로가 나오길래 BFS로 풀었다. 근데 생각해보니 visit 배열을 통해 x,y, 방향, 메모리값이 중복되는 것을 검사한다면 DFS로도 풀수 있을 듯하다 . 

'?' 가 나왔을때 어떻게 처리할 것인가 생각하는게 이 문제의 키포인트 인듯... 

나는 모든 방향에 대해 검사하는 것으로 처리 하였다 .

코드 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
int T, R, C;
char map[20][20];
int visit[4][15][20][20];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
struct point
{
    int x, y, d, m;
};
bool bfs()
{
    queue <point> q;
    q.push({ 0,0,0,0 });
    while (!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().d;
        int m = q.front().m;
        q.pop();
        if (map[y][x] - '0' >= 0 && map[y][x] - '0' <= 9)
        {
            m = map[y][x] - '0';
        }
        if (map[y][x] == '>')dir = 0;
        else if (map[y][x] == '<')dir = 1;
        else if (map[y][x] == '^')dir = 2;
        else if (map[y][x] == 'v')dir = 3;
        else if (map[y][x] == '+')
        {
            if (m == 15)
            {
                m = 0;
            }
            else
                m++;
        }
        else if (map[y][x] == '-')
        {
            if (m == 0)
            {
                m = 15;
            }
            else
                m--;
        }
        else if (map[y][x] == '_')
        {
            if (m == 0)
            {
                dir = 0;
            }
            else
            {
                dir = 1;
            }
        }
        else if (map[y][x] == '|')
        {
            if (m == 0)
            {
                dir = 3;
            }
            else
            {
                dir = 2;
            }
        }
        else if (map[y][x] == '@')
        {
            return true;
        }
        if (map[y][x] == '?')
        {
            for (int i = 0; i < 4; i++)
            {
                if (visit[i][m][y][x] == 0)
                {
                    visit[i][m][y][x] = 1;
                    int tx = (x + dx[i] + C) % C;
                    int ty = (y + dy[i] + R) % R;
                    q.push({ tx,ty,i,m });
                }
            }
        }
        else
        {
            if (visit[dir][m][y][x] == 0)
            {
                visit[dir][m][y][x] = 1;
                int tx = (x + dx[dir] + C) % C;
                int ty = (y + dy[dir] + R) % R;
                q.push({ tx,ty,dir,m });
            }
        }
    }
    return false;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    for (int testcase = 0; testcase < T; testcase++)
    {
        scanf("%d%d", &R, &C);
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                scanf("%1s", &map[i][j]);
            }
        }
        if (bfs())
        {
            printf("#%d %s\n", testcase + 1, "YES");
        }
        else
        {
            printf("#%d %s\n", testcase + 1, "NO");
        }
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                map[i][j] = 0;
            }
        }
        memset(&visit, 0, sizeof(visit));
    }
}