[ 백준 1347 ] 미로 만들기 (C++)

백준의 미로만들기(1347) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 문제에서 사람이 움직이는 방향과 나아가는 칸 수를 통해서 맵을 그려야 하는 문제이다.

   문제풀이에 들어가기 전, 우리가 어떤 점을 생각하면서 문제에 접근해야 하는지 알아보자.

   먼저 첫 번째 조건을 확인해 보자면 미로는 "직사각형의 격자모양" 이라는 것이다.

   즉, 문제에서 주어진 조건대로 맵을 그렸을 때, 그 모양이 직사각형 모양이 아니라면, 나머지 빈 칸을 직사각형이 되도록

   벽으로 채워줘야 한다는 점에 유의해 줘야 한다.

   두번째로 생각해 줘야할 것이 맵의 전체적인 크기이다. 본인은 맵의 크기를 101로 잡았다. 왜냐하면 문제에서

   미로를 탈출하는 내용의 길이가 50보다 작다고 했으므로, 50번 모두 앞으로 나가라는 지시가 떨어지더라도, 그게 맵의

   범위 내에서 이뤄줘야 하기 때문에, 시작점을 50, 50 으로 잡았고, 전체 맵의 크기는 101 x 101으로 설정하였다.

   즉, (50, 50)에서는 상하좌우 어디로든지 50칸을 가더라도 맵의 범위 내에서 움직일 수 있기 때문이다.

2) 본격적인 문제를 구현하는 방법에 대해서 알아보자.

   먼저 R 혹은 L이라는 문자가 나올 때에는, 방향을 바꿔주는 내용만 구현해 주면 된다.

   본인은 동서남북을 0,1,2,3 으로 설정해 주었고, R과 L에 따라 방향을 바꾸어 주는 함수를 구현하였다.

   (본문함수 : int Change_Direction(int dir, char cmd))

   F라는 문자가 나올 때에는, 실제로 한칸 움직인 것을 표현해 줘야 한다. 본인은 맵에서 1을 사람이 움직인 것으로

   표현했으며, 1은 즉 미로에서의 길이라는 것을 의미한다.

   이것을 표현하기 위해서 초기상태로 (50, 50) 또한 1로 표현해주었다.

3) 그렇다면 이제까지 우리가 한 것을 정리해보고, 남은 작업이 무엇인지 알아보자.

   우리가 위의 과정을 통해서 한 것을 예제 입력을 통해서 알아보자.

   예제 입력은 'RRFRF' 이다. 위의 말대로 우리가 맵에 표시를 제대로 했다면 아마

   이러한 모양이 되어 있을 것이다. (파랑색 1 = (50, 50) = 시작점)

    위의 그림에 좌표를 적어놓은 이유는 밑에 계속 읽어보면 알 수 있다.

    하지만 처음에 말했다시피, 미로는 직사각형의 모양이다. 위의 모양은 삼각형이기 때문에 직사각형으로 만들어 주기

    위해서 파랑색 오른쪽 빈 공간에 # 을 넣어줌으로써 벽으로 표시를 해줘야 할 것이다.

    하지만, 이건 둘째 치고 그 전에 이 삼각형 모양이라도 어떻게 출력해 내야 할지 생각해보자.

    바로 가장 먼저 나오는 x좌표와 가장 마지막에 나오는 x좌표, 가장 먼저 나오는 y좌표와 가장 마지막에 나오는 y좌표를

    찾아내는 것이다.

    위의 예제입력에 대한 정답에서는 가장 먼저 나오는 x좌표는 49, 가장 마지막에 나오는 x좌표는 50

    가장 먼저 나오는 y좌표는 50, 가장 마지막에 나오는 y좌표는 51이 될 것이다.

    그럼, 이 좌표값들을 찾는 것을 구현해보자.

{
    int sx, sy, ex, ey;
        sx = sy = MAX;
        ex = ey = 0;
        for (int i = 0; i < MAX; i++)
        {
            for (int j = 0; j < MAX; j++)
            {
                if (MAP[i][j] == 1)
                {
                    if (i < sx) sx = i;
                    if (j < sy) sy = j;
                    if (i > ex) ex = i;
                    if (j > ey) ey = j;
                }
            }
        }
    }
}

     위의 코드처럼 구현을 하면 된다. 0부터 101의 범위까지 모든 정점들을 반복하면서, 가장 작은 x,y값과 가장 큰 x,y값을

     계속해서 초기화 시켜주면서 찾아주면 된다.

     위의 값들을 찾았다면 저 범위 내에서만 반복문을 하면서 출력을 시켜주기만 하면 된다.

     굳이 전체범위가 아닌 저 범위 내에서만 반복을 하더라도 결과를 얻어낼 수 있다.

    for (int i = sx; i <= ex; i++)
    {
        for (int j = sy; j <= ey; j++)
        {
            if (MAP[i][j] == 1) cout << ".";
            else cout << "#";
        }
        cout << endl;
    }

     이런식으로 !

     전체적인 코드는 밑의 소스코드를 참고하도록 하자.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 101
using namespace std;
 
int N;
int MAP[MAX][MAX];
vector<char> V;
pair<int, int> Start;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        char a; cin >> a;
        V.push_back(a);
    }
    Start.first = Start.second = 50;
}
 
int Change_Direction(int dir, char cmd)
{
    if (cmd == 'R')
    {
        if (dir == 0) return 2;
        else if (dir == 1) return 3;
        else if (dir == 2) return 1;
        else if (dir == 3) return 0;
    }
    else if (cmd == 'L')
    {
        if (dir == 0) return 3;
        else if (dir == 1) return 2;
        else if (dir == 2) return 0;
        else if (dir == 3) return 1;
    }
}
 
void Solution()
{
    int x = Start.first;
    int y = Start.second;
    int Dir = 2;        // 초기방향 = 남쪽
 
    MAP[x][y] = 1;
 
    for (int i = 0; i < N; i++)
    {
        char D = V[i];
        if (D == 'R' || D == 'L') Dir = Change_Direction(Dir, D);
        else if (D == 'F')
        {
            x = x + dx[Dir];
            y = y + dy[Dir];
            MAP[x][y] = 1;
        }
    }
 
    int sx, sy, ex, ey;
    sx = sy = MAX;
    ex = ey = 0;
 
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if (MAP[i][j] == 1)
            {
                if (i < sx) sx = i;
                if (j < sy) sy = j;
                if (i > ex) ex = i;
                if (j > ey) ey = j;
            }
        }
    }
 
    for (int i = sx; i <= ex; i++)
    {
        for (int j = sy; j <= ey; j++)
        {
            if (MAP[i][j] == 1) cout << ".";
            else cout << "#";
        }
        cout << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}