[ 백준 5213 ] 과외맨 (C++)

백준의 과외맨(5213) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 문제가 일단 굉장히 길고 쓸모 없는 말이 많다. 문제를 간략하게 설명해보자면, 대충 딱 봤을 때는 맵과 맵 한칸한칸의

  숫자들을 입력받는 것 처럼 보인다. 근데 짝수행의 경우에는 제일 첫자리와 제일 마지막 자리 2자리가 비도록 입력을

  받는다. 구체적으로 보자면, 이 문제에서 맵은 한칸한칸의 개념이 아닌, 2개의 칸이 붙어있는 하나의 타일로 관리를

  한다. 즉, N = 5인 경우에는, 10개의 숫자를 입력받지만, 사실상 5개의 타일에 있는 숫자들을 입력받는 것이다.

  그리고 짝수행에서는 4개의 타일에 있는 숫자들만 입력을 받게 된다. 또한 타일의 번호도 주어진다. 가장 왼쪽 위에있는

  타일부터 1번부터 쭉 나아가는식으로...

- 본격적인 문제는 제일 시작점인 타일(제일 왼쪽 위) 에서 가장 마지막 타일로 몇 개의 타일을 거쳐서 갈 수 있는지,

  그리고 그 거쳐서 간 타일의 번호를 출력하는 것이 문제이다.

-  타일도 위의 그림과 같이 연결될 수 있는 타일이 있고 될 수 없는 타일이 있다. 같은 변을 공유하면서 같은 값을 가지는

   타일만 연결된 것이다. (빨강색으로 표시된 놈들만 연결되어 있는 상태)

[ 문제풀이 ]

1. 일단 입력을 받기 전에, 나는 이 문제를 일반 int형 MAP이 아닌, 구조체 2차원 배열을 만들었다. 하나의 타일당

   Left, Right, Tile_Number 이 3개의 변수를 가지는 구조체를 하나 만들었으며, 이 구조체를 자료형으로 2차원 배열을

   만들었다.

2. 입력을 받을 때는 짝수행과 홀수행의 갯수를 달리해서 받아야 하기 때문에, 또다른 변수 하나를 만들어서 홀수행에 대해서는

   1의 값을 가지고, 짝수행에 대해서는 0의 값을 가지는 변수를 만들어서 입력 받을 때 ++하게 해주었다.(변수 EvenOrOdd)

   - 기본적으로 N-1개만큼 입력을 받게 해놓고, 홀수행에 대해서는 1의 값을 가지는 변수이므로 +1 하면 결국 N개를, 짝수행

     에 대해서는 0의 값을 가지는 변수이므로 +0을 하면 결국 N-1개를 받을 수 있도록 !

   - 이렇게 되면 입력이 이상하게 될 것이다. 위의 그림처럼 입력을 받는 것이 아닌, 다 왼쪽정렬 시키고 짝수행들은

     가장 마지막 2칸이 비는 형식으로 입력을 받게 될 것이다. 본인은 이렇게 입력을 받은 후에 문제를 풀었고, 연결하는 과정

     에서 모두 고려해주었다.

   그리고 입력 받을 때 그 좌표의 Left값과 Right값 2개를 입력받아야 한다 ! 동시에 타일의 Number도 설정해 주었다.

