1953.탈주범 검거

이번에 풀어볼 문제는 SW Expert의 탈주범 검거이다.

SW Expert Academy

이러한 유형의 문제의 난이도는 사람마다 다르겠지만 쉬운 편에 속한다고 생각한다.

그 이유는 문제에서 요구하는 형태들을 정확하게 구현하기만 하면 되기 때문이다.

 

이번 문제에서도 별다른 고민없이 그저 해당 파이프가 주어졌을 때 어떤식으로 움직이게 되는지만

구현하는 것과 DFS만 구현하면 굉장히 쉽게 풀 수 있는 문제이다.

 

구현에서 신경써야할 부분은 그저 어떠한 파이프가 주어졌을 때, 탈주범이 갈 수 있느냐 없느냐만 주의해주면 된다.

=> 단순한 문제이기 때문에 따로 설명은 생략하도록 하겠다. 갈 수 있는지, 없는지에 대한 예외 조건만 신경쓰자!

=> 코드는 중복되는 부분을 줄여서 단순화 할 수 있다. 근데 굳이 필요는 없다고 생각한다.(이건 본인마음대로)

 

 

 

---

 

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <string.h>
#include <deque>
 
#define MAX 51
 
using namespace std;
 
int T, N, M, R, C, L, ans;
 
int map[MAX][MAX];
bool check[MAX][MAX];
 
deque<pair<int, int>>tmp; // DFS를 위한 deque
 
