[ SWEA 1824 ] 혁진이의 프로그램 검증 (C++)

SWExpertAcademy의 혁진이의 프로그램 검증 (1824 / D4) 문제이다.

[ 문제풀이 ]

입력으로 주어지는 프로그램이 정지할 수 있는지 구해야 하는 문제이다.

'@' 문자를 만나야지만 프로그램을 정지시킬 수 있다. 그렇다면 우리는 프로그램이 절대 종료되지 않는 한 가지 조건을

확인할 수 있다. 바로 입력으로 주어지는 맵에서 '@' 문자가 없는 프로그램이 주어진다면 해당 프로그램은 절대로 종료되지

않을 것이다. 게다가 문제에서 '@'문자는 무조건 1개 이상 주어진다라는 말도 없기 때문에 '@' 문자의 유무만으로도 정답을

출력할 수 있는 조건을 얻을 수 있게된다.

이 후에는 문제에서 제시한 명령어들에 맞게 좌표를 움직여 주면 된다. 중요한 것은 어떻게 무한루프가 도는 것을 체크하는지이다.

단순히, '방문했던 좌표를 재방문' 하는 것만으로는 무한루프가 돈다고 확신할 수가 없다. 왜냐하면, 중간중간 몇몇 명령어들은

메모리에 저장되어 있는 값 때문에 진행방향이 바뀌고, 메모리에 저장된 값들이 바뀌기 때문에, 같은 좌표를 재방문 하더라도 진행 방향이 다르거나, 메모리에 저장된 값들이 다르다면 이는 똑같은 상태에서의 재방문이 아닐 것이기 때문에 단순히 방문했던 좌표를 재방문 하는 것으로는 프로그램이 종료되지 않는다라고 판단할 수 없다.

따라서, 무한루프를 확인하려면, 위에서 말했던 것 처럼 4가지 상태를 모두 동시에 체크를 해주면 된다.

방문한 좌표 , 방문한 진행방향 , 방문했을 때의 메모리에 저장된 값 ! 이렇게 총 4가지(좌표 = (x, y)) 값을 확인했을 때, 만약

동일한 좌표에, 동일한 진행방향을 가지고 동일한 메모리에 저장된 값으로 재방문을 했다면 이는 프로그램이 종료되지 않는 다는 것이다.

이를 체크하기 위해서 본인은 4차원 배열을 사용해 주었다. Visit[x좌표][y좌표][진행방향][메모리의 값] !

이렇게 4차원 배열을 이용해서 방문 체크를 해 주었다.

구현할 때에는 단 한가지 문자 때문에, 너비우선탐색(BFS)를 이용해서 접근해 보았다. 문제에서 주어진 대부분의 명령어들을 보게 되면 진행방향이나 메모리의 값 등을 구체적으로 바꿔주는 명령어들이기 때문에 너비우선탐색과 같이 '발생할 수 있는 모든 경우의 수를 탐색하는 방법'을 사용하지 않아도 될 것 같지만, '?' 명령어 때문에 BFS탐색을 진행해 주었다.

'?'문자를 만나게 도리 경우, 이동방향을 상하좌우 중 한 방향으로 무작위로 바꾸기 때문에 4가지 방향을 모두 탐색해 보아야 한다.

그래서 이 문자 때문에 BFS탐색을 통해서 프로그램이 종료되는지 판단해 주었다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 25
using namespace std;
 
int N, M;
bool Finish_Mark;
bool Visit[MAX][MAX][4][16];
char MAP[MAX][MAX];
string Answer;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    Finish_Mark = false;
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == '@') Finish_Mark = true;
        }
    }
}
void Solution()
{
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(0, 0), make_pair(0, 0)));
    Visit[0][0][0][0] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Dir = Q.front().second.first;
        int Memory = Q.front().second.second;
        Q.pop();
 
        if (MAP[x][y] == '@')
        {
            Answer = "YES";
            return;
        }
        
        char C = MAP[x][y];
        int nDir, nMemory;
        nDir = Dir;
        nMemory = Memory;
        
        if (C == '<') nDir = 1;
        else if (C == '>') nDir = 0;
        else if (C == '^') nDir = 3;
        else if (C == 'v') nDir = 2;
        else if (C == '_') nDir = Memory == 0 ? 0 : 1;
        else if (C == '|') nDir = Memory == 0 ? 2 : 3;
        else if (C == '+') nMemory = Memory + 1 == 16 ? 0 : Memory + 1;
        else if (C == '-') nMemory = Memory - 1 == -1 ? 15 : Memory - 1;
        else if ('0' <= C && C <= '9') nMemory = C - '0';
 
        if (C == '?')
        {
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx < 0) nx = N - 1;
                else if (nx == N) nx = 0;
                if (ny < 0) ny = M - 1;
                else if (ny == M) ny = 0;
                
                if (Visit[nx][ny][i][nMemory] == false)
                {
                    Visit[nx][ny][i][nMemory] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(i, nMemory)));
                }
            }
        }
        else
        {
            int nx = x + dx[nDir];
            int ny = y + dy[nDir];
 
            if (nx < 0) nx = N - 1;
            else if (nx == N) nx = 0;
            if (ny < 0) ny = M - 1;
            else if (ny == M) ny = 0;
 
            if (Visit[nx][ny][nDir][nMemory] == false)
            {
                Visit[nx][ny][nDir][nMemory] = true;
                Q.push(make_pair(make_pair(nx, ny), make_pair(nDir, nMemory)));
            }
        }
    }
    Answer = "NO";
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}