ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1949.등산로 조성
    알고리즘/SW Expert Academy 2020. 6. 3. 22:51

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

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

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

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

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


    < 나의 설계 및 접근 >

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

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

     

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

     

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

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

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

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

     


    < Code 설명 >

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    #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= { 001-1 };
    int dy[4= { 1-100 };
    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, 0sizeof(map));
        memset(check, 0sizeof(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, false1); // 시작 좌표, dig유무, dig할 수 있는 최대값 넘겨줌
                        check[i][j] = false// 해당좌표 탐색이 끝났으므로 다음 탐색을 위해 방문처리 취소
                    }
                }
            }
            cout << "#" << z << " " << answer << "\n";
            reset();
        }
        return 0;
    }
    cs

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

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    2117.홈 방범 서비스  (0) 2020.06.06
    5653.줄기세포배양  (0) 2020.06.06
    1949.등산로 조성  (0) 2020.06.03
    5644.무선충전  (0) 2020.06.02
    1229.암호문2  (0) 2020.03.31
    1228.암호문1  (0) 2020.03.29

    댓글 0

Designed by Tistory.