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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE

SW Expert Academy

 

최종 코드

• GitHub github.com/hwayeon351/SWEA-Algorithms

hwayeon351/SWEA-Algorithms

//
//  main.cpp
//  SWEA1953
//
//  Created by Hwayeon on 2021/01/15.
//
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>

using namespace std;

int N, M, L, R, C;
int map[50][50] = {0, };
int num_loc = 0;
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, -1, 0, 1};
vector< vector<int> > ternal = {{0}, {1, 2, 3, 4}, {2, 4}, {1, 3}, {2, 3}, {3, 4}, {1, 4}, {1, 2}};

void find_loc(){
    bool visit[50][50] = {false, };
    queue<queue<pair<int, int>>> time_q;
    queue<pair<int, int>> hole;
    hole.push(make_pair(R, C));
    time_q.push(hole);
    int time = 1;
    visit[R][C] = true;
    while(time < L && time_q.empty() == false){
        queue<pair<int, int>> now_q = time_q.front();
        time_q.pop();
        queue<pair<int, int>> in_q;
        while(now_q.empty()==false){
            int x = now_q.front().second;
            int y = now_q.front().first;
            now_q.pop();
            int type = map[y][x];
            for(int i=0; i<ternal[type].size(); i++){
                int new_y = y + dy[ternal[type][i]];
                int new_x = x + dx[ternal[type][i]];
                int new_type = map[new_y][new_x];
                if(new_type == 0) continue;
                for(int j=0; j<ternal[new_type].size(); j++){
                    if(abs(ternal[new_type][j]-ternal[type][i]) == 2){
                        if(visit[new_y][new_x]==true) continue;
                        in_q.push(make_pair(new_y, new_x));
                        visit[new_y][new_x] = true;
                    }
                }
            }
        }
        time_q.push(in_q);
        time++;
    }
    for(int i=0; i<N; i++){
       for(int j=0; j<M; j++){
            if(visit[i][j] == true) num_loc++;
        }
    }
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        num_loc = 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];
            }
        }
        find_loc();
        cout << "#" << test_case << " " << num_loc << endl;
    }
    return 0;
}

 

---

풀이 과정

풀이 시간  1시간 40분

1. 터널 구조물 타입 표현하기

int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, -1, 0, 1};
vector< vector<int> > ternal = {{0}, {1, 2, 3, 4}, {2, 4}, {1, 3}, {2, 3}, {3, 4}, {1, 4}, {1, 2}};

 먼저, dx와 dy는 0:그대로, 1:좌, 2:상, 3:우, 4:하로 방향을 나타냈다.

그 후, 터널 구조물 타입마다의 기능을 vector ternal에 담아주었다. 이때 터널 구조물이 1~7까지 임을 고려해서 ternal[0]에는 임의로 0을 넣어주었다. 이렇게 설계한 이유는 터널의 타입을 살펴보면, 갈 수 있는 곳은 (현재 터널의 타입의 이동 인덱스 - 다음 터널의 타입의 이동 인덱스)의 절댓값이 2인 경우 지나갈 수 있다는 규칙을 찾았기 때문이다.

예를 들면, 왼쪽 그림처럼 왼쪽의 터널의 타입은 3, 오른쪽 터널의 타입은 1이다. ternal[3] = {1, 3}으로 좌, 우로 이동할 수 있고, ternal[1] = {1, 2, 3, 4}로 상, 하, 좌, 우 모두 이동 가능하다. 이때, 터널과 터널 사이를 이동해보자.

왼쪽 터널 입장에서는 우로 이동하는 것이고, 오른쪽 터널 입장에서는 좌로 이동한다. 현재 왼쪽 터널에 있고 그 위치가 x, y이면, ternal[3]의 3을 통해 x = x+dx[3], y = y+dy[3]을 하여 우로 한 칸 이동한 오른쪽 터널에 갈 수 있다. 오른쪽 터널에서 왼쪽 터널로 이동하기 위해서는 ternal[1]의 1을 통해 x = x+dx[1], y = y+dy[1]을하여 좌로 한 칸 이동해 왼쪽 터널로 갈 수 있다. 여기서 두 터널 타입에서 1과 3의 차는 2인 것을 확인 할 수 있다.

다른 터널 타입 간의 이동도 이렇게 abs(ternal[type1][i] - ternal[type2][j]) = 2 이면 가능한 것을 확인 할 수 있다.

 

 

2. 갈 수 있는 위치 찾기 find_loc()

 나는 특정 위치의 터널 타입에 따라 최대 4방향을 움직일 수 있고, 그렇게 영역을 넓혀가며 최대로 갈 수 있는 영역을 구한다는 점에서 BFS를 활용했다.

void find_loc(){
    bool visit[50][50] = {false, };
    queue<queue<pair<int, int>>> time_q;
    queue<pair<int, int>> hole;
    hole.push(make_pair(R, C));
    time_q.push(hole);
    int time = 1;
    visit[R][C] = true;
    while(time < L && time_q.empty() == false){
        queue<pair<int, int>> now_q = time_q.front();
        time_q.pop();
        queue<pair<int, int>> in_q;
        while(now_q.empty()==false){
            int x = now_q.front().second;
            int y = now_q.front().first;
            now_q.pop();
            int type = map[y][x];
            for(int i=0; i<ternal[type].size(); i++){
                int new_y = y + dy[ternal[type][i]];
                int new_x = x + dx[ternal[type][i]];
                int new_type = map[new_y][new_x];
                if(new_type == 0) continue;
                for(int j=0; j<ternal[new_type].size(); j++){
                    if(abs(ternal[new_type][j]-ternal[type][i]) == 2){
                        if(visit[new_y][new_x]==true) continue;
                        in_q.push(make_pair(new_y, new_x));
                        visit[new_y][new_x] = true;
                    }
                }
            }
        }
        time_q.push(in_q);
        time++;
    }
    for(int i=0; i<N; i++){
       for(int j=0; j<M; j++){
            if(visit[i][j] == true) num_loc++;
        }
    }
}

 

