더블릿 - 댐

문제 링크

BFS의 정말 정석적인 문제인 것 같다. 미로 찾기 문제와 탐색 방법은 거의 같은데 다른 점은 원하는 만큼 확장한 다음에, 그 갯수를 구한다는 것이다. 

너비우선탐색을 진행해가며 해당 좌표가 맵을 벗어나는지 아닌지, 길인지 아닌지, 그리고 범람했는지 아닌지를 검사한다. 

위 조건을 충족하면 해당 위치의 카운트를 증가시키고 큐에 넣어서 탐색을 계속 이어가고, 카운트가 만약 댐 건설 시간과 일치하면 해당 위치에 댐을 지어야 하므로 댐의 갯수인 ret 변수를 증가시킨다. 

만약 배열 탐색을 끝까지 했음에도 ret변수가 0이면, 댐으로 막지 못했다는 뜻이므로 "OH, MY GOD" 문자열을 출력하고, 0이 아닐 경우엔 막는 데 성공했다는 것이므로 ret의 값을 출력한다. 먼저 STL의 큐를 이용해서 구현했었는데, 라이브러리에 의존적이지 않도록 배열을 이용한 큐를 또 따로 작성해서 구현도 해보았다. 

밑은 이를 구현한 코드이다.

STL을 이용한 BFS

#include <cstdio>
#include <queue>
using namespace std;
//맵의 크기 t, 맵 변수 a, 댐 시간 변수 k, 홍수 넘침 여부 변수 flood 
int t,a[101][101],k,flood[101][101]={0,},x,y;
//해당 좌표 정보를 저장하는 구조체 
typedef struct{
    int x,y,count;  
}Point;
//bfs를 위한 큐 
queue<Point> q;
//해당 위치의 상대 좌표. 물의 확산 비교를 위해 
int relPos[4][2]= {{1,0},{-1,0},{0,1,},{0,-1}};
int bfs(){
    int ret=0;
    // 초기 좌표의 정보 값을 저장한 구조체를 만들고, 큐에 넣는다. 
    Point p = {x,y,0}; flood[y][x] = 1;
    q.push(p);  
    // bfs 시작 
    while(!q.empty()){
        p = q.front(); q.pop();
        for(int i=0; i<4;i++){
            int px = p.x + relPos[i][0];
            int py = p.y + relPos[i][1];
            //보드판의 범위 안에 있고, 방문한 적이 없고, 건물이 아니어야 한다. 
            if(px>0&&py>0 && px<t+1&&py<t+1 && flood[py][px]==0 && a[py][px]==0){
                //해당 거리에 홍수가 났음을 체크 
                flood[py][px] = 1;
                Point np = {px,py,p.count+1};
                //만약 이 위치에서 댐을 막았으면 ret의 카운트를 증가. 
                if(p.count+1==k) ret++;
                q.push(np);
            }
        }
    }   
    return ret;
}
int main(){
    scanf("%d",&t);
    // 맵 초기화 
    for(int i =1; i<=t;i++){
        for(int j=1;j<=t;j++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d %d",&x,&y);
    scanf("%d",&k);
    int ret = bfs();
    printf(ret==0?"OH, MY GOD":"%d",ret);
}

배열을 이용해 큐를 구현해 푼 BFS

#include <cstdio>
//맵의 크기 t, 맵변수 a, 댐 시간 변수 k, 홍수 넘침여부 변수 flood 
int t,a[101][101],k,flood[101][101]={0,},x,y;
//해당 좌표 정보를 저장하는 구조체 
typedef struct{
    int x,y,count;  
}Point;

//bfs를 위한 큐 
Point q[10000];
int front=0,rear=0;
void enqueue(Point p){
    q[rear++] = p;
}
Point dequeue(){
    return q[front++];
}
bool isEmpty(){
    return front==rear;
}

//해당 위치의 상대좌표. 물의 확산 비교를 위해 
int relPos[4][2]= {{1,0},{-1,0},{0,1,},{0,-1}};
int bfs(){
    int ret=0;
    // 초기 좌표의 정보값을 저장한 구조체를 만들고, 큐에 넣는다. 
    Point p = {x,y,0}; flood[y][x] = 1;
    enqueue(p); 
    // bfs 시작 
    while(!isEmpty()){
        p = dequeue();
        for(int i=0; i<4;i++){
            int px = p.x + relPos[i][0];
            int py = p.y + relPos[i][1];
            //보드판의 범위안에 있고, 방문한적이 없고, 건물이 아니어야한다. 
            if(px>0&&py>0 && px<t+1&&py<t+1 && flood[py][px]==0 && a[py][px]==0){
                //해당 거리에 홍수가 났음을 체크 
                flood[py][px] = 1;
                Point np = {px,py,p.count+1};
                //만약 이 위치에서 댐을 막았으면 ret의 카운트를 증가. 
                if(p.count+1==k) ret++;
                enqueue(np);
            }
        }
    }   
    return ret;
}
int main(){
    scanf("%d",&t);
    // 맵 초기화 
    for(int i =1; i<=t;i++){
        for(int j=1;j<=t;j++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d %d",&x,&y);
    scanf("%d",&k);
    int ret = bfs();
    printf(ret==0?"OH, MY GOD":"%d",ret);
}