[SWEA_모의SW역량테스트] 1953번 - 탈주범 검거

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq#;return%20false;

SW Expert Academy

SWEA 삼성 SW 모의 역량테스트 문제다.

전형적인 BFS 문제로, 갈 수 있는 길을 가고, 가지 않은 길을 가면서 탈주범이 최대 갈 수 있는 지역의 수를 구하는 문제다.

 

Map을 단순히 숫자로 표현하기보다는 상하좌우 접근가능한 정보를 저장하는 것이 구현하기 용이하여 구조체 Open을 사용하였으며, 4방위 탐색을 BFS에서 활용할 때 가장 기본이 되는 dir 구조체를 선언해 활용했다.

 

그리고 단계별 탐색이 되어야하는 BFS 문제이기 때문에, 루프를 돌 때마다 큐의 크기만큼만 반복문을 돌고 time을 증가시킨 뒤, L과 비교해 무한루프를 빠져나왔다.

 

L이 1일경우, 맨홀 입구아래 부분만 있을 수 있으므로 답을 1로 하여 출력하도록 하였다.

 

아래는 소스코드.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int T, N, M, R, C, L;
typedef struct Open{
    bool up = false;
    bool down = false;
    bool left = false;
    bool right = false;
}Open;
 
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
vector<vector<bool> > check;
vector<vector<Open> > Map;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> T;
    for (int tc = 1; tc <= T; tc++){
        cin >> N >> M >> R >> C >> L;
        // L = 1일 때 맨홀 뚜껑 위치이며 지점 한 개에 있을 수 있는 것.
        Open tmp;
        Map.assign(N, vector<Open>(M, tmp));
        check.assign(N, vector<bool>(M, false));
        for (int r = 0; r < N; r++){
            for (int c = 0; c < M; c++){
                int ele;
                cin >> ele;
                if (ele > 0){
                    switch (ele){
                    case 1: // 상하좌우
                        Map[r][c].up = true;
                        Map[r][c].down = true;
                        Map[r][c].left = true;
                        Map[r][c].right = true;
                        break;
                    case 2: // 상하
                        Map[r][c].up = true;
                        Map[r][c].down = true;
                        break;
                    case 3: // 좌우
                        Map[r][c].left = true;
                        Map[r][c].right = true;
                        break;
                    case 4: // 상우
                        Map[r][c].up = true;
                        Map[r][c].right = true;
                        break;
                    case 5: // 하우
                        Map[r][c].down = true;
                        Map[r][c].right = true;
                        break;
                    case 6: // 좌하
                        Map[r][c].left = true;
                        Map[r][c].down = true;
                        break;
                    case 7: // 좌상
                        Map[r][c].left = true;
                        Map[r][c].up = true;
                        break;
                    }
                }
            }
        }
        int answer = 1;
        int time = 1;
        queue<pair<int, int> > q;
        q.push(make_pair(R, C));
        check[R][C] = true;
        int level;
        while (1){
            if (L == 1) break;
            int cnt = q.size();
            for (int k = 0; k < cnt; k++){
                pair<int, int> curPos = q.front();
                q.pop();
                int curR = curPos.first;
                int curC = curPos.second;
                for (int i = 0; i < 4; i++){ // 동 서 남 북
                    int nR = curR + direction[i].dr;
                    int nC = curC + direction[i].dc;
                    if (0 <= nR && nR < N && 0 <= nC && nC < M){
                        if (i == 0){
                            if (Map[curR][curC].right && Map[nR][nC].left && !check[nR][nC]){
                                check[nR][nC] = true;
                                answer++;
                                q.push(make_pair(nR, nC));
                            }
                        }
                        else if (i == 1){
                            if (Map[curR][curC].left && Map[nR][nC].right && !check[nR][nC]){
                                check[nR][nC] = true;
                                answer++;
                                q.push(make_pair(nR, nC));
                            }
                        }
                        else if (i == 2){
                            if (Map[curR][curC].down && Map[nR][nC].up && !check[nR][nC]){
                                check[nR][nC] = true;
                                answer++;
                                q.push(make_pair(nR, nC));
                            }
                        }
                        else if (i == 3){
                            if (Map[curR][curC].up && Map[nR][nC].down && !check[nR][nC]){
                                check[nR][nC] = true;
                                answer++;
                                q.push(make_pair(nR, nC));
                            }
                        }
                    }
                }
            }
            time++;
            if (time == L) break;
        }        
        cout << "#" << tc << " " << answer << '\n';
        Map.clear();
        check.clear();
    }
    return 0;
}