[Baekjoon] 백준 14502번: 연구소 (c++)

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

14502번: 연구소

 

SSAFY 코테 준비 겸 한번 풀어봤는데,, 정답률 높아서 쉽게풀줄 알았지만,,, 쉽게는 못풀었다 ㅠ ㅠ

일단 벽을 3개 무조건 세워야 해서, 벽을 3개 세우는 모든 경우의 수를 생각해야함!

시간 제한은 2초에, 2차원 배열 크기는 (3 ≤ N, M ≤ 8) 이라서 시간초과는 무한루프 제외하고는 거의 안걸릴 듯 하다!

**벽이 무조건 3개 일때만 실행해주게 해야함. if(cnt == 3) 조건 추가 후 2에 대하여 DFS 후 0개수 출력

 

내가 푼 방법은

1. map배열에 입력 저장

2. DFS함수에서 벽 3개에 대하여 백트래킹

3. 벽 개수가 3일때만 DFS로 2의 상하좌우 모두 2로 업데이트

4. 남은 0의 개수 출력

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 10

int map[MAX][MAX] = {0,};
int origin[MAX][MAX] = {0,}; //복사본 배열
int Max = 0;
int result = 0;
int cnt = 0;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void DFS2(int N,int M, int y, int x); //2의 상하좌우를 모두 2로 업데이트하는 함수

void DFS(int N, int M, int i,int j){
    
    if(i != -1 && j != -1) {
        map[i][j] = 1;
        cnt++;
    }
    //벽 세우기
    for(int i=0;i<N;i++){
        if(cnt == 3)break;
        
        for(int j=0;j<M;j++){
            if(map[i][j] == 0){
                copy(&map[0][0], &map[0][0]+MAX*MAX, &origin[0][0]);
                DFS(N, M, i, j);
                origin[i][j] = 0;
                cnt--;
                copy(&origin[0][0], &origin[0][0]+MAX*MAX, &map[0][0]);
            }
        }
    }
    
    //cnt == 3 일때, 2로 DFS 후 0의 개수 구하기
    
    if(cnt == 3){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j] == 2) DFS2(N, M, i, j); //2의 상하좌우 모두 2로
            }
        }
        
        Max = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j] == 0) Max++;
            }
        }
        result = max(Max, result);
    }
}
void DFS2(int N,int M, int y, int x){
    
    if(map[y][x] == 0) map[y][x] = 2;
    
        if(map[y][x] == 2) {
            for(int k=0;k<4;k++){
                int py = dy[k] + y;
                int px = dx[k] + x;
                if((px < 0 || px >= M || py < 0 || py >= N) || map[py][px] != 0) continue;
                DFS2(N, M, py, px);
            }
        }
}

int main(){
//    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int N, M; //세로 N, 가로 M
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin >> map[i][j];
        }
    }
    copy(&map[0][0], &map[0][0]+MAX*MAX, &origin[0][0]);
    DFS(N, M, -1, -1);
    
    cout << result;
}