3. 이 문제에서 가장 골칫덩어리인 부분이다. 바로 타일을 연결하는 부분이다. 솔직히 타일을 연결하고 나서 BFS로 끝점까지

   가는 것은 쉬울 거라 생각했고, 타일을 연결하는 것이 굉장히 어려웠다.

   먼저 모든 타일이 연결될 수 있는 규칙이 똑같지가 않다. 이것도 짝수행과 홀수행이 연결될 수 있는 타일이 다르다.

   3-1) 먼저 홀수행에 대해서 확인해보자.

       3번째 줄에 2 4 5 1 6 1 1 6 2 3 있는 행에서, (5 , 1) 을 값으로 갖는 타일에 주목해보자. 모든 타일의 모든 숫자가

       동일하다고 가정했을 때, (5 , 1) 이 타일은 위의 (4 , 2), (5 , 6) 양쪽에 (2 , 4), (6 , 1) 아래쪽에 (4 , 2) , (5 , 3)

       이렇게 6방향으로 연결이 가능하다.

       이 6방향을 우리가 입력받은 맵의 형태에서 표시를 해보면 다음과 같다

     

   3-2) 그럼 짝수행은 어떻게 될까?

       2번째 줄에 4 2 5 6 4 4 6 5 에서 ( 5, 6)을 값으로 갖는 타일에 주목해보자. 모든 타일의 모든 숫자가 동일하다고

      가정했을 때, (5 , 6)의 타일은 위의 (4 , 5) , (3 , 4), 양쪽에 (4 , 2), (4 , 4) 아래쪽에 (5 , 1), (6 , 1) 이렇게

       6방향으로 연결이 가능하다.

       이 6방향을 우리가 입력 받은 맵의 형태에서 표시를 해보면 다음과 같다

      

       보면 홀수행과 짝수행이 모든 숫자가 같다고 가정했을 때, 연결되는 방향을 보면 서로 다르다는 것을 알 수 있다

       그렇다면 한 점을 기준으로 8방향을 이렇게 생각해보자.

      여기서 숫자는 방향을 말하는 것이다.

       홀수행의 경우 0, 1, 3, 5, 6, 7 번 이렇게 6방향으로 연결이 가능하고, 짝수행의 경우 1, 2, 3, 4, 5, 7 번 이렇게

      6방향으로 연결이 가능하다.

      그렇다면 이 부분을 코딩으로 어떻게 구현해야 할까? 먼저 나는 기준점을 기준으로 움직일 수 있는 방향을 8방향으로

       설정해주었고, 실제로도 0번일때 좌측위로, 1번일때 위로, 2번일 때 우측위로 가도록 값을 설정해 주었다.

       여기서 값을 설정해주었다는 것은 dx[] 와 dy[]의 순서를 저렇게 설정해 주었다는 의미이다.

  3-3) 그럼 이제 dx[], dy[]의 값도 설정해 주었고, 실제로 연결을 한번 시켜보자. 먼저 나는 연결을 관리하는 bool형 3차원

      배열을 하나 사용하였다. Connect[][][8]인데, 마지막 [8]의 의미는 8방향 중 연결되 있는 방향으로는 true의 값을

      갖도록 설정해주었다.

      물론 우리는 위에서 홀수행, 짝수행의 경우 몇 번 방향으로 연결이 가능한지 알아놓았고, 이제는 값을 비교만 하면 된다.

      여기서 또 주의해야할 것이 값 비교인데, 값이 똑같을 때만 연결이 가능하다. 이 값은 맵을 잘 보면서 내가 연결될 수 있

      는 방향에서 타일 중 어느 값과 비교해야할지 보면서 설정해 주면 된다.

      조금 더 이해를 돕자면 위에서 말한 홀수행 예시를 다시한번 생각해보면 (5, 6)은 위의 (4, 5)와 연결이 가능한데, 이 떄

      (4, 5)의 값을 갖는 타일의 Right 값과, (5, 6)의 값을 갖는 타일의 Left값이 같아야만 연결이 가능하다. 이러한 조건은

      밑에 코드를 참조하여도 좋고, 스스로 생각하면서 하면 어려운 부분이 아닐 것이다.

      (연결하는 부분 : 함수 Set_Tile_Connecting() 참고)

4. 이제 연결다 했으니 BFS만 돌려주면 된다. 사실 어려운 작업은 모두 끝났다. BFS에서는 특별한 조건 없이 연결이 되어 있으

   면 Queue에 계속 넣어 주는 방식으로만 구현하면 된다.

   4-1) 문제에서 이러한 조건이 있다. 가장 마지막 타일로 가지 못하는 경우라면, 타일의 번호가 가장 큰 곳으로 가는 걸로

        답을 도출해내라는 식의 말이 있다. 이 부분은 걱정하지 않아도 되는게, 어차피 BFS를 구현하게 되면, 자연스럽게

        가장 마지막 부분까지 갈 것이고, 마지막 부분까지 갈 수 없다 하더라도 자연스럽게 마지막 부분을 제외한 타일의 번호

        가 가장 큰 타일까지 움직일 것이다. 그래서 이부분에 대한 별다른 조건을 생각하지 않아도 된다. 단지, BFS안에서

        타일의 Number를 계속 받아오면서 타일의 Number가 더 큰놈이 Queue에 들어오면 Tile Max값을 계속해서 갱신시켜

        주면서 그 값을 저장해주는 변수만 있으면 된다.

5. 마지막 관문이다. 경로를 출력해야 한다. 어떻게 출력해야할까? 나는 이 부분을 위해서 Path[]라는 1차원 배열을 사용했다.

   Path[a] = b의 의미는 "a번은 b번에서부터 왔다" 이다. 예를들어서, 1번타일이 6번 타일과 연결되어서 6번으로 갔다고

   생각해보자. 그럼 Path[6] = 1이 된다. BFS에서 이 부분에 대한 구현만 추가해주면 된다. 어렵지 않은 부분이니 코드를 보면

   금방 이해가 갈 것이다.

