[PS스터디 심화반] 4주차 백준 감시

개요

 

삼성 역량테스트의  기출 문제이며, 취준을 앞둔 입장으로 도움이 될 것 같아 선정하였습니다

 

https://www.acmicpc.net/problem/15683

15683번: 감시

 

 

리뷰와 피드백

 

큰 아이디어가 필요하다니 보단 단순 구현을 요구하는 문제 였습니다. 다만 그 범위가 넓으며, 요구하는 사항들 사이에

언듯 비슷한 부분이 많아 어떻게 모듈화하여 줄일 수 없을까란 생각에 빠지게되어 문제의 난이도가 더 높게 느껴진 문제입니다. 저는 해당 문제를 vector 컨테이너를 이용하여 풀었습니다만, 다른 분들 중에는 배열을 사용해 해결하셨습니다.

 

전체적인 해결과정이 비슷하였지만 다른 분들에 비해 저의 코드는 성능이 조금 떨어졌습니다. vector 컨테이너를 사용함에 따른 성능저하인지 dfs를 구현하는 과정에서 반복문이 아닌 재귀호출에 의한 성능저하인지 의문이 들었습니다.

 

 

 

 

개선안

 

이러한 성능적인 부분을 개선하기 위해 현재 코드에서 변화를 주었습니다.

vector를 쓰지 않고 배열로 구현한 다는 것은 현재 풀이의 근간 자체가 바뀌는 셈이라 현재 풀이방법을 검증하는데 큰 의미가 없을 것 같아 dfs의 구현만을 재귀호출에서 단순 반복으로 구현하였습니다.

 

dfs의 구현을 바꾼 것 만으로는 성능적인 변화가 없었습니다. 그래서 vector라는 컨테이너를 호출하메 있어 추가적인 비용이 소요된 것은 아닌가 추측하였습니다.

 

 

개선 전 / 후   코드 전문

 

... 생략
// 개선 전

#include <iostream> // 사무실 전체를 재귀로 순회하며 모든 경우를 다 구합니다
#include <algorithm> // 이후 카메라가 감시 하는 범위의 구역이 가이 큰 경우를 구한 뒤
#include <vector>    // 그 전체 범위에서 최대감시범위를 빼고 출력합니다.
                     // 초기에 입력을 받으며 벽이 있는 구역은 block 배열에 미리 true로 대입합니다.
using namespace std;

int n, m;
vector<vector<int>> arr(10, vector<int>(10));
vector<vector<bool>> block(10, vector<bool>(10));  // 감시범위이거나 벽인 경우 true

int mx = 0;

void dfs(int x, int y, int x_dir, int y_dir, vector<vector<bool>>& v) {
    v[x][y] = true;
    if (x + x_dir >= 0 && x + x_dir < n) {
        if (y + y_dir >= 0 && y + y_dir < m) {
            if (arr[x + x_dir][y + y_dir] != 6) dfs(x + x_dir, y + y_dir, x_dir, y_dir, v);
        }
    }

}

void rec(int x, int y, vector<vector<bool>> v) {
    int n_x = x, n_y = y + 1;
    if (x == n && y == 0) {     // 마지막 구역 도달 시 현재 배열 순회하여 감시구역 수 확인
        int count = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (v[i][j] == true) ++count;
            }
        }
        mx = max(mx, count);

        return;
    }
    if (n_y >= m) { ++n_x; n_y = 0; } // 2차원 배열 인덱스 초과시 유효 범위로 조정한다.

    if (arr[x][y] == 1) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, -1, 0, v2);
        rec(n_x, n_y, v2);
        vector<vector<bool>> v3 = v;
        dfs(x, y, 0, -1, v3);
        rec(n_x, n_y, v3);
        vector<vector<bool>> v4 = v;
        dfs(x, y, 1, 0, v4);
        rec(n_x, n_y, v4);
    }
    else if (arr[x][y] == 2) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, 0, -1, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, -1, 0, v2);
        dfs(x, y, 1, 0, v2);
        rec(n_x, n_y, v2);
    }
    else if (arr[x][y] == 3) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, 1, 0, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, 0, 1, v2);
        dfs(x, y, -1, 0, v2);
        rec(n_x, n_y, v2);
        vector<vector<bool>> v3 = v;
        dfs(x, y, 0, -1, v3);
        dfs(x, y, 1, 0, v3);
        rec(n_x, n_y, v3);
        vector<vector<bool>> v4 = v;
        dfs(x, y, 0, -1, v4);
        dfs(x, y, -1, 0, v4);
        rec(n_x, n_y, v4);
    }
    else if (arr[x][y] == 4) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, 1, 0, v1);
        dfs(x, y, -1, 0, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, 0, -1, v2);
        dfs(x, y, 1, 0, v2);
        dfs(x, y, -1, 0, v2);
        rec(n_x, n_y, v2);
        vector<vector<bool>> v3 = v;
        dfs(x, y, 0, 1, v3);
        dfs(x, y, 0, -1, v3);
        dfs(x, y, 1, 0, v3);
        rec(n_x, n_y, v3);
        vector<vector<bool>> v4 = v;
        dfs(x, y, 0, 1, v4);
        dfs(x, y, 0, -1, v4);
        dfs(x, y, -1, 0, v4);
        rec(n_x, n_y, v4);
    }
    else if (arr[x][y] == 5) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, -1, 0, v1);
        dfs(x, y, 0, -1, v1);
        dfs(x, y, 1, 0, v1);
        rec(n_x, n_y, v1);
    }
    else {
        rec(n_x, n_y, v);  // 0, 6인 경우
    }
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == 6) block[i][j] = true; // 벽의 경우 미리 true로 만든다.
        }
    }

    rec(0, 0, block);
    cout << n * m - mx;
}

 

 

 

