[ SWEA 1949 ] 등산로 조성 (C++)

SWExpertAcademy의 등산로조성(1949) 문제이다.

[ 문제풀이 ]

1) 본인은 이 문제를 DFS를 통해서 접근해 보았다. 먼저 기존의 맵에서 갈 수 있는 등산로의 최대길이를 계산해서 값을 한번

    갱신시켜 주었고 이후에 모든 좌표들을 돌면서 1부터 K 까지 돌면서 그 값만큼 빼주면서 진행해 주는 완전탐색 방법을

    진행해 주었다. 모든 좌표들을 돌면서 다 빼준것 맞지만, 가장 낮은 지형에 대해서는 계산해 주지 않았다.

    가장 낮은 지형을 더 낮춰줘봤자 크게 의미가 없는 탐색이기 때문이다.

    사실 시간이 조금 걸리는 부분이 있어서 줄여주고 싶었는데 도저히 방법이 생각이 나질 않았따....

2) 사실 DFS탐색은 특별한 조건은 없었다. 이동하려는 봉우리가 이전 봉우리보다 낮기만 하다면 탐색을 계속 진행해주면

    된다. 별다른 설명보다는 소스코드만 보더라도 충분히 이해할 수 있을 거라 생각한다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
bool Already_Answer;
int Answer, N, K;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, int>> V_Max;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
int Max, Min;
 
void Initialize()
{
    Answer = 0;
    Already_Answer = true;
    Max = 0;
    Min = 987654321;
    memset(Visit, false, sizeof(Visit));
    memset(MAP, 0, sizeof(MAP));
    V_Max.clear();
}
 
void Input()
{
 
    int Num = 0;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (i == 0 && j == 0) Num = MAP[i][j];
            else
            {
                if (Already_Answer == true)
                {
                    if (MAP[i][j] != Num) Already_Answer = false;
                }
            }
 
            if (MAP[i][j] > Max) Max = MAP[i][j];
            if (MAP[i][j] < Min) Min = MAP[i][j];
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == Max) V_Max.push_back(make_pair(i, j));
        }
    }
}
 
void BFS(int a, int b, int A[][MAX])
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 1));
    Visit[a][b] = true;
 
    int Cnt;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        Cnt = Q.front().second;
        Q.pop();
 
        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 (Visit[nx][ny] == false && A[nx][ny] < A[x][y])
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
    }
    Answer = Bigger(Answer, Cnt);
}
 
void DFS(int x, int y, int Len, int A[][MAX])
{
    Answer = Bigger(Answer, Len);
    
    Visit[x][y] = true;
    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 (Visit[nx][ny] == false && A[nx][ny] < A[x][y])
            {
                DFS(nx, ny, Len + 1, A);
            }
        }
    }
    Visit[x][y] = false;
}
 
void Copy_MAP(int A[][MAX], int B[][MAX])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            A[i][j] = B[i][j];
        }
    }
}
 
void Solution()
{
    if (Already_Answer == true)
    {
        Answer = 2;
        return;
    }
 
    for (int i = 0; i < V_Max.size(); i++)
    {
        int x = V_Max[i].first;
        int y = V_Max[i].second;
        DFS(x, y, 1, MAP);
    }
 
    for (int k = 0; k < V_Max.size(); k++)
    {
        int x = V_Max[k].first;
        int y = V_Max[k].second;
 
        int C_MAP[MAX][MAX];
        Copy_MAP(C_MAP, MAP);
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (MAP[i][j] == Min) continue;
                if (i == x && j == y) continue;
 
                for (int t = 1; t <= K; t++)
                {
                    C_MAP[i][j] = C_MAP[i][j] - t;
                    DFS(x, y, 1, C_MAP);
                    C_MAP[i][j] = C_MAP[i][j] + t;
                }
            }
        }
    }
}
 
void Solve()
{
    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;
}