[BOJ] 14502번 연구소 문제풀이 (C++)

2017.10.6에 쓰여진 글입니다.

---

 

문제링크

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

14502번: 연구소

 

풀이방법

푸는 방법은 완탐으로 다돌면서 벽을 3개를 세운담에 바이러스 퍼뜨리고 

안전구역 영역을 찾고 이걸 계속 반복하면서 최대값을 찾으면 됨

그리고 2가지의 풀이방법으로 풀었는데 둘이 비슷하지만 조금 다름.

1번 소스코드는 dfs를 이용한 풀이이고,

2번 소스코드는 bfs를 이용한 풀이. 이때 큐가 사용되었음.

같은 문제라도 최대한 여러방법으로 풀어보는것이 좋은것 같음.

 

추가적으로 참고할 사항은 소스코드2에서 wall함수인데,

만약 0 0 0 처럼 일자로벽을 세운다고 가정하고 숫자 순서대로 벽을 세운다고 하면

1 2 3 

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

이 6개의 방법 모두 결국 일자로 벽을 세워주는 거고 같은 방법이니까 굳이 할필요가 없음.

따라서 

1번벽을 세우고 현재좌표보다 뒤에있는 좌표에서만 2번벽을 세움

2번벽을 세우고 현재좌표보다 뒤에있는 좌표에서만 3번벽을 세움

이게 무슨말이냐면

0 0 0 0 0 0 이렇게 빈공간이 있어서 벽을 3개를 세우려고 한다면

1 0 2 0 0 3 이렇게 세워졌다고 하면 그다음번은

1 3 0 2 0 0 이렇게는 세울수가없음. 왜냐면 3번벽은 2번벽좌표보다 뒤에잇어야하기때문

따라서 

1 0 0 2 3 0 부터 벽을 세우기 시작해야함. 

이런식으로 코드를 바꿔주니까 156MS정도에서 44MS로 시간이 대폭 줌.

왜 이런짓을 했냐면 만약에 N,M이 커진다면? 

만약에 세울수있는 벽의 수가 커진다면?

이와같은 문제는 바로 시간초과로 가는 지름길이고 최적화의 중요성을 보여주는 예시라고 생각함.

이래서 시간초과가 발생하는 문제는

숫자 만들기, 벌꿀채취 이런 류의 문제들이있음.

중복을 제거해주지않고 계속 돌린다면 시간초과의 길로 가버림.

재귀 짤때 시간초과를 항상 생각해주면서 짜자.

 

소스코드

소스코드1 dfs 이용

#include <iostream>
#include <algorithm>    //max 함수 위한 헤더
 
using namespace std;
 
enum { BLANK = 0, WALL, VIRUS };
 
int map[8][8];
int tmp_map[8][8];
bool visited[8][8];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int virus_x[10];//바이러스 위치 x좌표
int virus_y[10];//바이러스 위치 y좌표
 
void Init_virus_xy()
{
    for (int i = 0; i < 10; i++) {
        virus_x[i] = 0;
        virus_y[i] = 0;
    }
}
 
void Init_map()
{
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++) {
            map[i][j] = 0;
            tmp_map[i][j] = 0;
        }
}
 
void Init_visited()
{
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            visited[i][j] = false;
}
 
void Copy_map()
{
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            tmp_map[i][j] = map[i][j];
}
 
void Infection(int cur_x, int cur_y, int x_size, int y_size)
{
    if (0 <= cur_x&&cur_x < x_size &&
        0 <= cur_y&&cur_y < y_size &&
        !visited[cur_x][cur_y]) {
        visited[cur_x][cur_y] = true;
        for (int i = 0; i < 4; i++)
            if (0 <= cur_x + dx[i] && cur_x + dx[i] < x_size &&
                0 <= cur_y + dy[i] && cur_y + dy[i] < y_size &&
                tmp_map[cur_x + dx[i]][cur_y + dy[i]] == BLANK) {
                tmp_map[cur_x + dx[i]][cur_y + dy[i]] = VIRUS;
                Infection(cur_x + dx[i], cur_y + dy[i], x_size, y_size);    //바이러스 퍼뜨리기
            }
    }
 
}
 
int Check(int x_size, int y_size)
{
    int count = 0;
    for (int i = 0; i < x_size; i++)
        for (int j = 0; j < y_size; j++)
            if (tmp_map[i][j] == BLANK)
                count++;
 
    return count;
}
 
