백준[15683]감시

삼성 SW역량테스트 문제이다. 

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

4가지 방향을 기준으로 재귀 DFS를 통해 구현하는 문제이다. 

예를들어  카메라가 하나있을 경우 가능한 4가지 방향에 대해 모두 탐색하면 된다.

그렇다면 카메라가 2개 있을때는 어떻게 처리해야 할까?

1, 2, 3, 4 를 동서남북 방향이라 잡고, A, B라는 카메라고 있다고 하자 표를 간단하게 그린다면

A	B
1	1
1	2
1	3
1	4

    

A	B
2	1
2	2
2	3
2	4

etc.........

이런식으로 나타낼 수 있다. 이 카메라수와 방향에 따른 조합을 모두 나타내었다면 문제의 내용대로 구현을 하면 된다.

참고로 필자는 이 구현부분을 모두 구현하는 바람에 코드가 길고 깔끔하지 않다. 카메라 종류별로 중복 방향이 있는 부분을 처리하여 좀 더 깔끔하게 구현할 수 있다.

#include<stdio.h>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>
#include<deque>
 
using namespace std;
 
int n, m, arr[10][10],visit[9],cnt,map[10][10],gg[9],gg2[10];
int x[10], y[10],z[10], k, chk,ans=987654321;
 
 
void five(int a,int b) {
        int kx = a, ky = b;
        //cout << kx << " " << ky << endl;
        for (int v = ky; v < m; v++) {
            ky++;
            if (arr[kx][ky] == 6) break;
            arr[kx][ky] = 8;
        }
        ky = b;
        
        for (int v = ky - 1; v >= 0; v--) {
            ky--;
            if (arr[kx][ky] == 6) break;
            arr[kx][ky] = 8;
        }
        ky = b;
        for (int v = kx; v < n; v++) {
            kx++;
            if (arr[kx][ky] == 6) break;
            arr[kx][ky] = 8;
        }
        kx = a;
        for (int v = kx - 1; v >= 0; v--) {
            kx--;
            if (arr[kx][ky] == 6) break;
            arr[kx][ky] = 8;
        }
}
 
void dfs(int tt) {
    if (tt == cnt) {
        
        for (int i = 0; i < k; i++) {
            five(gg[i], gg2[i]);
        }  
        for (int a = 0; a < cnt; a++) {
            if (z[a] == 1) {
                if (visit[a] == 1) {
                    int kx = x[a], ky = y[a];
                    for (int v = ky; v < m; v++) {
                        ky++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
                else if (visit[a] == 2) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx; v < n; v++) {
                        kx++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
                else if (visit[a] == 3) {
                    int kx = x[a], ky = y[a];
                    for (int v = ky-1; v >= 0; v--) {
                        ky--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
                else if (visit[a] == 4) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx-1; v >= 0; v--) {
                        kx--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
            }
 
            else if (z[a] == 2) {
                if (visit[a] == 1 || visit[a] == 3) {
                    int kx = x[a], ky = y[a];
                    for (int v = ky; v < m; v++) {
                        ky++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    ky = y[a];
                    for (int v = ky-1; v >= 0; v--) {
                        ky--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
                else if (visit[a] == 2 || visit[a] == 4) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx; v < n; v++) {
                        kx++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = kx-1; v >= 0; v--) {
                        kx--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
            }
 
            else if (z[a] == 3) {
                if (visit[a] == 1) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx-1; v >= 0; v--) {
                        kx--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = ky; v < m; v++) {
                        ky++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
 
                else if (visit[a] == 2) {
                    int kx = x[a], ky = y[a];
                    for (int v = ky; v < m; v++) {
                        ky++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    ky = y[a];
                    for (int v = kx; v < n; v++) {
                        kx++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
 
                else if (visit[a] == 3) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx; v < n; v++) {
                        kx++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = ky-1; v >= 0; v--) {
                        ky--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
 
                else if (visit[a] == 4) {
                    int kx = x[a], ky = y[a];
                    for (int v = ky-1; v >= 0; v--) {
                        ky--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    ky = y[a];
                    for (int v = kx-1; v >= 0; v--) {
                        kx--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
            }
 
            else if (z[a] == 4) {
                if (visit[a] == 1) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx-1; v >= 0; v--) {
                        kx--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = ky; v < m; v++) {
                        ky++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    ky = y[a];
                    for (int v = ky-1; v >= 0; v--) {
                        ky--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
                else if (visit[a] == 2) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx-1; v >= 0; v--) {
                        kx--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = ky; v < m; v++) {
                        ky++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    ky = y[a];
                    for (int v = kx; v < n; v++) {
                        kx++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
                else if (visit[a] == 3) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx; v < n; v++) {
                        kx++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = ky; v < m; v++) {
                        ky++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    ky = y[a];
                    for (int v = ky-1; v >= 0; v--) {
                        ky--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
                else if (visit[a] == 4) {
                    int kx = x[a], ky = y[a];
                    for (int v = kx-1; v >= 0; v--) {
                        kx--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = kx; v < n; v++) {
                        kx++;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                    kx = x[a];
                    for (int v = ky-1; v >= 0; v--) {
                        ky--;
                        if (arr[kx][ky] == 6) break;
                        arr[kx][ky] = 8;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0) {
                    chk++;
                }
            }
        }
        
        ans = min(ans, chk);
        chk = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = map[i][j];
            }
        }
        return;
    }
    for (int i = 0; i < 4; i++) {
        visit[tt] = i + 1;
        dfs(tt + 1);
        visit[tt] = 0;
    }
}
 
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
            map[i][j] = arr[i][j];
            if (arr[i][j] != 6 && arr[i][j] != 0 && arr[i][j] != 5) {
                x[cnt] = i;
                y[cnt] = j;
                z[cnt] = arr[i][j];
                //cout << x[cnt] << " " << y[cnt] << " " << cnt << endl;
                cnt++;
            }
            if (arr[i][j] == 5) {
                gg[k] = i;
                gg2[k] = j;
                k++;
            }
        }
    }
    dfs(0);
    printf("%d", ans);
    return 0;
}