(C++) 1953. [모의 SW 역량테스트] 탈주범 검거

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

문제 자체는 어렵지 않다. BFS 로 풀면 됨.
– 시작 위치 (맨홀 위치)부터 queue에 넣으면 됨. (시간 정보도 필요)
– queue에서 하나씩 dequeue하면서 좌우상하 위치로 도달 가능한지 (+방문한 적이 없는가) 체크하면서 도달 가능하면 visited mark하고 시간 1 추가해서 enqueue 
(dequeue할 때마다 도달가능한 곳 카운트 1씩 증가)
– 단, enqueue할 때 시간이 넘어간 경우 enqueue하지 않음
– queue에서 나온 후,   도달가능한 곳 카운트 해놓은 것 출력

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    //freopen("input.txt", "r", stdin);

    int T = 0;
    cin >> T;

    int map[50][50] = {0};
    int visited[50][50] = {0};
    int queueR[50*50] = {0};
    int queueC[50*50] = {0};
    int queueT[50*50] = {0};

    for (int test_case = 1; test_case <= T; test_case++) {
        int numN = 0, numM = 0, numR = 0, numC = 0, numL = 0;
        cin >> numN >> numM; // map size (row: N, column: M)
        cin >> numR >> numC; // loc of manhole (R, C)
        cin >> numL; // time elapsed after escape

        // add pipe information
        int numArrived = 0;
        for (int r = 0; r < numN; r++) 
            for (int c = 0; c < numM; c++) 
                cin >> map[r];

        for (int r = 0; r < numN; r++) 
            for (int c = 0; c < numM; c++) 
                visited[r] = 0;
        
        int queueFront = -1;
        int queueRear = -1;

        // first enqueue starting point
        if (queueFront == -1)
            queueFront = 0;

        queueRear++;
        queueR[queueRear] = numR;
        queueC[queueRear] = numC;
        queueT[queueRear] = 1;
        visited[numR][numC] = 1;

        // while the queue is not empty
        while (queueFront != -1 &amp;&amp; queueFront <= queueRear) {
            // dequeue
            int myRow = queueR[queueFront];
            int myColumn = queueC[queueFront];
            int myTime = queueT[queueFront];
            queueFront++;

            //cout << myRow << '/' << myColumn << ' ' << myTime << '\n';
            numArrived++;

            // left, right, up, down
            int rowPair[4] = {0, 0, -1, 1};
            int columnPair[4] = {-1, 1, 0, 0};

            for (int i = 0; i < 4; i++) {
                int newRow = myRow + rowPair[i];
                int newColumn = myColumn + columnPair[i];

                // out of array, don't go further
                if (newRow < 0 || newRow > numN - 1 || newColumn < 0 || newColumn > numM - 1)
                    continue;

                // already visited, don't need to check more than once
                if (visited[newRow][newColumn] == 1)
                    continue;

                // can't go beyond time limit 
                if (myTime == numL)
                    continue;

                switch (i) {
                    case 0: // left
                        // current place: can go to left
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 3 || map[myRow][myColumn] == 6 || map[myRow][myColumn] == 7) {
                            // next place: can arrived from right
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 3 || map[newRow][newColumn] == 4 || map[newRow][newColumn] == 5) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 1: // right
                        // current place: can go to right
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 3 || map[myRow][myColumn] == 4 || map[myRow][myColumn] == 5) {
                            // next place: can arrived from left
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 3 || map[newRow][newColumn] == 6 || map[newRow][newColumn] == 7) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 2: // up
                        // current place: can go to up
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 2 || map[myRow][myColumn] == 4 || map[myRow][myColumn] == 7) {
                            // next place: can arrived from down
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 2 || map[newRow][newColumn] == 5 || map[newRow][newColumn] == 6) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 3: // down
                        // current place: can go to down
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 2 || map[myRow][myColumn] == 5 || map[myRow][myColumn] == 6) {
                            // next place: can arrived from up
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 2 || map[newRow][newColumn] == 4 || map[newRow][newColumn] == 7) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                }
            }
        }

        cout << '#' << test_case << ' ' << numArrived << '\n';
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.