... 생략
// 개선 후

#include <iostream> // 사무실 전체를 재귀로 순회하며 모든 경우를 다 구합니다
#include <algorithm> // 이후 카메라가 감시 하는 범위의 구역이 가이 큰 경우를 구한 뒤
#include <vector>    // 그 전체 범위에서 최대감시범위를 빼고 출력합니다.
                     // 초기에 입력을 받으며 벽이 있는 구역은 block 배열에 미리 true로 대입합니다.
using namespace std;

int n, m;
vector<vector<int>> arr(10, vector<int>(10));
vector<vector<bool>> block(10, vector<bool>(10));  // 감시범위이거나 벽인 경우 true

int mx = 0;

void dfs(int x, int y, int x_dir, int y_dir, vector<vector<bool>> &v) {
    if (x_dir == 0) {
        int n_y = y;
        while (n_y >= 0 && n_y < m) {
            if (arr[x][n_y] == 6) break;
            v[x][n_y] = true;
            n_y += y_dir;
        }
    }
    if (y_dir == 0) {
        int n_x = x;
        while (n_x >= 0 && n_x < n) {
            if (arr[n_x][y] == 6) break;
            v[n_x][y] = true;
            n_x += x_dir;
        }
    }

}


void rec(int x, int y, vector<vector<bool>> v) {
    int n_x = x, n_y = y + 1;
    if (x == n && y == 0) {     // 마지막 구역 도달 시 현재 배열 순회하여 감시구역 수 확인
        int count = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (v[i][j] == true) ++count;
            }
        }
        
        mx = max(mx, count);


        return;
    }
    if (n_y >= m) { ++n_x; n_y = 0; } // 2차원 배열 인덱스 초과시 유효 범위로 조정한다.

    if (arr[x][y] == 1) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, -1, 0, v2);
        rec(n_x, n_y, v2);
        vector<vector<bool>> v3 = v;
        dfs(x, y, 0, -1, v3);
        rec(n_x, n_y, v3);
        vector<vector<bool>> v4 = v;
        dfs(x, y, 1, 0, v4);
        rec(n_x, n_y, v4);
    }
    else if (arr[x][y] == 2) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, 0, -1, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, -1, 0, v2);
        dfs(x, y, 1, 0, v2);
        rec(n_x, n_y, v2);
    }
    else if (arr[x][y] == 3) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, 1, 0, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, 0, 1, v2);
        dfs(x, y, -1, 0, v2);
        rec(n_x, n_y, v2);
        vector<vector<bool>> v3 = v;
        dfs(x, y, 0, -1, v3);
        dfs(x, y, 1, 0, v3);
        rec(n_x, n_y, v3);
        vector<vector<bool>> v4 = v;
        dfs(x, y, 0, -1, v4);
        dfs(x, y, -1, 0, v4);
        rec(n_x, n_y, v4);
    }
    else if (arr[x][y] == 4) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, 1, 0, v1);
        dfs(x, y, -1, 0, v1);
        rec(n_x, n_y, v1);
        vector<vector<bool>> v2 = v;
        dfs(x, y, 0, -1, v2);
        dfs(x, y, 1, 0, v2);
        dfs(x, y, -1, 0, v2);
        rec(n_x, n_y, v2);
        vector<vector<bool>> v3 = v;
        dfs(x, y, 0, 1, v3);
        dfs(x, y, 0, -1, v3);
        dfs(x, y, 1, 0, v3);
        rec(n_x, n_y, v3);
        vector<vector<bool>> v4 = v;
        dfs(x, y, 0, 1, v4);
        dfs(x, y, 0, -1, v4);
        dfs(x, y, -1, 0, v4);
        rec(n_x, n_y, v4);
    }
    else if (arr[x][y] == 5) {
        vector<vector<bool>> v1 = v;
        dfs(x, y, 0, 1, v1);
        dfs(x, y, -1, 0, v1);
        dfs(x, y, 0, -1, v1);
        dfs(x, y, 1, 0, v1);
        rec(n_x, n_y, v1);
    }
    else {
        rec(n_x, n_y, v);  // 0, 6인 경우
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == 6) block[i][j] = true; // 벽의 경우 미리 true로 만든다.
        }
    }

    rec(0, 0, block);
    cout << n * m - mx;
}

 

 

 

 

향후 방침, 느낀 점

 

기업 코딩테스트에서 구현문제의 비중이 높아지는 만큼 많이 공부를 해야겠습니다.