알고리즘 - BFS/DFS(연구소)

aquarius1997·2020년 5월 12일
1

Algorithm

목록 보기
2/9
  • 문제 출처 : 백준
  • 문제명 : 연구소 (#14520)
  • 분류 : DFS, BFS, Bruteforce
  • 언어 : C++
  • 체감 난이도 : ⭐⭐
  • 풀이 시간 : 22min
  • Fail Cnt : 0
  • BFS, DFS알고리즘을 모두 활용할 수 있는 문제

알고리즘 설계

1. 전역변수 / etc

#include <cstdio>
#include <queue>
using namespace std;

int g_table[10][10] = {0,}; //연구소 정보 ( 0:빈칸, 1:벽, 2:바이러스)
int g_N = 0; //연구소 세로크기
int g_M = 0; //연구소 가로 크기
int g_maxCnt = 0; //최대 안전 구역 개수
queue<int> g_Q; //세균의 위치를 저장하는 큐

2. 프로세스

  1. 모든 경우의 수에 대해 3개의 벽을 세운다
  2. 3개의 벽을 모두 세웠으면
    1) 현재 테이블 정보를 임시 저장하고
    2) 세균을 확산시키는 함수를 호출한다
    3) 안전 영역을 카운팅해서, 최대 안전 영역 개수를 업데이트 한다
    4) 원래 테이블 정보로 원상 복구한다

3. 3개의 벽을 세우는 DFS 함수

/// 3개의 벽을 세운다
/// @param row 벽을 세울 위치
/// @param col 벽을 세울 위치
/// @param cnt 함수 실행시 세우는 걸 포함해, 여태까지 세운 벽의 수
void constructing(int row, int col, int cnt) {
    int r, c;
    int tempT[10][10] = {0,};
    int safeCnt = 0;
    
    //벽을 세운다
    g_table[row][col] = 1;
    
    if(cnt == 3) {
        //현재 테이블 정보를 임시 저장
        for(r=0; r<g_N; r++) {
            for(c=0; c<g_M; c++) {
                tempT[r][c] = g_table[r][c];
                if(g_table[r][c] == 2) { g_Q.push(r);   g_Q.push(c);}   //동시에 세균 위치 큐에 삽입
            }
        }
        
        //세균 확산 함수 호출
        bfs_spreading();
        
        //안전영역 최대 크기 구해서 업데이트
        for(r=0; r<g_N; r++) {
            for(c=0; c<g_M; c++) {
                if(g_table[r][c] == 0) { safeCnt++; }
            }
        }
        if(safeCnt > g_maxCnt) { g_maxCnt = safeCnt;}

        
        //원래 테이블 정보로 원상 복구
        for(r=0; r<g_N; r++) {
            for(c=0; c<g_M; c++) {
                g_table[r][c] = tempT[r][c];
            }
        }
    } else {
        for(c=col+1; c<g_M; c++) {
            if(g_table[row][c] == 0) { constructing(row, c, cnt+1);}
        }
        for(r=row+1; r<g_N; r++) {
            for(c=0; c<g_M; c++) {
                if(g_table[r][c] == 0) { constructing(r, c, cnt+1);}
            }
        }
    }
    
    //벽 세운걸 없앤다
    g_table[row][col] = 0;
}

재귀 호출을 통해 3개의 벽을 세운다.

4. 세균을 확산 시키는 DFS 함수

void bfs_spreading(void) {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    int r, c;
    
    while(!g_Q.empty()) {
        r = g_Q.front();    g_Q.pop();
        c = g_Q.front();    g_Q.pop();
        
        for(int d=0; d<4; d++) {
            if(r+dx[d] >= 0 && r+dx[d] < g_N) {
                if(c+dy[d] >= 0 && c+dy[d] < g_M) {   //테이블 범위에 속하고
                    if(g_table[r+dx[d]][c+dy[d]] == 0) {    //빈칸이면
                        g_Q.push(r+dx[d]);  g_Q.push(c+dy[d]);  //큐에 삽입
                        g_table[r+dx[d]][c+dy[d]] = 2;  //세균으로 저장
                    }
                }
            }
        }   //end for(d)
        
    }
}

dx와 dy배열을 통해, 기준 위치로부터 상하좌우 테이블 정보를 확인한다.

  • dx[0], dy[0] -> 기준 위치의 위쪽
  • dx[1], dy[1] -> 기준 위치의 아래쪽
  • dx[2], dy[2] -> 기준 위치의 왼쪽
  • dx[3], dy[3] -> 기준 위치의 오른쪽
profile
안녕하세요😀😀

0개의 댓글