[ SWEA 1210 ] Ladder1 (C++)

SW Expert Academy의 Ladder1(1210 / d4) 문제이다.

[ 문제풀이 ]

1) 이 문제는 사다리 게임을 하는데, 몇 번 시작점에서 시작해야, '2'로 끝나는 점에 도착할 수 있는 시작점을 구하는 문제이다.

   본인은, 이 문제를 사다리를 거꾸로 타는 식으로 구현해보았다. 사실, 0 ~ 100 까지 사다리가 존재하는 모든 정점에서, 사다리를

   타보고, 2로 끝나는 정점을 출력해도 되지만, 이렇게 되면 시간이 너무 오래 걸릴 것 같아서, 역으로 끝나는 점인 '2'에서 거꾸로

   사다리를 타서 시작점을 찾는 식으로 구현해보았다. 

  

2) 구현하는 내용은 어렵지 않다. 현재 x좌표와 y좌표 2개를 관리해주었는데, 마지막 점에서 위로 쭉 올라가다가 왼쪽 혹은 오른쪽

   에 길이 생기면, 그 길을 따라서 가고, 다시 올라가는 길이 생긴다면 올라가는 식으로 정말 사다리 타기 게임 그대로 구현해 주었

   다. 어려운 알고리즘이 사용된 것이 아닌, 문제에서 원하는대로 구현을 잘해야 하는 문제이기 때문에 소스코드를 참고하는

   것이 긴 설명 보다 더 나을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int MAP[MAX][MAX];
int Answer;
 
pair<int, int> Start;
 
void Initialize()
{
    Answer = 0;
    Start.first = -1;
    Start.second = -1;
}
 
void Input()
{
    int Num; cin >> Num;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 2)
            {
                Start.first = i;
                Start.second = j;
            }
        }
    }
}
 
int Start_Ladder(int x, int y)
{
    char Dir = 'U';
 
    while (1)
    {
        if (x == 0) return y;
        
        if (Dir == 'U')
        {
            x--;
            while (1)
            {
                if (x == 0) break;
 
                if (y + 1 < MAX)
                {
                    if (MAP[x][y + 1] == 1)
                    {
                        Dir = 'R';
                        break;
                    }
                }
 
                if (y - 1 >= 0)
                {
                    if (MAP[x][y - 1] == 1)
                    {
                        Dir = 'L';
                        break;
                    }
                }
                x--;
            }
        }
        else if (Dir == 'R')
        {
            y++;
            while (1)
            {
                if (x - 1 >= 0)
                {
                    if (MAP[x - 1][y] == 1)
                    {
                        Dir = 'U';
                        break;
                    }
                }
                y++;
            }
        }
        else if (Dir == 'L')
        {
            y--;
            while (1)
            {
                if (x - 1 >= 0)
                {
                    if (MAP[x - 1][y] == 1)
                    {
                        Dir = 'U';
                        break;
                    }
                }
                y--;
            }
        }
    }
}
 
void Solution()
{
    Answer = Start_Ladder(Start.first, Start.second);
}
 
void Solve()
{
    int Tc = 10;
    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;
}