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

SWExpertAcademy의 탈주범 검거(1953) 문제이다.

[ 문제풀이 ]

1) 본인은 이 문제를 완전탐색 중 너비우선탐색인 BFS를 이용해서 탐색한다면 정답을 도출할 수 있을 거라 생각했다.

   물론, 그러기 위해서는 각 구조물들의 연결관계를 알고 있어야 한다.

   여기서 말하는 연결관계라는 것은 다음과 같은 것들이다. (7개의 터널 구조물들을 보면서 읽으시면 편합니다.)

   1번 모양에서 오른쪽으로 탐색할 때, 오른쪽 방향에 2번 모양이 있으면 갈 수 있는지 ?

   4번 모양에서 위쪽으로 탐색할 때, 위쪽 방향에 6번 모양이 있으면 갈 수 있는지 ?

   이러한 연결관계들이다. 또한, 이러한 연결관계를 알기 위해서는 각 모양들이 갈 수 있는 방향 또한 알고 있어야 한다.

   예를 들면 다음과 같은 것들이다.

   현재 도형이 '2'번 도형인데 왼쪽이나 오른쪽으로 갈 수 있는지 ? 

   현재 도형이 '4'번 도형인데 왼쪽이나 오른쪽으로 갈 수 있는지 ?

   1번 도형 같은 경우 동서남북 모든 방향으로 움직일 수 있다.

   2번 도형 같은 경우 남북으로만, 3번 도형 같은 경우 동서 로만, 4번 도형 같은 경우 동북,

   5번 도형은 동남, 6번 도형은 서남, 7번 도형은 서북 으로만 움직일 수 있다.

   위에서 말한 방향들은, 현재 내가 'x번' 도형일 때, 움직일 수 있는 방향들을 정리한 것이다.

   즉, 탐색을 할 때의 순서가 다음과 같이 계산되어 진다.

   1. 현재 도형에서 특정 방향으로 움직일 수 있는지 ?

   2. 1번 조건에 부합하는 방향이라면, 그 방향으로 움직였을 때 적합한 도형이 있는지 ?

   이렇게 2가지를 탐색해 줘야 한다는 것이다.

   따라서 본인은 위의 조건들을 모두 2개의 배열을 이용해서 표시해 주었다.

  

2) 첫 번째 배열은 bool PipeDir[8][4] 이다.

   PipeDir[a][b] = true의 의미는, 'a번 도형은 b 방향으로 갈 수 있습니다.' 를 의미한다.

   ( 본인 코드 기준 - 0 : 동 / 1 : 서 / 2 : 남 / 3 : 북 )

   1번 도형과 2번 도형만 예를 들어보자면

   PipeDir[1][0] = PiepDir[1][1] = PipeDir[1][2] = PipeDir[1][3] = true 가 된다. 왜냐하면 현재 도형이 '1'번 도형이라면

   모든 방향으로 다 움직일 수 있기 때문이다.

   PipeDir[2][2] = PipeDir[2][3] = true. 2번 도형 같은 경우는 이렇게 2가지 경우만 true가 된다.

   왜냐하면, 현재 도형이 '2'번 도형이라면 남쪽 혹은 북쪽으로만 움직일 수 있기 때문이다.

   먼저 이렇게, '각 도형에서 갈 수 있는 방향'을 체크해주었다.

 

   두 번째 배열은 각 도형간의 연결관계를 나타낸 bool Connect[8][8][4] 이다.

   Connect[a][b][c] = true의 의미는 "a도형에서 b도형으로 c의 방향으로 갈 수 있습니다." 를 의미한다.

   예를 들어서 몇 가지만 보자.

   Connect[1][1][0] = Connect[1][1][1] = Connect[1][1][2] = Connect[1][1][3] = true.

   위의 4가지 경우는 1번 도형에서 1번 도형으로 움직이는 경우를 말한다. 1번 도형에서 1번 도형으로 움직이기 위해서는

   어디에 있던지 상관이 없다. 따라서 4가지 방향 모두 true가 되어진다.

   Connect[1][2][2] = Connect[1][2][3] = Connect[1][3][0] = Connect[1][3][1] = true.

   그럼 이 경우를 생각해보자.

   Connect[1][2][2] = Connect[1][2][3] = true를 보면

   1번 도형에서 2번 도형으로 남쪽 / 북쪽 방향으로 갈 수 있습니다. 를 의미한다.

   2번 도형 같은 경우 세로로 일자인 모양이기 때문에, 1번 도형에서 왼쪽이나 오른쪽으로 움직였을 때 2번 도형이 나온다면

   제대로 탐색되지 않을 것이고, 북쪽이나 남쪽으로 움직였을 때 2번 도형이 나온다면 정상적인 모습이기 때문에 true로 표시

   해 준 것이다. 1번과 3번 도형의 관계 같은 경우는 반대로 동, 서쪽으로 움직였을 때만 움직일 수 있는 경우가 된다.

   이런식으로 본인은 모든 블록들의 연결관계를 미리 세팅해 주고 문제 풀이를 시작했다.

   위의 관계를 설정할 때 머리가 조금 아플 수 있지만, 쉽게하는 방법은(?)

   Connect[a][b][c] 에서, a 도형을 기준으로 동서남북 4곳에 b도형을 붙여 봤을 때 움직일 수 있다면 true, 그게 아니라면

   false로 설정해 주면 된다.

