화투의 개발 블로그

문제 링크

BFS 문제다. 값의 범위만 조심하면 어려울 것 없는 문제였다.

다만 지금까지 풀었던 BFS는 방문을 체크하는 변수와 현재 탐색 레벨의 변수를 따로 두고 풀었는데, 이번에는 이전 문제와는 다르게,방문을 체크하는 변수 안에 현재 탐색 레벨을 담았다. 다만 그 체크를 위해 맨 처음 값이 1로 시작해야 했기에, 마지막 결과 값에서 1을 빼서 반환했다.

밑은 내가 풀이한 코드이다. 

#include <cstdio>
#include <queue>
using namespace std;
//기존에 풀었던 BFS문제와는 다르게, visited 배열에 현재 레벨도 저장하였다. 
int n, k, visited[100001]={0,};
queue<int> q;
int bfs(){
    //큐에 수빈의 위치를 넣고, 방문을 체크하는 배열에 1을 넣어준다. 
    q.push(n); visited[n] = 1;
    //bfs 시작 
    while(!q.empty()){
        //큐를 꺼내고, 수빈이가 동생의 위치에 도달했는지 확인한다. 
        int p = q.front(); q.pop();
        if(p==k) return visited[p]-1;
        
        //수빈이 현재 위치 -1이 0보다 크거나 같고, 방문한 적이 없을경우. 현재 값에서 레벨을 1증가시켜 큐에 넣어준다. 
        if(p-1>=0&&visited[p-1]==0){
            visited[p-1] = visited[p]+1;
            q.push(p-1);
        }
        //수빈이 현재 위치의 +1이 100,000보다 작거나 같고, 방문한 적이 없을경우.
        if(p+1<=100000&&visited[p+1]==0){
            visited[p+1] = visited[p]+1;
            q.push(p+1);
        }
        //수빈이 현재 위치의 2배가 0보다 크거나 같고, 방문한 적이 없을경우.
        if(2*p<=100000&&visited[2*p]==0){
            visited[2*p] = visited[p]+1;
            q.push(2*p);
        }
    }
}
int main(){
    scanf("%d %d",&n,&k);
    printf("%d",bfs());
}

문제 링크

나는 BFS로 푼 문제이다. 시작 점이 꼭 1번 건물이 아닐 수도 있으므로 모든 건물의 정보를 입력 받는 과정에, 그 이전 단계가 있는 건물들은 시작 건물이 아니라 단정하고 시작 건물들이 가능한 건물들은 처음에 큐에 미리 넣어주고 BFS를 진행하였다.

이 문제에 함정이 있는 게, 문제는 최소 시간을 구하라고 하는데 따지고 보면 그냥 그 단계까지 누적 최고 건설 시간들만 구해주면 된다. 왜냐하면 특정 단계 건물을 짓기 위해서는 선행 건물들을 모두 지어야 하는데, 선행 건물들 중에 건설 시간이 짧은 것을 아무리 먼저 지어도 건설 시간이 긴 건물이 지어지기 전까지는 그 특정 단계의 건물을 지을 수 없기 때문이다. 

이 로직 대로 코드를 짰는데, 처음에 문제를 풀 때 시간 초과가 났었다. 뭐가 문제인가 고민을 해봤더니, 초기에는 build배열에서 첫 번째 인덱스는 현재 건물, 두 번째 인덱스는 다른 건물을 인덱스로 두고, 그 배열 값이 참이면 경로가 존재한다고 하고 풀이를 진행했었다.

이 과정에서 매 루프마다 그때의 건물 배열을 1부터, n까지 전부 다 경로 검사를 진행해야 하니 시간 초과가 일어난 것이다. 그래서 일일이 해당 인덱스에 저장하는 방법을 버리고 해당 건물이 가진 경로의 개수를 path 배열 에다가 저장하고, 배열의 1 인덱스부터 다음 경로들을 저장하는 방법을 택하니 시간 초과에서 벗어났다. 

밑은 위의 과정대로 작성한 코드이다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm> 
using namespace std;
//각 건물의 인덱스 0번에 건설 시간을 저장한다. 
int t,build[1001][1001],isFirst[1001]={0,},value[1001],path[1001];
int x,y,n,k,w;
queue<int> q; 
 
int bfs(){  
    int ret = 0;
    //시작점이 가능한 것들을 전부 큐에 넣는다. 
    for(int i=1;i<=n;i++){
        if(isFirst[i]==0){
            q.push(i);
            //초기 빌드의 누적 비용을 건설 비용으로 초기화한다. 
            value[i] = build[i][0];
        }
    }   
    //BFS를 진행한다. 
    while(!q.empty()){
        //큐에서 인덱스를 하나씩 꺼내서, 다음 경로에서 가능한 것을 찾는다.
         int p = q.front(); q.pop();
        //원하는 건물에 도달하면, 최대 값을 넣어준다.
         if(p==w) ret = max(ret,value[p]);
         else{
         for(int i=1;i<=path[p];i++){
            if(build[p][i]>=1){
                int a = build[p][i];
                // 다음 빌드를 짓는 데에 드는 최대 비용을 구한다. 최대 비용이 안되면 enqueue 하지 않는다.  
                if(value[a] < value[p]+build[a][0]){
                    value[a] =value[p] + build[a][0];
                    q.push(a);
                 }
             }
         }
        }
    }
    return ret;
}
int main(){
    scanf("%d",&t);
    while(t--){
        //초기화// 
        for(int i=0; i<q.size();i++) q.pop();
        memset(build,0,sizeof(build));
        memset(value,0,sizeof(value));
        memset(isFirst,0,sizeof(isFirst));
        memset(length,0,sizeof(length));
        
        //건물의 갯수와 건설 규칙 순서 
        scanf("%d %d",&n,&k);
        //각 건물 0번 인덱스에 건물의 건설 시간을 저장한다. 
        for(int i=1;i<=n;i++)
            scanf("%d",&build[i][0]);
       //각 건물의 경로 초기화           
        for(int i=0;i<k;i++){
            scanf("%d %d",&x,&y);
            int a = ++path[x];
            //해당 경로가 있음을 표시하기위해  1을 저장한다. 
            build[x][a] = y;
            //또한 해당 경로가 시작점이 가능한지 아닌지도 체크를 해야된다.
            isFirst[y] = 1; 
        } 
        //목표 건물 
        scanf("%d",&w);
        printf("%d\n",bfs());       
    } 
}

변수가 쓸대 없이 많아진 것 같아 나중에 시간을 내서 리팩토링을 해야겠단 생각이 든다.

정답률이 15%라 엄청 긴장하고 풀었는데 그 정도 까지의 문제는 아니었던 것 같다.

문제 링크

#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);
}

#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);
}