SWExpert #1949 등산로 조성

목표: SWExpertacademy P1949 등산로 조성 문제 풀기

환경: mac OS High Sierra 10.13.4, CLion

이 문제 또한 완전탐색으로 풀려고 합니다. 완전탐색이란 문제의 답을 찾는 것인데, 가능한 경우를 모두 나열하고, 각각이 해가 될 수 있는지 확인하는 방법입니다.

우선 완전탐색의 장단점을 얘기해보자면 장점으로는 어떻게든 답을 구해낼 수 있다는 것이에요. 모든 경우를 다 살펴보고 해를 구하는 것이니까요. 단점은 문제의 조건에 따라 오래 걸린다는 것인데, 이것을 최적화 하는 방법들이 있어요. 가지치기라든지 백트래킹이라든지

[제약 사항]

  1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

  2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)

  3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)

  4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.

  5. 지도에서 가장 높은 봉우리는 최대 5개이다.

  6. 지형은 정수 단위로만 깎을 수 있다.

  7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.

로직

이 문제도 크게 두가지 로직으로 나뉘는데요.

깍을 산을 선택하는 로직과

등산로 조성 즉 등산로 길이를 구하는 로직으로 나뉘는데요.

깍을 산을 선택하는 로직은 N제한이 크지 않기 때문에 2중 for문을 통해서 각각의 산을 K번 깍습니다.

등산로 조성은 결국 노드를 이동하는 것인데, 노드를 이동하는 것은 그래프의 순회를 이용하면 되는데요.

그래프 순회로는 가장 간단한 방법 중 DFS,BFS가 있는데, 자기자신보다 낮은 산으로 이동하여, 그 길이를 구하는 것이기 때문에 DFS로 풀기로 결정했어요.

“나를 먼저 방문하고 그 다음으로 인접한 노드를 차례대로 방문” -> 인접한노드를 차례대로 방문이라는 말은 자기자신 위치를 기준으로 상 하 좌 우로 이동이 가능하며, 자기 자신보다 낮은 산으로 이동해야하는 규칙이 있습니다.

“단, 방문했던 노드는 방문하지 않는다.”

일반적인 DFS는 체크배열을 이용해서 이전에 방문한 정점인지 확인하는 노드가 필요한데, 이 문제에는 자기보다 작은 값으로만 이동가능하다는 특성이 있기 때문에 따로 체크배열을 만들지 않고 자기자신보다 작으면 이동하는 것으로 체크로직을 대신했습니다.

이 문제가 의미있다고 생각하는 이유는 브루트포스를 이용해 풀 수 있고, 완전탐색(부르트포스)는 인간의 논리를 넣지않고, 컴퓨터의 연산능력을 이용해 모든 경우의수(등산로 조성이 가능한)를 탐색하라입니다 단, 입력제한으로 시간복잡도 계산을 통해 시간안에 프로그램이 수행된다고 하면요.

등산로 조성

[code]

#include <iostream>
#include <cstring>

using namespace std;

const int PEAKMAX = 5;
const int MAX = 20;
int TC, N, K, max1, ans;
int map[MAX][MAX];

int dRow[] = {-1, 0, 1, 0}; //상하좌우 이동을 위한 배열
int dCol[] = {0, 1, 0, -1};

pair<int, int> highestPoint[PEAKMAX];

void DFS(int row, int col, int cnt) {
    //봉우리의 위치에서부터 등산로 조성하고 등산로 길이 갱신하는 함수

    for (int i = 0; i < 4; ++i) {
        int nextRow = row + dRow[i];
        int nextCol = col + dCol[i];

        if (nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < N) {
            if (map[nextRow][nextCol] < map[row][col]) {
//                cout<<"row: "<<nextRow<<", col: "<<nextCol<<"인 "<<map[nextRow][nextCol]<<"에 방문\n";
                DFS(nextRow, nextCol, cnt + 1);
                if (cnt + 1 > ans) {
                    ans = cnt + 1;
                }
            }
        }
    }
}

int main() {
    cin >> TC;

    int cnt = 0;


    for (int T = 1; T <= TC; ++T) {
        cin >> N >> K;

        max1 = 0;
        ans = 0;
        cnt = 0;

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> map[i][j];

                //  미리 봉우리 위치를 저장해두고

                if (max1 < map[i][j]) {
                    max1 = map[i][j];
                    memset(highestPoint, 0, sizeof(highestPoint));
                    cnt = 0;
                    highestPoint[cnt].first = i;
                    highestPoint[cnt].second = j;
                    cnt += 1;
                } else if (max1 == map[i][j]) {
                    highestPoint[cnt].first = i;
                    highestPoint[cnt].second = j;
                    cnt += 1;
                }
            }
        }

        for (int k = 0; k < N; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = 1; j <= K; ++j) {

                    //2중 for문을 통해 각각의 산을 다 깍아보면서

                    map[k][i] -= j;
//                        cout<<"row: "<<k<<", col:"<<i<<" 을 "<<j<<"만큼 깍아서 "<<map[k][i]<<"로 깍였음\n";

                    for (int l = 0; l < cnt; ++l) {

                        //각각의 봉우리 위치에서 DFS를 수행한다.

                        int row = highestPoint[l].first;
                        int col = highestPoint[l].second;
//                            cout<<"row: "<<row<<", col: "<<col<<"인 "<<map[row][col]<<"에 방문\n";
                        DFS(row, col, 1);
//                            cout<<"봉우리 높이:"<<map[row][col]<<"에서"<<" row: "<<row<<", col: "<<col<<", 현재 제일 긴 등산로 길이: "<<ans<<"입니다\n";
                    }

                    //깍았던 산을 원상복귀 시킨다. 백트래킹의 경우 함수 호출전에 상태를 바꿨으면 함수 호출 후 상태를 원복 시켜야 각각의 경우의 수가 독립적인 탐색을 한다고 볼 수 있음.
                    map[k][i] += j; 



                }
            }
        }

        cout << "#" << T << " " << ans << "\n";

    }


    return 0;
}