[ SWEA 1861 ] 정사각형 방 (C++)

SWExpertAcademy의 정사각형 방(1861 / D4) 문제이다.

[ 문제풀이 ]

1) 본인은 이 문제를 메모이제이션을 이용해서 풀어보았다.

   단순히, 모든 좌표에서 움직일 수 없을 때 까지 움직여보는 방법은 구현해보지는 않았지만, 시간이 조금 오래 걸릴 것 같아서

   이미 한번이라도 움직여본 좌표라면 몇 번 움직일 수 있는지를 저장해 보면서 진행하였다.

   본인이 사용한 변수로는, int Move_Num[][] 이라는 2차원 int형 배열을 하나 만들어서 사용해주었는데,

   Move_Num[a][b] = c의 의미는 "(a, b)에서는 c개의 방을 이동할 수 있습니다" 를 의미한다.

   주의해야 할 것은, 탐색을 시작하는 순간, Move_Num[x좌표][y좌표] 의 값은 1이 된다는 것이다.

   왜냐하면, 해당 좌표 하나만으로도 이미 1개의 방을 이동할 수 있기 때문이다.

  

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, Answer, Answer_Num;
int MAP[MAX][MAX];
int Move_Num[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
    memset(Move_Num, -1, sizeof(Move_Num));
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int DFS(int x, int y)
{
    if (Move_Num[x][y] != -1) return Move_Num[x][y];
    Move_Num[x][y] = 1;
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (MAP[nx][ny] - MAP[x][y] == 1)
            {
                Move_Num[x][y] = Move_Num[x][y] + DFS(nx, ny);
            }
        }
    }
    return Move_Num[x][y];
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int Result = DFS(i, j);
            if (Answer < Result)
            {
                Answer = Result;
                Answer_Num = MAP[i][j];
            }
            else if (Answer == Result)
            {
                Answer_Num = Min(Answer_Num, MAP[i][j]);
            }
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer_Num << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}