3) 이렇게 세팅을 다 해주었으니 본격적으로 문제를 풀어보자. 본인은 처음에 말했듯이, BFS 탐색을 이용해서 접근해 보았다.

   BFS탐색에서 탐색할 조건은 다음과 같다.

   1. 현재 도형에서 현재 방향으로 탐색할 수 있는지 ?

   2. 현재 도형에서 탐색하려는 도형으로 현재 방향으로 갈 수 있는지 ?

   3. 아직 방문하지 않은 좌표인지 ?

   1번 조건은 위에서 설정한 PipeDir[][] 배열을 통해서 쉽게 확인할 수 있다.

   2번 조건 또한 위에서 설정한 Connect[][][] 배열을 통해서 쉽게 확인할 수 있다.

   3번 조건은 BFS 탐색의 기본조건이다.

   위의 3가지 조건을 계속 탐색해주면 된다. 물론 ! 현재 시간이 'L'초인 경우에는 더 이상 탐색을 하지 않고 그냥 넘어가도록

   구현해 주었다.

글을 쓰면서 더 쉬운 방법이 생각났다. Connect[][][] 배열에서 도형과 도형간의 연결관계를 저렇게 머리 아프게 구현하는

것보다 PipeDir의 역으로 배열을 하나 더 만들어도 더 쉽게 해결이 가능할 것 같다..

PipeDir 배열 같은 경우, 현재 도형에서 특정 방향으로 움직일 수 있는지를 저장해주는 배열이었다면,

현재 방향으로 특정 도형으로 움직일 수 있는지를 저장해주는 배열을 만들어준다면 훨씬 더 간단해 질 것 같다..

예를 들면, Inv_PipeDir[a][b] = true 이런식으로 만들어서, 의미는 "b방향으로 움직였을 때 a도형으로 갈 수 있다" 라는

식으로 해봐도 괜찮을 것 같다..

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, R, C, L, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool PipeDir[8][4];
bool Connect[8][8][4];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Setting()
{
    /* 
    미리 설정하는 단계. 
    PipeDir[a][b] = true - a도형에서 b방향으로 움직일 수 있습니다.
    Connect[a][b][c] = true - a도형에서 b도형으로 c방향으로 움직일 수 있습니다.
    
    이 부분은 모든 TestCase에 대해서 공통적인 부분이기 때문에, 각 테스트케이스 마다 호출되는것이 아닌
    프로그램 시작과 동시에 1번만 호출시키도록 구현해놨음.
    */
    PipeDir[1][0] = PipeDir[1][1] = PipeDir[1][2] = PipeDir[1][3] = true;
    PipeDir[2][2] = PipeDir[2][3] = true;
    PipeDir[3][0] = PipeDir[3][1] = true;
    PipeDir[4][0] = PipeDir[4][3] = true;
    PipeDir[5][0] = PipeDir[5][2] = true;
    PipeDir[6][1] = PipeDir[6][2] = true;
    PipeDir[7][1] = PipeDir[7][3] = true;
 
    Connect[1][1][0] = Connect[1][1][1] = Connect[1][1][2] = Connect[1][1][3] = true;
    Connect[1][2][2] = Connect[1][2][3] = Connect[1][3][0] = Connect[1][3][1] = true;
    Connect[1][4][2] = Connect[1][4][1] = Connect[1][5][1] = Connect[1][5][3] = true;
    Connect[1][6][0] = Connect[1][6][3] = Connect[1][7][2] = Connect[1][7][0] = true;
    Connect[2][1][3] = Connect[2][1][2] = Connect[2][2][2] = Connect[2][2][3] = true;
    Connect[2][4][2] = Connect[2][5][3] = Connect[2][6][3] = Connect[2][7][2] = true;
    Connect[3][1][0] = Connect[3][1][1] = Connect[3][3][0] = Connect[3][3][1] = true;
    Connect[3][4][1] = Connect[3][5][1] = Connect[3][6][0] = Connect[3][7][0] = true;
    Connect[4][1][3] = Connect[4][1][0] = Connect[4][2][3] = Connect[4][3][0] = true;
    Connect[4][5][3] = Connect[4][6][0] = Connect[4][6][3] = Connect[4][7][0] = true;
    Connect[5][1][0] = Connect[5][1][2] = Connect[5][2][2] = Connect[5][3][0] = true;
    Connect[5][4][2] = Connect[5][6][0] = Connect[5][7][0] = Connect[5][7][2] = true;
    Connect[6][1][1] = Connect[6][1][2] = Connect[6][2][2] = Connect[6][3][1] = true;
    Connect[6][4][1] = Connect[6][4][2] = Connect[6][5][1] = Connect[6][7][2] = true;
    Connect[7][1][1] = Connect[7][1][3] = Connect[7][2][3] = Connect[7][3][1] = true;
    Connect[7][4][1] = Connect[7][5][1] = Connect[7][5][3] = Connect[7][6][3] = true;
}
 
void Initialize()
{
    Answer = 0;
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> N >> M >> R >> C >> L;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
 
void Solution()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(R, C), 1));
    Visit[R][C] = true;
    Answer++;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        int Shape = MAP[x][y];
        Q.pop();
 
        if (Cnt == L) continue;
 
        for (int i = 0; i < 4; i++)
        {
            if (PipeDir[Shape][i] == true)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M)
                {
                    if (MAP[nx][ny] == 0) continue;
                    if (Visit[nx][ny] == false)
                    {
                        int nShape = MAP[nx][ny];
                        if (Connect[Shape][nShape][i] == true)
                        {
                            Visit[nx][ny] = true;
                            Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                            Answer++;
                        }
                    }
                }
            }
        }
    }
}
 
void Solve()
{
    Setting();            // 테스트 케이스가 돌기 전에 1번만 실행.
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}