[그래프]-조건 추가된 문제들

1. 벽부수고 이동하기 (백준 2206)

2. 미로만들기 (백준 2665)

3. 말이 되고픈 원숭이(백준 1600)

---------------------------------------------------

1. 벽부수고 이동하기 (백준 2206)

NxM행렬이 있을 때, (1,1)에서 (N,N)까지 벽을 피해서 이동할 수 있는 최소이동수를 찾으시오. 단, 벽을 한 번 깨는 찬스 사용가능.

풀이

- (1.1)에서 출발해서 BFS처럼 (N,N)까지 이동. 

- 일반 BFS와 달리, 다음 방문 노드를 구하는 것을, 상/하/좌/우 방문하는 것으로 처리

- 상/하/좌/우 노드에서, 

  . 박스를 벗어나는 노드들에 대해서는 스킵

    if(y1<1 || y1>N || x1<1 || x1>M) continue;

  . 방문하지 않았던 노드들만 처리 

- 방문하는 노드들에 대해서 dist를 관리하는데, 찬스를 사용하지 않고 도달한 dist와, 찬스를 사용하여 도달한 dist를 구분하는 게 핵심

- 만약 방문한 노드가 방이라면, dist는 선조 노드 + 1

           if(a[y1][x1]=='0' && dist[y1][x1][z]==-1) {

                dist[y1][x1][z] = dist[y][x][z] + 1;

                q.push(P(y1,x1,z));             

            }

-만약 방문한 노드가 벽이라면, 선조가 찬스를 사용하지 않았어야 하고, dist[y1][x1][1]값이 증가됨

            if(a[y1][x1]=='1' && z==0 && dist[y1][x1][1]==-1){

                dist[y1][x1][1] = dist[y][x][z]+1;

                q.push(P(y1,x1,1));             

            }

-(N,N)까지의 최소 이동회수를 구하는 것이므로, (N,N)노드가 발견되는 즉시 그 때의 dist[N][N]값을 출력하면 됨.

  (문제 조건에 따라서, 이렇게 큐에서 뽑아낸 노드가 (N,N)일 때 즉시 출력하면 안되고, 여러 경로에서 접근되어 갱신이 완료된 후의 값을 추력해야 할 때도 있다. 이 경우는 큐에 있는 모든 것을 처리하고 난 후 (N,N)에 있는 값을 출력해야 함)

소스

#include <stdio.h>

#include <string.h>

#include <queue>

 

using namespace std;

 

struct P{

    int y,x,z; //z:chance 사용여부 

    P(){};

    P(int _y, int _x, int _z){y=_y; x=_x; z=_z;};

};

 

char a[1002][1002],dy[4]={0,0,1,-1}, dx[4]={1,-1,0,0};

int N,M,dist[1001][1001][2];

int main(){

    int i,j;

    memset(dist,-1,sizeof(dist));   

    scanf("%d %d",&N,&M);

    for(i=1;i<=N;++i)    scanf("%s",&a[i][1]);

     

    dist[1][1][0]=1;

    dist[1][1][1]=1;

    queue<P> q;

    q.push(P(1,1,0));

    while(!q.empty()){

        P u = q.front(); q.pop();

        int y=u.y; int x=u.x; int z=u.z;        

        if(y==N && x==M){

            printf("%d\n",dist[N][M][z]); return 0;

        }

        for(i=0;i<4;++i){

            int y1=y+dy[i]; int x1=x+dx[i];         

            if(y1<1 || y1>N || x1<1 || x1>M) continue;

            if(a[y1][x1]=='0' && dist[y1][x1][z]==-1) {

                dist[y1][x1][z] = dist[y][x][z] + 1;

                q.push(P(y1,x1,z));             

            }

            if(a[y1][x1]=='1' && z==0 && dist[y1][x1][1]==-1){

                dist[y1][x1][1] = dist[y][x][z]+1;

                q.push(P(y1,x1,1));             

            }

        }

    }   

    printf("-1");

    return 0;

}

2. 미로만들기 (백준 2665)

nxn모양의 미로가 있고, 벽과 방으로 이루어져 있을 때, (1,1)에서 (n,n)까지 최소의 벽을 허물면서 가려고 할 때, 허무는 최소 벽수를 구하시오.

BFS처럼 가는데, 주변에 있는 상/하/좌/우로 움직이면서 (n,n)으로 이동 (박스밖으로는 못 나가게 처리)

if(y1<1 || y1>n || x1<1 || x1>n) continue;

- 이동하면서 방문회수를 vtd[][]에 기록하는데, 지금의 선조로부터 오는 경로보다 더 짧은 경로가 이미 기록되어 있다면, 지금경로 무시

if(vtd[y1][x1]!=-1 && vtd[y1][x1] <= vtd[y][x]) continue;

- 방문한 노드가 벽이면 vtd를 1증가. 아니면 그대로 선조의 vtd를 따라감

