ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2117.홈 방범 서비스
    알고리즘/SW Expert Academy 2020. 6. 6. 21:30

    이번에 풀어볼 문제는 SW Expert 2117 홈 방범 서비스다. 난이도는 역시나 그렇게 어려운 거같진 않지만

    이번에 느낀점은 역시 예외상황을 확인하려면 예시를 잘봐야한다.

    이 문제에서 나의 실수는 탐색에 있었다. 이 문제는 전부다 탐색을 해봐야 하는데.. 

    나는 집위주로만 탐색을 했다. 허허허.. 여튼 다시수정했으니 됐지만...

     

    SW Expert Academy

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

    swexpertacademy.com

    1. 탐색을 언제 끝마칠지 판단해야함 => 서비스 범위가 맵을 넘어서면 정지

    2. 언제 최대값을 가져갈지 생각해야함 => 이득 - 운영비용이 적자가 나지 않으면 해당 값을 최대치와 비교

    3. 탐색하는 좌표에 집이 있는 경우 => 집 갯수 +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
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    #pragma warning(disable:4996)
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
     
    #define MAX 21
    using namespace std;
    int T, N, M;
     
    int dx[4= { 001-1 };
    int dy[4= { 1-100 };
     
    int map[MAX][MAX];
    int check[MAX][MAX];
    queue<pair<intint>>q;
    int answer = 0;
     
    void reset_check(){ // check배열과 queue 초기화
        for (int i = 0; i < MAX; i++){
            for (int j = 0; j < MAX; j++){
                check[i][j] = 0;
            }
        }
        int size = q.size();
        for (int i = 0; i < size; i++)
            q.pop();
    }
     
    void reset(){ // 변화하는 모든 배열과 변수 초기화
        for (int i = 0; i < MAX; i++){
            for (int j = 0; j < MAX; j++){
                check[i][j] = map[i][j] = 0;
            }
        }
        answer = 0;
    }
     
    int search(int x, int y){ // 탐색
        q.push(make_pair(x, y)); // 시작 좌표 큐에 push
        check[x][y] = 1;         // 시작 좌표 방문
        int house = 0;  // 집 관련 변수
        int k = 1;      //
        if (map[x][y]) // 해당 좌표 map 값이 0보다 크면
            house += 1;// 집이있으니 집갚 +1
        
        while (!q.empty()){ 
            if (k > N + 1// N+1보다 K값이 커지면
                break;     // 탐색종료
     
            if ((house*- ((k*k) + (k - 1)*(k - 1))) >= 0// 집세로 받은 돈보다 운영값이 적으면
                answer = max(answer, house); // 집 갯수 비교후 최대값 저장
            
            int size = q.size(); // 큐에 크기만큼만 탐색
            for (int j = 0; j < size; j++){
                int xx = q.front().first;
                int yy = q.front().second;
                q.pop();
     
                for (int i = 0; i < 4; i++){
                    int ax = xx + dx[i];
                    int ay = yy + dy[i];
                    if (ax < 0 || ay < 0 || ax >= N || ay >= N)
                        continue;
                    if (!check[ax][ay]){ // 방문한적없으면
                        q.push(make_pair(ax, ay)); // 방문으로 체크하고
                        check[ax][ay] = check[xx][yy] + 1// 방범 운영범위 저장( 디버깅하기 좋게)
                        if (map[ax][ay]){ // 방문한 좌표에 집이있으면
                            house += 1// 집크기 +1
                        }
                    }
                }
            }    
            k++// 방범 운영 범위 증가
        }
        return answer;
    }
     
    int main(){
        freopen("2117.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            reset();     // 다음 테스트 케이스를 위해 초기화
            int ans = 0;// 정답변수
            cin >> N >> M;
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++)
                    cin >> map[i][j]; // 맵에 값 입력받기
            }
     
     
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    ans = max(ans, search(i, j)); // 탐색 후 최대값 저장
                    reset_check(); // check 배열만 초기화
                }
            }
            cout << "#" << z << " " << ans << endl;
        }
        return 0;
    }
    cs
    반응형

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

    5650.핀볼 게임  (0) 2020.06.14
    5656.벽돌깨기  (0) 2020.06.12
    5653.줄기세포배양  (0) 2020.06.06
    1949.등산로 조성  (0) 2020.06.03
    5644.무선충전  (0) 2020.06.02

    댓글

Designed by Tistory.