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

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

문제 링크

 

해결방법

BFS 를 통해 해당 경로를 갈 수 있는지 확인하는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

처음에는 그냥 명령어에 따라 이동만 했는데 프로그램이 종료가 되지않는 큰 문제점이 생겼다

이를 해결하기 위해서 visited 배열이 필요했다

• 단순히 x,y 좌표로만 방문처리를 하면 안됨!
• x좌표, y좌표, 메모리, 방향 을 이용한 4차원 배열로 방문처리를 해줘야한다

 

또한 ? 명령어의 처리가 필요하다

• 문제에서는 무작위로 방향을 선택하라고하지만, 사실 4개의 확률은 동일하기 때문에 4방향 모두 돌려버리면 된다

 

 

소스코드

문제 해결 시간 : 2h

메모리 : 12796 KB

시간 : 45 ms

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

struct node {
    int x,y,mem,dir;
    
    node(){ }
    node(int _x,int _y,int _mem,int _dir) : x(_x),y(_y),mem(_mem),dir(_dir) { }
};

int testcase;
int n,m;
string ans;
char map[21][21];
bool visited[21][21][16][4];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

bool bfs(){
    queue<node> q;
    q.push(node(0,0,0,0));
    visited[0][0][0][0] = true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int mem = q.front().mem;
        int dir = q.front().dir;
        q.pop();
        
        if(map[x][y]>='0' && map[x][y]<='9') mem = map[x][y] - '0';
        else if(map[x][y] == '>') dir = 0;
        else if(map[x][y] == '<') dir = 1;
        else if(map[x][y] == 'v') dir = 2;
        else if(map[x][y] == '^') dir = 3;
        else if(map[x][y] == '+') mem = mem == 15 ? 0 : mem + 1;
        else if(map[x][y] == '-') mem = mem == 0 ? 15 : mem - 1;
        else if(map[x][y] == '_') dir = mem == 0 ? 0 : 1;
        else if(map[x][y] == '|') dir = mem == 0 ? 2 : 3;
        else if(map[x][y] == '@') return true;
        else if(map[x][y] == '?'){
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx == -1) nx = n-1;
                else if(nx == n) nx = 0;
                if(ny == -1) ny = m-1;
                else if(ny == m) ny = 0;
                
                if(!visited[nx][ny][mem][i]){
                    q.push(node(nx,ny,mem,i));
                    visited[nx][ny][mem][i] = true;
                }
            }
        }
        
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if(nx == -1) nx = n-1;
        else if(nx == n) nx = 0;
        if(ny == -1) ny = m-1;
        else if(ny == m) ny = 0;
        
        if(!visited[nx][ny][mem][dir]){
            q.push(node(nx,ny,mem,dir));
            visited[nx][ny][mem][dir] = true;
        }
    }
    
    return false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        cin >> n >> m;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                cin >> map[i][j];
            }
        }
        
        memset(visited, false, sizeof(visited));
        ans = bfs() ? "YES" : "NO";
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}