탐색을 시작하기 전에 중요하게 설정해야 할 것이 있다.

    bool visit[50][50] = {false, };
    queue<queue<pair<int, int>>> time_q;
    queue<pair<int, int>> hole;
    hole.push(make_pair(R, C));
    time_q.push(hole);
    int time = 1;
    visit[R][C] = true;

•  visit 배열 만들기 

 처음에 나는 visit을 체크하지 않고 풀어서 테스트케이스 5번이 시간 초과가 났다. 원인은 방문한 곳을 다시 또 탐색하기 때문에 돌고 돌았기 때문이다. 따라서 이를 방지하기 위해 visit[new_y][new_x] == false인 곳만 큐에 담도록 한다.

 

• 2중 Queue time_q 만들기

 문제에서 탈출 소요 시간 L이 주어지고, 시간이 소요됨에 따라 탈주범이 있을 수 있는 위치의 개수를 계산해야하기 때문에, 1시간마다 따라 넓혀갈 영역들이 큐에 담겨야 한다. 따라서 queue<queue<pair<int, int>>> time_q를 선언한다.

 위 그림을 참고하면 시간에 따라 탐색해야하는 위치들을 담기 위해 time_q가 필요한 것을 알 수 있다.

또한, 하나의 time_q요소는 위치를 (y, x) 형태로 저장한다.

 

 

• 맨홀뚜껑 위치 time_q에 담기, time = 1 초기화

 탐색은 맨홀뚜껑 위치에서 부터 시작되기 때문에 맨홀뚜껑의 위치가 탈주 1시간 후의 위치이다. 따라서 BFS 탐색 전에 맨홀 뚜껑의 위치를 time_q에 담아주고 visit[R][C] = true 해준다. 또한, 맨홀뚜껑을 방문했으니 time = 1로 초기화 해준다.

 

 

• BFS 탐색

   while(time < L && time_q.empty() == false){
        queue<pair<int, int>> now_q = time_q.front();
        time_q.pop();
        queue<pair<int, int>> in_q;
        while(now_q.empty()==false){
            int x = now_q.front().second;
            int y = now_q.front().first;
            now_q.pop();
            int type = map[y][x];
            for(int i=0; i<ternal[type].size(); i++){
                int new_y = y + dy[ternal[type][i]];
                int new_x = x + dx[ternal[type][i]];
                int new_type = map[new_y][new_x];
                if(new_type == 0) continue;
                for(int j=0; j<ternal[new_type].size(); j++){
                    if(abs(ternal[new_type][j]-ternal[type][i]) == 2){
                        if(visit[new_y][new_x]==true) continue;
                        in_q.push(make_pair(new_y, new_x));
                        visit[new_y][new_x] = true;
                    }
                }
            }
        }
        time_q.push(in_q);
        time++;
    }

탐색은 time < L이고 더 탐색할 위치가 있으면 이루어진다.

• 현재 시간에 탐색해야할 위치들을 담은 time_q.front()를 now_q에 담아주고, time_q.pop() 해준다.
• 한 시간 뒤에 탐색해야할 위치들을 담을 in_q를 생성한다.
• now_q에 담긴 위치들을 탐색한다.

       1) now_q의 front에 담긴 위치를 x, y에 담아주고, now_q.pop() 해준다.

       2) 현재 x, y의 터널 타입을 type에 담아준다.

       3) ternal[type]의 크기만큼 반복하여 현재 터널을 통해 이동한 위치를 new_y, new_x에 담아준다.

           [1] 이동한 위치가 0인 경우에는 이동할 수 없음을 의미하기 때문에, continue하여 다른 방향으로. 이동한다.

           [2] 이동한 위치가 0이 아닌 경우, 이동한 위치의 터널 타입을 new_type에 담아주고, [3]을 진행한다.

           [3] 이동한 위치의 터널 타입에 담긴 방향 인덱스 ternal[new_type][j]와 현재 터널 타입의 방향 인덱스 ternal[type][i]의 차 2인 경우가 있다면 터널 사이를 이동할 수 있음을 의미하므로 [4]를 진행한다. 차가 2인 경우가 없다면, 터널이 이어져 있지 않아 이동할 수 없음을 의미한다.

           [4] in_q에 new_y, new_x를 push 해 1시간 뒤 탐색이 이뤄지도록하고, visit[new_y][new_x] = true 해준다.

       4) now_q의 위치들을 모두 탐색하면. time_q.push(in_q)와 time++를 해준다.

 

 

• 탈주범이 위치할 수 있는 장소의 개수 세기

    for(int i=0; i<N; i++){
       for(int j=0; j<M; j++){
            if(visit[i][j] == true) num_loc++;
        }
    }

탐색이 모두 끝나면 visit[i][j] = true인 위치를 카운팅 해 탈주범이 위치할 수 있는 장소의 개수를 센다.

 

 

 

---

참고

• 2021/01/11 - [C++] - [알고리즘] BFS와 DFS

[알고리즘] BFS와 DFS