1949.등산로 조성

이번에 풀어볼 문제는 SW Expert의 1949 등산로 조성이다. ( 아래링크는 SW Expert 로그인하고 눌러야함.. )

SW Expert Academy

난이도는 높지않지만 한 가지를 빼먹어서 테스트 케이스 50개중 48개만 맞았다..

제엔자앙!!!!!!! => 완벽한 설계인줄 알았는데... 닿을 듯 말 듯하네.. ㅎㅎ

여기서 중요한 점은 깎는 점에 대한 처리인데 언제깎아야할지는 생각보다 간단하다.

---

< 나의 설계 및 접근 >

0. 제일 높은 봉우리를 찾고난 뒤 => 제일 높은 봉우리 일때만 해당좌표를 시작으로 탐색을 진행한다.

=> 탐색(BFS)은 재귀함수로 진행!! => 그렇지 않으면 check배열을 처리하는게 불편해짐

 

1. 다음 좌표의 값이 현재 좌표의 값보다 낮을 때 => 그냥 DFS 탐색으로 하면된다.

 

2. 다음 좌표의 값이 현재 좌표의 값보다 크거나 작을 때 => 이 때 깎아주면 된다!!

=> 하지만 중요한건 나는 최대 깎을 수 있는 K만큼 깎았는데 이 문제의 함정이 바로 여기에 있다.

=> 봉우리가 높을 수록 갈 수 있는 경로가 당연히 길어질 수 밖에 없기 때문에 깎을 양은

=> 현재좌표의 값 - 1 한 것(최대한 높게 깎아야 한다)이 최대값을 만들어 낼 수 있다.. (이걸 빼먹었다..)

 

---

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <string.h>
#define MAX 9
using namespace std;
int T, N, K;
 
int map[MAX][MAX];    // map이 저장
bool check[MAX][MAX]; // 방문한 곳 저장
int answer = 0;         // 정답
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
void showme(){ // 배열 내용 보기
    cout << "\n";
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
    cout << "\n";
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cout << check[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
    cout << "answer = " << answer << "\n";
}
void search(int x, int y, bool dig, int cnt){
    for (int i = 0; i < 4; i++){
        int ax = x + dx[i];
        int ay = y + dy[i];
        if (ax < 0 || ay < 0 || ax >= N || ay >= N) // map 내부에 있는지 확인
            continue; // 아닌 경우 넘어감
        int tmp = map[ax][ay]; //해당좌표값이 깎일 수도 있으니 원복에 대비하여 저장해두기
        if (!check[ax][ay] && map[x][y] > map[ax][ay]){ // 높은 곳에서 낮은 곳인 경우
            check[ax][ay] = true; // 방문 좌표 체크
            answer = max(cnt + 1, answer);  // 하나 방문했으니 경로+1, 정답과 비교해서 최대값을 저장
            search(ax, ay, dig, cnt + 1); // 재귀함수로 다음 좌표 방문
            check[ax][ay] = false;        // 재귀함수 이후, 다른 경로를 확인하기위해 방문한 좌표 지움(가는길이 똑같은 여러 경로가 있을 수 있으니)
        }
        //방문한적 없으면 다음에 방문할 좌표의 값이 이전 좌표의 값보다 크거나 같을때
        else if (!check[ax][ay] && map[ax][ay] >= map[x][y] && abs(map[ax][ay] - map[x][y]) < K && !dig){
            check[ax][ay] = true;       // 방문 좌표 체크
            map[ax][ay] = map[x][y] - 1;  // 해당 좌표값을 기존과 -1 차이로 깎음 ( 최대 K만큼 깎을수 있지만 높이가 높을수록 경로를 길게 뺄 수 있으므로)
            answer = max(cnt + 1, answer); // 경로 +1 추가후 최대값 비교
            search(ax, ay, true, cnt + 1); // 재귀함수로 다음좌표 방문( 깎기를 진행했으므로 flag값은 true로 진행)
            check[ax][ay] = false;       // 재귀함수 이후, 다른 경로를 확인하기위해 방문한 좌표 지움(가는길이 똑같은 여러 경로가 있을 수 있으니)
            map[ax][ay] = tmp;           // 깎은값 원복
        }
    }
    //showme();
    return; //더이상 해당 사항없으면 반환
}
void reset(){ // 다음 테스트 케이스를 위한 초기화
    memset(map, 0, sizeof(map));
    memset(check, 0, sizeof(check));
    answer = 0;
}
int main() {
    freopen("1949.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        cin >> N >> K;
        int high = 0;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                cin >> map[i][j];
                high = max(map[i][j], high); // 가장 높은 봉우리 찾기
            }
        }
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (map[i][j] == high){ // 가장높은 봉우리 일때부터 탐색 시작
                    check[i][j] = true; // 시작좌표 방문처리
                    search(i, j, false, 1); // 시작 좌표, dig유무, dig할 수 있는 최대값 넘겨줌
                    check[i][j] = false; // 해당좌표 탐색이 끝났으므로 다음 탐색을 위해 방문처리 취소
                }
            }
        }
        cout << "#" << z << " " << answer << "\n";
        reset();
    }
    return 0;
}

# 어제보다 한 발 더 내딛은 기분이다!!