[Algorithm] 백준 15683번 감시

백준 15683번 감시

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

총 5종류의 CCTV가 있는데, 각 CCTV 별로 지켜볼 수 있는 방향이 정해져 있음.

    - 1번 : 상, 하, 좌, 우 중 1방향

    - 2번 : (상, 하) or (좌, 우) 중 하나  

    - 3번 : 상, 하, 좌, 우 중 2 방향 (대신,  선택된 두 방향은 인접해야함)

    - 4번 : 상, 하, 좌, 우 중 3방향

    - 5번 : 상, 하, 좌, 우 모든 방향

그 외에 6번은 '벽'이고, cctv 영상은 벽까지만 볼 수 있으며 벽을 건너서는 볼 수 없음.

이러한 CCTV 별 특성으로 인하여 각 별개로 처리를 해주어야 함.

문제 풀이

1. 초기에 데이터를 입력 받음과 동시에 각 cctv를 배열에 저장함. 

   이때, 5번 cctv는 별도로 저장함. (이유는 방향을 돌릴 필요가 없기 때문)

   그리고, cctv와 벽이 아닌 공간이 몇 칸인지 미리 세어놓는다. (map의 값이 0인 경우를 체크하면 됨)

2. 5번 cctv의 경우, 회전이 필요없기 때문에 초기에 먼저 map에 작업을 진행함.

3. 앞선 문제들과 동일하게 각 cctv마다 회전 가능 경우를 다 계산해보며 blind spot을 찾으면 됨.

실수 포인트 및 Vector/Array에 따른 Call 비교 정리

1. map을 이전 상태로 복원할 때, 재귀 특성을 고려하지 못하고 Global로 선언하여 고생함.

2. Vector를 사용할 때 Call By Reference / Call By Value 비교

    - Call By Refrence For Vector

        - 호출 부분 callFunc(arr)

        - 함수 부분 void callFunc(vector<int> &arr) 

    - Call By Value For Vector

        - 호출 부분 callFunc(arr)

        - 함수 부분 void callFunc(vector<int> &arr) 

3. 1차원 배열(1D Array)을 사용할 때 Call By Reference / Call By Value 비교

    - Call By Refrence For 1D Array

        - 호출 부분 callFunc(arr)

        - 함수 부분 void callFunc(int *arr) 

    - Call By Value For 1D Array

        - 호출 부분 callFunc(arr)

        - 함수 부분 void callFunc(int arr[]) 

3. 2차원 배열(2D Array)을 사용할 때 Call By Reference / Call By Value 비교

    - Call By Refrence For 2D Array

        - 호출 부분 callFunc(arr)

        - 함수 부분 void callFunc(int (*arr)[10])    → 반드시 열의 개수를 명시해줘야함!!!!!!!!!!!!!!

    - Call By Value For 2D Array

        - 호출 부분 callFunc(arr)

        - 함수 부분 void callFunc(int arr[][]) 

< 벡터, 1차원 배열, 2차원 배열 Call By Reference/Call By Value 코드 정리 >

		Call By Reference - 전달된 파라미터 값 변경시 적용됨.	Call By Value - 전달된 파라미터 값 변경시 적용 안됨.
벡터 (Vector)	함수 호출 부분	callFunc(arr)	callFunc(arr)
	함수 부분 (호출 받는 부분)	void callFunc(vector<int> &arr)	void callFunc(vector<int> &arr)
1차원 배열 (1D Array)	함수 호출 부분	callFunc(arr)	callFunc(arr)
	함수 부분 (호출 받는 부분)	void callFunc(int *arr)	void callFunc(int arr[])
2차원 배열 (2D Array)	함수 호출 부분	callFunc(arr)	callFunc(arr)
	함수 부분 (호출 받는 부분)	void callFunc(int (*arr)[10])	void callFunc(int arr[][])

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
 
#define ll long long int
 
using namespace std;
 
struct Position {
    int kind;
    int x;
    int y;
    Position() : x(0), y(0), kind(0) {}
    Position(int x, int y, int kind) :x(x), y(y), kind(kind) {}
};
 
int N, M;
int map[9][9];
vector<Position> cctv;
vector<Position> cctvFor5;
vector<bool> cctvVisit;
int cctvSize;
int blindCnt = 0;
 
// 1: one side, 2: two sides, 3: two sides(vertical), 4: three side, 5: four sides
// 1: 4 case, 2: 2 case, 3: 4 case, 4: 4 case, 5: 1 case
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
 
int answer = 64;
 
void copyMap2Temp(int (*temp)[9]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            temp[i][j] = map[i][j];
        }
    }
}
void copyTemp2Map(int(*temp)[9]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map[i][j] = temp[i][j];
        }
    }
}
 
int setMap(int i, Position cctv, int cnt) {
    int cx = dx[i] + cctv.x;
    int cy = dy[i] + cctv.y;
    while (1) {
        if (cx >= 0 && cy >= 0 && cx < N && cy < M && map[cx][cy] != 6) {
            if (map[cx][cy] == 0) {
                cnt--;
                map[cx][cy] = 7;
            }
        }
        else break;
        cx += dx[i];
        cy += dy[i];
    }
    return cnt;
}
void dfs(int pos, int cnt) {
    if (pos == cctvSize) {
        if (answer > cnt) {
            answer = cnt;
        }
        return;
    }
    switch (cctv[pos].kind)
    {
    case 1:
        for (int i = 0; i < 4; i++) {
            int temp[9][9];
            copyMap2Temp(temp);
            int cntOrigin = cnt;
            cnt = setMap(i, cctv[pos], cnt);
            dfs(pos + 1, cnt);
            cnt = cntOrigin;
            copyTemp2Map(temp);
        }
        break;
    case 2:
        for (int i = 0; i < 2; i++) {
            int temp[9][9];
            copyMap2Temp(temp);
            int cntOrigin = cnt;
            cnt = setMap(i, cctv[pos], cnt);
            cnt = setMap((i + 2) % 4, cctv[pos], cnt);
            dfs(pos + 1, cnt);
            cnt = cntOrigin;
            copyTemp2Map(temp);
        }
        break;
    case 3:
        for (int i = 0; i < 4; i++) {
            int temp[9][9];
            copyMap2Temp(temp);
            int cntOrigin = cnt;
            cnt = setMap(i, cctv[pos], cnt);
            cnt = setMap((i + 1) % 4, cctv[pos], cnt);
            dfs(pos + 1, cnt);
            cnt = cntOrigin;
            copyTemp2Map(temp);
        }
        break;
    case 4:
        for (int i = 0; i < 4; i++) {
            int temp[9][9];
            copyMap2Temp(temp);
            int cntOrigin = cnt;
            cnt = setMap(i, cctv[pos], cnt);
            cnt = setMap((i + 1) % 4, cctv[pos], cnt);
            cnt = setMap((i + 2) % 4, cctv[pos], cnt);
            dfs(pos + 1, cnt);
            cnt = cntOrigin;
            copyTemp2Map(temp);
        }
        break;
    }
}
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] > 0 && map[i][j] < 5) {
                cctv.push_back(Position(i, j, map[i][j]));
            }
            else if (map[i][j] == 5) {
                cctvFor5.push_back(Position(i, j, map[i][j]));
            }
            if (map[i][j] == 0) blindCnt++;
        }
    }
    cctvSize = cctv.size();
    cctvVisit.assign(cctvSize, false);
    for (int i = 0; i < cctvFor5.size(); i++) {
        for (int j = 0; j < 4; j++) {
            blindCnt = setMap(j, cctvFor5[i], blindCnt);
        }
    }
    dfs(0, blindCnt);
    cout << answer;
    return 0;
}