6. 이제 모든 것이 다 끝났다. 그럼 지금까지 위에서 우리가 무얼했는지 , 이제 무엇을 해야하는지 정리해보자.

   지금까지 맵을 입력받고, 타일을 연결하였고, 연결된 타일을 타고 움직이고 움직여서 가장 마지막 타일 혹은 가장 큰번호의

   타일까지 왔고(가장 큰 번호의 타일은 위에서 말한 Tile_Max라는 변수에 저장되어 있을 것이고) 경로도 다 저장해 두었다.

   이제 우리는 그 경로를 출력하기만 하면 된다.

   문제의 예제출력1을 한번 보자. 경로가 1 2 7 12 ... 22 23 으로 되어있다.

   그럼 우리는 지금 어떻게 되어있을까? Path[2] = 1 , Path[7] = 2, Path[12] = 7 ... Path[23] = 22 이런식으로 저장이 되어 있

   을 것이다. 이 부분을 출력시키기 위해서 나는 Vector를 하나 사용했다.

   가장 먼저 Vector에 Max_Tile을 집어넣었다. 그렇다면 현재 Vector에는 23이라는 값이 들어가 있을 것이다.

   그리고 Path[a] 의 값이 0이 될 때까지(Path[1] = 0) 반복하면서 Vector에 값을 넣어주기만 하면 된다.

   push_back(Path[Max_Tile]) -> Max_Tile = Path[Max_Tile] 이 구문이 반복되는 반복문만 잘 구현한다면 Vector에 값이

   잘 들어갈 것이다. 지금 보면 Vector에 값을 역순으로 넣어놨다. 아마 23 22 ... 7 2 1 이렇게 들어가 있을 것이니

   벡터를 역순으로 출력만 해주면 경로 출력도 완성된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 550
using namespace std;
 
typedef struct
{
    int Left;
    int Right;
    int Num;
}TILE;
 
int N, Max_Tile, Last_Tile;
TILE MAP[MAX][MAX];
bool Connect[MAX][MAX][8];
bool Visit[MAX][MAX];
int Path[MAX * MAX];
 
int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Max_Tile = 0;
    memset(MAP, -1, sizeof(MAP));
    memset(Connect, false, sizeof(Connect));
}
 
void Input()
{
    cin >> N;
    int Num = 1;
    int EvenOrOdd;
 
    for (int i = 1; i <= N; i++)
    {
        if (i % 2 == 1) EvenOrOdd = 1; // 홀수 행에 대해서는 True 값을
        else EvenOrOdd = 0;              // 짝수 행에 대해서는 False 값을
 
        for (int j = 1; j <= N - 1 + EvenOrOdd; j++)
        {
            cin >> MAP[i][j].Left >> MAP[i][j].Right;
            MAP[i][j].Num = Num;
            Num++;
        }
    }
}
 
void Set_Tile_Connecting()
{
    // 홀수행의 경우 0 1 3 5 6 7
    // 짝수행의 경우 1 2 3 4 5 7 
    int EvenOrOdd;
    for (int i = 1; i <= N; i++)
    {
        if (i % 2 == 1) EvenOrOdd = 1;    // 1일 때 홀수행
        else EvenOrOdd = 0;                // 0일 때 짝수행
 
        for (int j = 1; j <= N - 1 + EvenOrOdd; j++)
        {
            for (int k = 0; k < 8; k++)
            {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (MAP[nx][ny].Left == -1 || MAP[nx][ny].Right == -1) continue;
                
                if (EvenOrOdd == 1) // 홀수 행일 때
                {
                    if (k == 2 || k == 4) continue;
                    else if (k == 0 || k == 6 || k == 7)
                    {
                        if (MAP[nx][ny].Right == MAP[i][j].Left) Connect[i][j][k] = true;
                    }
                    else if (k == 1 || k == 3 || k == 5)
                    {
                        if (MAP[nx][ny].Left == MAP[i][j].Right) Connect[i][j][k] = true;
                    }
                }
                else
                {
                    if (k == 0 || k == 6) continue;
                    else if (k == 1 || k == 5 || k == 7)
                    {
                        if (MAP[nx][ny].Right == MAP[i][j].Left) Connect[i][j][k] = true;
                    }
                    else if (k == 2 || k == 3 || k == 4)
                    {
                        if (MAP[nx][ny].Left == MAP[i][j].Right) Connect[i][j][k] = true;
                    }
                }
            }
        }
    }
}
 
void BFS()
{
    queue<pair<pair<int, int>, int > > Q;
    Q.push(make_pair(make_pair(1, 1), 1));
    Visit[1][1] = true;
    Path[1] = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int n = Q.front().second;        
        Q.pop();
 
        Max_Tile = Bigger(n, Max_Tile);
 
        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nn = MAP[nx][ny].Num;
 
            if (MAP[nx][ny].Left == -1 || MAP[nx][ny].Right == -1) continue;
            if (Connect[x][y][i] == true)    // 연결되어 있다면
            {
                if (Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), nn));
                    Path[nn] = n;
                }
            }
        }
    }
}
 
void Find_Result_Path()
{
    vector<int> V;
 
    int Tmp = Max_Tile;
    V.push_back(Tmp);
    while (Path[Tmp] != 0)
    {
        V.push_back(Path[Tmp]);
        Tmp = Path[Tmp];
    }
    cout << V.size() << endl;
    for (int i = V.size() - 1; i >= 0; i--)
    {
        cout << V[i] << " ";
    }
    cout << endl;
}
 
void Solution()
{
    Set_Tile_Connecting();
    BFS();
    Find_Result_Path();
}
 
void Solve()
{
    Initialize();
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}