void search(){
    int x, y;
    for (int z = 1; z < L; z++){ // 이미 첫 1초에 맨홀에서 나온것도 시간에 포함이므로 1초부터 시작
        int size = tmp.size(); // 이 부분이 중요! 1초에 얼만큼 가는지 체크하는 변수가 됨
        while (size--){
            x = tmp.front().first;
            y = tmp.front().second;
            tmp.pop_front();
            if (map[x][y] == 1){ // 파이프의 모양에 따라 갈 수 있는 곳과 없는 곳을 구별하는 로직을 구현하면됨( 1 ~ 7 번 형태의 파이프 각각 구현 )
                int dx[4] = { -1, 1, 0, 0 }; 
                int dy[4] = { 0, 0, -1, 1 };
                for (int i = 0; i < 4; i++){
                    int ax = x + dx[i];
                    int ay = y + dy[i];
                    if (ax < 0 || ay < 0 || ax >= N || ay >= M)
                        continue;
 
                    if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 2 || map[ax][ay] == 7 || map[ax][ay] == 6))
                        continue;
 
                    else if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 2 || map[ax][ay] == 4 || map[ax][ay] == 5))
                        continue;
 
                    else if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 4 || map[ax][ay] == 7 || map[ax][ay] == 3))
                        continue;
 
                    else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 5 || map[ax][ay] == 6 || map[ax][ay] == 3))
                        continue;
 
                    if (map[ax][ay] && !check[ax][ay]){ // DFS를 하기위함임
                        ans += 1;
                        check[ax][ay] = true;
                        tmp.push_back(make_pair(ax, ay));
                    }
                }
            }
            else if (map[x][y] == 2){
                int dx[2] = { -1, 1 };
                int dy[2] = { 0, 0 };
                for (int i = 0; i < 2; i++){
                    int ax = x + dx[i];
                    int ay = y + dy[i];
 
                    if (ax < 0 || ay < 0 || ax >= N || ay >= M)
                        continue;
 
                    if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 4 || map[ax][ay] == 7 || map[ax][ay] == 3))
                        continue;
                    else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 5 || map[ax][ay] == 6 || map[ax][ay] == 3))
                        continue;
 
                    if (map[ax][ay] > 0 && !check[ax][ay]){
                        ans += 1;
                        check[ax][ay] = true;
                        tmp.push_back(make_pair(ax, ay));
                    }
                }
            }
            else if (map[x][y] == 3){
                int dx[2] = { 0, 0 };
                int dy[2] = { -1, 1 };
                for (int i = 0; i < 2; i++){
                    int ax = x + dx[i];
                    int ay = y + dy[i];
                    if (ax < 0 || ay < 0 || ax >= N || ay >= M)
                        continue;
 
                    if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 6 || map[ax][ay] == 7 || map[ax][ay] == 2))
                        continue;
                    else if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 4 || map[ax][ay] == 5 || map[ax][ay] == 2))
                        continue;
 
                    if (map[ax][ay] > 0 && !check[ax][ay]){
                        ans += 1;
                        check[ax][ay] = true;
                        tmp.push_back(make_pair(ax, ay));
                    }
                }
            }
            else if (map[x][y] == 4){
                int dx[2] = { -1, 0 };
                int dy[2] = { 0, 1 };
                for (int i = 0; i < 2; i++){
                    int ax = x + dx[i];
                    int ay = y + dy[i];
 
                    if (ax < 0 || ay < 0 || ax >= N || ay >= M)
                        continue;
 
                    if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 4 || map[ax][ay] == 7 || map[ax][ay] == 3))
                        continue;
                    else if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 2 || map[ax][ay] == 4 || map[ax][ay] == 5))
                        continue;
 
                    if (map[ax][ay] > 0 && !check[ax][ay]){
                        ans += 1;
                        check[ax][ay] = true;
                        tmp.push_back(make_pair(ax, ay));
                    }
                }
            }
            else if (map[x][y] == 5){
                int dx[2] = { 1, 0 };
                int dy[2] = { 0, 1 };
                for (int i = 0; i < 2; i++){
                    int ax = x + dx[i];
                    int ay = y + dy[i];
 
                    if (ax < 0 || ay < 0 || ax >= N || ay >= M)
                        continue;
 
                    if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 5 || map[ax][ay] == 2 || map[ax][ay] == 4))
                        continue;
                    else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 5 || map[ax][ay] == 3 || map[ax][ay] == 6))
                        continue;
 
                    if (map[ax][ay] > 0 && !check[ax][ay]){
                        ans += 1;
                        check[ax][ay] = true;
                        tmp.push_back(make_pair(ax, ay));
                    }
                }
            }
            else if (map[x][y] == 6){
                int dx[2] = { 1, 0 };
                int dy[2] = { 0, -1 };
                for (int i = 0; i < 2; i++){
                    int ax = x + dx[i];
                    int ay = y + dy[i];
 
                    if (ax < 0 || ay < 0 || ax >= N || ay >= M)
                        continue;
 
                    if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 2 || map[ax][ay] == 6 || map[ax][ay] == 7))
                        continue;
                    else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 3 || map[ax][ay] == 5 || map[ax][ay] == 6))
                        continue;
 
                    if (map[ax][ay] > 0 && !check[ax][ay]){
                        ans += 1;
                        check[ax][ay] = true;
                        tmp.push_back(make_pair(ax, ay));
                    }
                }
            }
            else if (map[x][y] == 7){
                int dx[2] = { -1, 0 };
                int dy[2] = { 0, -1 };
                for (int i = 0; i < 2; i++){
                    int ax = x + dx[i];
                    int ay = y + dy[i];
                    if (ax < 0 || ay < 0 || ax >= N || ay >= M)
                        continue;
                    if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 7 || map[ax][ay] == 3 || map[ax][ay] == 4))
                        continue;
                    else if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 7 || map[ax][ay] == 6 || map[ax][ay] == 2))
                        continue;
 
                    if (map[ax][ay] > 0 && !check[ax][ay]){
                        ans += 1;
                        check[ax][ay] = true;
                        tmp.push_back(make_pair(ax, ay));
                    }
                }
            }
        }    
    }
}
 
void init(){ // 초기화
    memset(map, 0, sizeof(map))
    memset(check, 0, sizeof(check));
    tmp.clear();
}
 
int main() {
    freopen("1953.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        init();
        cin >> N >> M >> R >> C >> L;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                cin >> map[i][j];
            }
        }
        ans = 1; // 맨홀에서 나온 것부터 탈주범이 있을 수 있는 경우의 수이므로
        check[R][C] = true;
        tmp.push_back(make_pair(R, C));
        search();
        cout << "#" << z << " " << ans << endl;
    }
    return 0;
}