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

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

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

SW Expert Academy

<풀이>

1. 지하터널 지도를 입력받는다.

2. 주어진 시간동안 탈주범이 위치할 수 있는 장소의 개수를 출력한다.

 

<해법>

1. 문제를 해결한 핵심 알고리즘

=> 저는 먼저 문제를 간단히 생각해보았습니다. 터널 구조물이 없다고 생각하면, 단순한 길찾기 문제입니다. 문제가 주어진 시간동안 점차 움직이는 것이므로, DFS보다는 BFS를 선택하는 것이 적합하다고 생각하였습니다. 저는 BFS를 이용하여 해결하였습니다.

 

2. 다른 터널 구조물로 갈 수 있는지 판단하는 방법

=> 다음은 터널 구조물을 처리하는 방법입니다. 현재 내가 있는 터널 구조물을 1번이라고 하고, 그 위에 있는 구조물을 2번이라고 하겠습니다. 1번과 2번끼리 연결되어있는지 알아보려면, (1) 1번 구조물이 위로 갈 수 있어야한다. 와 (2) 2번 구조물은 아래(위와 반대방향)로 갈 수 있어야한다. 입니다. 저는 모든 구조물마다 갈 수 있는 방향을 미리 배열로 저장해 두었습니다. 자세한건 아래 코드의 type배열을 참조하시면 됩니다.

 

#include <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int type[8][4] = {
    {0,0,0,0},
    {1,1,1,1}, //1번 구조물
    {1,0,1,0}, //2번 구조물
    {0,1,0,1}, //...
    {1,1,0,0},
    {0,1,1,0}, 
    {0,0,1,1},
    {1,0,0,1}
};
 
int N, M, R, C, L;
int map[50][50];
bool visited[50][50];
int answer;
 
bool isInner(pos p) {
    if (p.x < 0 || p.y < 0 || p.x >= N || p.y >= M) {
        return false;
    }
    return true;
}
 
bool canConnect(int from, int to, int dir) {
    if (type[from][dir] && type[to][(dir + 2) % 4]) return true;
    return false;
}
 
void solution() {
    queue<pos> q;
    q.push({ R,C });
    visited[R][C] = true;
    while (L && !q.empty()) {
        int qsize = q.size();
        while (qsize--) {
            pos cur = q.front();
            q.pop();
            answer++;
 
            for (int i = 0; i < 4; i++) {
                pos nxt = cur;
                nxt.x += dx[i];
                nxt.y += dy[i];
 
                if (!isInner(nxt) || visited[nxt.x][nxt.y]) continue;
 
                if (canConnect(map[cur.x][cur.y], map[nxt.x][nxt.y], i)) {
                    visited[nxt.x][nxt.y] = true;
                    q.push(nxt);
                }
            }
        }
        L--;
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, M = 0, R = 0, C = 0, L = 0;
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> N >> M >> R >> C >> L;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

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