문제 링크



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



'Algorithm > Problems' 카테고리의 다른 글

백준 - 2294 동전 2  (0) 2016.03.07
백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1005 ACM Craft  (0) 2016.02.27
더블릿 - 댐  (0) 2016.02.26
알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25


문제 링크


나는 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%라 엄청 긴장하고 풀었는데 그 정도 까지의 문제는 아니었던 것 같다.

'Algorithm > Problems' 카테고리의 다른 글

백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28
더블릿 - 댐  (0) 2016.02.26
알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25
알고스팟 - MORSE, DICT  (0) 2016.02.25


문제 링크

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




'Algorithm > Problems' 카테고리의 다른 글

백준 - 1697 숨바꼭질  (1) 2016.02.28
백준 - 1005 ACM Craft  (0) 2016.02.27
알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25
알고스팟 - MORSE, DICT  (0) 2016.02.25
백준 - 1963 소수경로  (0) 2016.02.24


문제 링크


문제에서 풀이 방법을 가르쳐주었기 때문에 그냥 그 로직대로 따라가 풀었다. 코드 라인이 쓸대없이 길어져서 귀찮았던 것 같다.

나는 에라스토테네스의 체로 소수들을 전부 구하고 시작했는데, 풀고 보니 에라스토테네스의 체같은건 필요 없고, 그냥 평범하게 소수를 구하거나 그때그때 판별해도 상관없는 문제였다...

어쨌든 각 각 자리수를 바꿀수 있는 한도 내에서 바꾼 뒤, 해당 숫자의 이전 방문 여부와 에라스토테네스의 체로 구한 배열에서 소수인지 판별하고 큐에 넣어서 반복해주었다.

처음엔 그냥 숫자로만 풀이하려다가 숫자를 배열로, 배열을 숫자로 바꿔서 풀이하였다. 근데 바꾸나 마나였단 생각이 든다...

밑에는 풀이 코드이다.




#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue> 
using namespace std;
int t, x, y, a[10000] = { 0, }, visited[10000] = { 0, }, num[4];
typedef struct {
    int num, count;
}Prime;
queue<Prime> q;
//에라토스테네스의 체로 9999이하의 소수들을 모두 구한다. 
void era(int n) {
    int i;
    while (true) {
        for (i = 2; i <= n; i++)
            if (a[i] == 0) break;
        if (i>n) return;
        a[i] = 1;
        for (int j = 2; j*i <= n; j++) {
            if (a[i*j] == 0) {
                a[i*j] = 2;
            }
        }
    }
}
//배열을 숫자로 바꾼다.
int numToArr(){
    int ret=0;
    for(int i=0; i<4;i++){
        ret+=num[i]*pow(10,3-i);
    }
    return ret;
}
//자리수를 한번 바꾼 값이 소수인지 판별하고, 소수이면 큐에 넣는다.
void check(int i,int count){
    int k = i==0?0:1;
    int bak = num[i];
    while(num[i]-1>=1-k){
        num[i] -=1;
        int n = numToArr();
        if(a[n]==1&&visited[n]==0){
            Prime p1 = {n,count+1};
            visited[n]=1;
            q.push(p1);
        }
    }
    num[i]=bak;
    while(num[i]+1<=9){
        num[i] +=1;
        int n = numToArr();
        if(a[n]==1&&visited[n]==0){
            Prime p1 = {n,count+1};
            visited[n]=1;
            q.push(p1);
        }
    }
    num[i]=bak;
}
//너비우선 탐색.
int dfs() {
    Prime p = { x,0 };
    q.push(p);
    while (!q.empty()) {
        p = q.front(); q.pop();
        //값을 찾았으면 카운트값을 반환 
        if (p.num == y) return p.count;
        //숫자를 배열로 변경 
        for(int i=0;i<4;i++){
            num[i] = p.num/pow(10,3-i);
            p.num = p.num-num[i]*pow(10,3-i);
        }
        for(int i=0;i<4;i++){
            check(i,p.count);
        }
    }
    //못찾았으면 -1을 반환한다. 
    return -1;
}
int main() {
    era(9999);
    scanf("%d",&t);
    while(t--){
        scanf("%d %d", &x, &y);
        int ret = dfs();
        printf(ret==-1?"Impossible\n":"%d\n",ret);
        while(!q.empty())q.pop();
        memset(visited,0,sizeof(visited));
    }
}



'Algorithm > Problems' 카테고리의 다른 글

알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25
알고스팟 - MORSE, DICT  (0) 2016.02.25
백준 - 2960 에라토스테네스의 체  (1) 2016.02.24
백준 - 1541 잃어버린 괄호  (0) 2016.02.23
백준 - 1946 신입사원  (0) 2016.02.23

+ Recent posts