ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2105.디저트 카페
    알고리즘/SW Expert Academy 2020. 6. 27. 12:05

    이번에 풀어볼 문제는 SW Expert 2105번 디저트 카페이다. 재귀함수를 이용해서 풀면 간단히 풀리지만

    중요한건 역시나 설계이다. 어떻게하면 불필요한 계산을 줄일지 고민해보고 풀어야한다.

     

    SW Expert Academy

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

    swexpertacademy.com

    1. 각 모서리 값은 굳이 탐색을 할 필요가 없다

    => 우리가 탐색하는 형태는 마름모 모양이므로 각 모서리는 탐색을 할 수 없다는 것을 인지

     

    2. 항상 탐색의 시작은 아래로만 탐색하면된다. => Point !!

    => 탐색은 왼쪽에서 오른쪽으로, 윗줄부터 아랫줄로 탐색이 진행되는데 그림을 그려보면 알겠지만

         윗줄에서 탐색한 내용들은 전부 아랫줄에서 위로 탐색하는 부분과 일치한다. 그러므로 불필요한 연산이다.

     

    3. 탐색방향에 대한 생각  => Point !!

    => 그렇다면 우리가 탐색을 시작하는 건 무조건 아랫쪽방향인데 그렇게는 두 가지가 있다. 바로 시계냐 반시계냐 인데

         이 또한 그림을 그려서 생각해보면 방향이 상관이 없다는 것을 알 수 있다.

     

    4. 중복은 배열의 인덱스로 체크해주자! 

    => 다양한 문제를 풀어보았다면 한 번쯤은 마주치게되는 스킬이다. 해당 배열의 값을 인덱스로 중복되지 않았는지 check!!

     

    => 개인적으로 2, 3번을 떠올리는게 Key point 같다.

     


     

    < 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

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <string.h>
    #include <algorithm>
     
    #define MAX 21
    #define MAX2 101
     
    using namespace std;
     
    int T, N;
    int map[MAX][MAX]; // 디저트 map
    bool check[MAX2]; // 갔던 카페인지 확인하기 위한 배열
     
    int dx[4= { 11-1-1 }; // 대각선 방향 => 시계방향
    int dy[4= { 1-1-11 };
     
    int start_x, start_y; // 탐색 시작 좌표
    int answer = -1// 정답
     
    void search(int x, int y, int dir, int cnt){// y, x 좌표, 탐색방향의 idx, 탐색한 카페 갯수
        int ax = x + dx[dir]; // 대각선이동
        int ay = y + dy[dir];
     
        if (ax < 0 || ay < 0 || ax >= N || ay >= N) // 맵에서 벗어나면 return
            return;
     
        if (ax == start_x && ay == start_y && dir == 3){ // 초기의 값으로 돌아오거나 대각선 탐색 idx를 모두 사용한 경우
                                                         // 이렇게 하는 이유는 idx를 조건으로 안주면 왔던길을 되돌아오는걸 걸러낼수 없음
            answer = max(answer, cnt); // 최대 값을 구하고 리턴
            return;
        }
     
        
        if (!check[map[ax][ay]]){ // 간적이 없는 길인 경우
            check[map[ax][ay]] = true// 간것으로 표기
            search(ax, ay, dir, cnt + 1); // 탐색 대각선 방향은 그대로해서 탐색 진행
     
            if (dir < 3// 탐색 방향을 모두 사용하지 않았다면
                search(ax, ay, dir + 1, cnt + 1);  // 탐색방향을 바꿔서 다시 탐색 진행
            
            check[map[ax][ay]] = false// 다른 방향을 찾기위해 갔던길은 다시 false
        } 
    }
    void init(){ // 초기화 함수
        answer = -1;
        memset(map, 0sizeof(map));
        memset(check, 0sizeof(check));
    }
    int main()
    {
        freopen("2105.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            init(); // 초기화
     
            cin >> N;
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    cin >> map[i][j]; // 입력을 받음
                    if ((i == 0 || i == N-1&& (j == 0 || j == N - 1)) // 각 모서리의 경우 
                        map[i][j] = 0// 탐색하지 않기위해 0으로 초기화
                }
            }
     
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    if (map[i][j]){ // map에 값이 있을 때만 탐색
                        start_x = i;// 탐색 시작 초기좌표 저장
                        start_y = j;
                        check[map[i][j]] = true// 탐색 시작의 디저트 번호는 방문으로 체크
                        search(i, j, 01); // 탐색 시작
                        check[map[i][j]] = false;// 다른 탐색을 위해 다시 방문 해제
                    }
                }
            }    
            cout << "#" << z << " " << answer << endl;
        }
        return 0;
    }
    cs
    반응형

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

    2383.점심 식사시간  (0) 2020.07.10
    2477.차량 정비소  (2) 2020.07.07
    2115.벌꿀채취  (0) 2020.06.23
    4008.숫자 만들기  (0) 2020.06.19
    5658.보물상자 비밀번호  (0) 2020.06.18

    댓글

Designed by Tistory.