int New_map(int cur_x, int cur_y, int x_size, int y_size, int virus_count)
{
    int Answer = 0;
    for (int i = 0; i < x_size; i++)
        for (int j = 0; j < y_size; j++)
            if (map[i][j] == BLANK) {
                map[i][j] = WALL;      //벽을 세움 (2개째)
                for (int k = 0; k < x_size; k++)
                    for (int m = 0; m < y_size; m++)
                        if (map[k][m] == BLANK) {
                            map[k][m] = WALL;      //벽을 세움 3개째
                            Copy_map();
                            Init_visited();        //바이러스 퍼뜨리기 전에 방문을 초기화함, 바이러스 퍼뜨리면서 방문체크를 할것이기 때문
                            for (int n = 0; n < virus_count; n++)
                                Infection(virus_x[n], virus_y[n], x_size, y_size);            //바이러스 퍼뜨림
                                                                                              //바이러스 아까 저장해놓은 좌표에서 하나씩 퍼뜨리기
                            Answer = max(Answer, Check(x_size, y_size));   //안전구역의 갯수를 세자, 
                                                                           //원래 답과 비교해서 더 큰 안전구역값 반환
                            map[k][m] = BLANK;      //3번째 벽을 원상복귀시킴
                        }
                map[i][j] = BLANK;      //2번째벽을 원상복구시킴   
            }
 
    return Answer;
}
 
int main()
{
    int N, M;
    int Answer = 0;
    int virus_count = 0;
 
    cin >> N >> M;
    Init_map();      //맵초기화
    Init_virus_xy();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];      //맵 입력
            if (map[i][j] == VIRUS) {        //바이러스 좌표를 저장해놓는다
                virus_x[virus_count] = i;
                virus_y[virus_count] = j;
                virus_count++;                //바이러스 갯수
            }
        }
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == BLANK) {      //0인 빈칸이 있으면 
                map[i][j] = WALL;   //복사본에 해당 i,j에 벽을 세운다
                Answer = max(Answer, New_map(i, j, N, M, virus_count));      //New_map 함수 호출, 안전구역이 가장 큰 경우를 답으로!
                map[i][j] = BLANK;   //1번째 벽을 원상복구시킴
            }
    cout << Answer << endl;
}

 

소스코드2 bfs, 큐(queue) 이용

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
 
using namespace std;
 
enum { BLANK = 0, WALL = 1, VIRUS = 2 };
 
int N, M;
int map[8][8];
int tmp_map[8][8];
bool visited[8][8];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
queue < pair < int, int > > q;
int Answer;
 
void Init()                //맵초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            map[i][j] = BLANK;
}
 
void Init_visited()        //방문초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            visited[i][j] = false;
}
 
void copy_map()            //맵복사
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            tmp_map[i][j] = map[i][j];
}
 
void infection()        //감염시킴
{
    Init_visited();        //방문초기화해주고
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (tmp_map[i][j] == VIRUS) {    //만약 바이러스면
                q.push(make_pair(i, j));    //큐에 넣어줌
                visited[i][j] = true;        //방문표시도해줌
            }
    while (!q.empty()) {                //큐 빌때까지 돌림
        int cur_x = q.front().first;    //현재 좌표 저장하고
        int cur_y = q.front().second;
        q.pop();                        //큐빼주고
        for (int i = 0; i < 4; i++) {    //상하좌우 돌리기
            int new_x = cur_x + dx[i];
            int new_y = cur_y + dy[i];
            if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M    //범위안에있고
                && !visited[new_x][new_y]                        //방문안했고
                && tmp_map[new_x][new_y] == BLANK) {            //감염가능한구역이면
                q.push(make_pair(new_x, new_y));                //큐에넣고
                visited[new_x][new_y] = true;                    //방문표시해주고
                tmp_map[new_x][new_y] = VIRUS;    //새로운좌표 바이러스로 감염시킴
            }
        }
    }
}
 
void solve()
{
    int area_cnt = 0;    //영역 카운트 0으로
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (tmp_map[i][j] == BLANK)
                area_cnt++;        //안전구역있으면 체크해줌
    Answer = max(Answer, area_cnt);        //정답이랑 영역카운트랑 더 큰 값 정답에 저장
}
 
void wall(int cnt,int cur_x,int cur_y)
{
    if (cnt == 3) {        //벽을 3개 세웠으면
        copy_map();        //맵복사
        infection();    //감염시키고
        solve();        //안전구역 체크
        return;
    }
    for (int j = cur_y; j < M; j++)
        if (map[cur_x][j] == BLANK) {
            map[cur_x][j] = WALL;        //벽세움
            wall(cnt + 1, cur_x, j);            //다음벽세우러 들어감
            map[cur_x][j] = BLANK;        //벽원상복구시켜줌
        }
    for (int i = cur_x+1; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == BLANK) {
                map[i][j] = WALL;        //벽세움
                wall(cnt + 1, i, j);            //다음벽세우러 들어감
                map[i][j] = BLANK;        //벽원상복구시켜줌
            }
}
 
int main()
{
    cin >> N >> M;        //입력받고
    Init();                //맵초기화
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];    //맵입력받기
    Answer = 0;        //정답초기화
    wall(0,0,0);        //wall함수 호출
    cout << Answer << endl;    //정답출력
 
    return 0;
}