[C++] SWEA 1953 - 탈주범 검거

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

<풀이>

1. 시작점부터 시간 안에 갈 수 있는 곳을 탐색한다.

2. 갈 수 있는 곳의 개수를 세어 출력한다.

​

<해법>

1. 7가지 지하터널 표기 방법

=> 맵 입력을 받을 때, 있는 그대로의 숫자를 받는 대신 그 숫자가 가진 의미를 맵에 저장합니다.

 

2. 그 시간대에 갈 수 있는 모든 곳 탐색 방법

=> 그 시간대에 큐의 사이즈를 저장한 후 그 사이즈만큼 반복문을 돌려줍니다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct tunnel {
    //좌표
    int x, y;
};
 
const int MAX = 50;
 
//북,동,남,서
//연결가능 = 1, 연결불가능 = 0
int shape[8][4] ={ 
    {0,0,0,0},
    {1,1,1,1},    //1번 모양 => 북,동,남,서 방향 연결가능
    {1,0,1,0},    //2번 모양 => 북,남 방향 연결가능
    {0,1,0,1},    //3번 모양 => 동,서 방향 연결가능
    {1,1,0,0},
    {0,1,1,0},
    {0,0,1,1},
    {1,0,0,1} 
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N, M, R, C, L;
int map[MAX][MAX][4];
bool visited[MAX][MAX];
int res;
 
void bfs(tunnel start) {
    //처음 흉악범 탈출 지점 -> 1시간 후
    queue<tunnel> q;
    q.push(start);
    visited[start.x][start.y] = true;
    L--;
    res++;
 
    //시간이 종료될 때 까지
    while (L--) {
        //그 시간대에 갈 수 있는 모든 곳 탐색
        int qsize = q.size();
        for (int i = 0; i < qsize; i++) {
            tunnel cur = q.front();
            q.pop();
 
            for (int j = 0; j < 4; j++) {
                tunnel nxt = cur;
                nxt.x += di[j];
                nxt.y += dj[j];
 
                //범위를 벗어났을 경우 continue
                if (nxt.x < 0 || nxt.y < 0 || nxt.x >= N || nxt.y >= M) {
                    continue;
                }
                
                //1. 현재 터널에서 가는 방향으로 뚫려있고,
                //2. 다음 터널에서 오는 방향으로 뚫려있고,
                //3. 이전에 방문했던 적이 없는 경우
                if (map[cur.x][cur.y][j] == 1 && map[nxt.x][nxt.y][(j + 2) % 4] && !visited[nxt.x][nxt.y]) {
                    visited[nxt.x][nxt.y] = true;
                    q.push(nxt);
                    res++;
                }            
            }
        }
    }
    return;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
        
        //입력
        cin >> N >> M >> R >> C >> L;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //맵 입력을 받을 때, 그 곳에서 가능한 방향도 같이 저장
                int tmp;
                cin >> tmp;
                for (int k = 0; k < 4; k++) {
                    map[i][j][k] = shape[tmp][k];
                }
            }
        }
 
        //사용할 메모리 초기화
        memset(visited, false, sizeof(visited));
        res = 0;
        tunnel start = { R,C };
 
        //탐색 시작
        bfs(start);
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
}

 

구현과 BFS에 대해 알아볼 수 있는 문제였습니다.