[SWEA] 1953번 탈주범 검거

1953번 탈주범 검거

문제 링크

 

해결방법

BFS 탐색을 통해 방문한 노드의 개수를 파악하는 완전 탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

터널입력 시, 비트연산자로의 변환이 필요하다

4자리 비트로 동 서 남 북 의 이동여부를 저장해야한다

만약 현재위치에서 오른쪽으로 이동이 가능하려면 현재 터널은 오른쪽으로 이동이 가능한 터널이어야 하며, 오른쪽 터널 또한 왼쪽으로 이동이 가능한 터널이어야한다

 

문제의 조건

• N,M ≤ 50
• 소요시간 ≤ 20
• 탈주범은 1시간에 1만큼 이동 가능

 

시간 복잡도

현재 위치에 대해 BFS 탐색을 수행하므로 O(N∗M) 의 시간복잡도를 가진다

 

 

소스코드

문제 해결 시간 : 50m

메모리 : 12656 KB

시간 : 9 ms

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

struct node {
    int x,y,cnt;
    
    node() { }
    node(int _x,int _y,int _cnt) : x(_x),y(_y),cnt(_cnt) { }
};

int testcase;
int n,m,r,c,l,ans,in;
int map[51][51];
int visited[51][51];

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

int getBit(int b){
    if(b==1) return 15;
    else if(b==2) return 12;
    else if(b==3) return 3;
    else if(b==4) return 9;
    else if(b==5) return 5;
    else if(b==6) return 6;
    else if(b==7) return 10;
    else return 0;
}

int changeBit(int b){
    if(b==0) return 1;
    else if(b==1) return 0;
    else if(b==2) return 3;
    else return 2;
}

void bfs(){
    queue<node> q;
    q.push(node(r,c,1));
    visited[r][c] = true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
        
        // 시간이 L 만큼 흘렀을 경우
        if(cnt == l){
            continue;
        }
        
        for(int i=0; i<4; i++){
            // 현재 터널의 모양대로 이동
            if(map[x][y] & (1<<i)){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 맵 밖을 벗어났다면
                if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
                
                // 터널이 연결되었는지 확인
                if(map[nx][ny] & (1<<changeBit(i))){
                    if(!visited[nx][ny]){
                        q.push(node(nx,ny,cnt+1));
                        visited[nx][ny] = true;
                        ans++;
                    }
                }
            }
        }
    }
}

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 >> r >> c >> l;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                cin >> in;
                
                // 비트 연산자를 위해 변형된 비트를 삽입
                map[i][j] = getBit(in);
            }
        }
        
        memset(visited, false, sizeof(visited));
        ans = 1;
        
        bfs();
        
        cout << "#" << t << " " << ans << "\n";
    }
    
    return 0;
}