- vtd[n][n]값이 최종 답이 되는데, (n,n)이 최초로 발견되었을 때의 vtd[n][n]값을 취하면 안되고, 큐에 있는 모든것이 처리되서, 

  모든 경로에서 (n,n)까지 오는것이 처리되고 난 후의 vtd[n][n]값을 출력해야 함.

소스

#include <stdio.h>

#include <string.h>

#include <queue>

#include <algorithm>

using namespace std;

typedef pair<int,int> P; //y,x

int  n, vtd[51][51]; 

char a[52][52]; //1:가능 0:불가

char dy[4]={0,0,1,-1},dx[4]={1,-1,0,0};

int main(){

int i,j;

memset(vtd,-1,sizeof(vtd));

scanf("%d",&n);

for(i=1;i<=n;++i) scanf("%s",&a[i][1]);

vtd[1][1]=0;

queue<P> q;

q.push(make_pair(1,1));

int y,x;

while(!q.empty()){

P u = q.front(); q.pop();

y = u.first; x=u.second;

//if(y==n && x==n) printf("%d\n",vtd[n][n]);

for(i=0;i<4;++i){

int y1 = y+dy[i]; int x1 = x+dx[i];

if(y1<1 || y1>n || x1<1 || x1>n) continue;

if(vtd[y1][x1]!=-1 && vtd[y1][x1] <= vtd[y][x]) continue;

vtd[y1][x1] = (a[y1][x1]=='1') ? vtd[y][x] : vtd[y][x] + 1;

q.push(make_pair(y1,x1));

}

}

printf("%d\n",vtd[n][n]);

return 0;

}

3. 말이 되고픈 원숭이 (백준 1600)

기본적으로 상하좌우로 움직일 수 있고, 또한 주어진 K번 한도 내에서 장기의 '마'처럼 이동할 수 있을 때, (1,1)에서 (H.W)까지의 최동 이동회수는? 말판에는 이동불가한 벽들도 있음

풀이

- BFS처럼 찾아가는데 단, 한 노드에서 이웃 노드로의 이동을 상하좌우 혹은 '마'처럼 이동

- 각 노드의 방문여부를 나타내는 vtd를 3차원배열로 만든다. y,x 좌표별로 '마'찬스를 사용여부 설정

  즉, 각 노드를 방문할 때마다 cnt를 증가시키고 또한 '마'를 사용했다면 '마'를 사용했다는 체크 설정

  cnt[y1][x1] = cnt[y][x] + 1;

  vtd[y1][x1][z+1]=true

- 큐에 넣는 노드 정보에도 현재까지 사용한 '마'사용회수 기록

  q.push(make_pair(make_pair(y1,x1),z+1)); 

- 만약 큐에서 꺼낸 노드의 '마'사용회수가 주어진 찬스 한도인 K 이상이면, '마'처럼 이동은 불가하고, 상하좌우로만 이동

- 큐에서 꺼낸 노드가 (H,W)이면, 바로 그 때의 cnt[H][W] 출력하면 됨.

소스

#include <stdio.h>

#include <queue>

#include <algorithm>

using namespace std;

typedef pair<pair<int,int>,int> P; //(y,x,count_of_chanceUse)

int K,W,H;

char a[202][202];

short cnt[201][201];

bool vtd[201][201][31];

char dy[4]={0,0,1,-1}, dx[4]={1,-1,0,0};

char hy[8]={-2,-2,-1,-1,1,1,2,2}, hx[8]={-1,1,-2,2,-2,2,-1,1};

     

int main(){

int i,j;

scanf("%d \n %d %d",&K,&W,&H);

for(i=1;i<=H;++i) for(j=1;j<=W;++j) scanf("%d",&a[i][j]);

queue<P> q;

q.push(make_pair(make_pair(1,1),0)) ;

while(!q.empty()){

P u = q.front(); q.pop();

int y=u.first.first; int x=u.first.second; int z=u.second;

if(y==H && x==W){

printf("%d\n",cnt[y][x]);

return 0;

}

for(i=0;i<4;++i){

int y1=y+dy[i]; int x1=x+dx[i];

if(a[y1][x1]==1 || y1<1 || y1>H || x1<1 || x1>W) continue;

if(!vtd[y1][x1][z]){

cnt[y1][x1] = cnt[y][x]+1;

vtd[y1][x1][z]=true;

q.push(make_pair(make_pair(y1,x1),z)); 

}

}

if(z>=K) continue;

for(i=0;i<8;++i){

int y1=y+hy[i]; int x1=x+hx[i];

if(a[y1][x1]==1 || y1<1 || y1>H || x1<1 || x1>W) continue;

if(!vtd[y1][x1][z+1]){

cnt[y1][x1] = cnt[y][x]+1;

vtd[y1][x1][z+1]=true;

q.push(make_pair(make_pair(y1,x1),z+1)); 

}

}

}

printf("-1\n");

return 0;

}

-끝-