[C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이)

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

2206: 벽 부수고 이동하기

구현!

 사실 원래의 BFS를 이용한 최단거리 알고리즘에서 조금만 추가하면 쉽게 풀 수 있는 문제이다. 여기서 중요한 것은 tuple안의 4개의 원소를 집어넣어 각각 x좌표, y좌표, 벽을 뚫고 지나갔는지에 대한 여부, 현재까지의 거리를 저장해야 하는 것이다. 또한 중요한 것이 visit 배열인데 기존의 2차원으로만 표현하면 안되고 3차원으로 표현하여 벽을 뚫고 지나갔는지에 대한 여부에 따라 visit 표시를 따로 해줘야한다.

 

Tuple!

 tuple은 vector가 두개의 변수만 저장할 수 있는 반면에 3개이상의 변수를 넣을 수 있어 구조체로 표현할 수 있는 것을 조금 더 간편하게 만들어주는 내장 STL이다. 여기서는 queue를 정의할 때 tuple을 이용하여 4개의 변수를 넣어주었다. 그 이유로는 queue에 지나간 지점, 즉 x좌표와 y좌표를 넣어주어야 하고 (변수 2개) 벽을 기존에 부쉈는지에 따라 벽을 또 부술 수 있는지 확인해야하므로 벽의 부숨 여부를 넣어줘야 하며 (변수 1개), 현재까지 온 거리를 저장하기 위해서 변수가 필요하다(변수 1개).

 

queue<tuple<int,int,int,int>>q1

ex) q1.push(make_tuple(nx,ny,wall_visit,distance+1))

 

 특히 변수 3번째 자리를 주목해야하는데 벽을 이미 부쉈다면 1을 안부쉈다면 0을 넣어주었다. 이렇게 넣어준 이유는 도달한 지점을 queue에 넣어도 되는지 안되는지에 대한 해결책을 주기 때문이다.

 

Visit!

 이 문제와 같이 최단거리 문제를 풀때는 BFS로 구현하여 푸는데 이때 항상 필요한 것이 visit 배열이다. 이미 지나간 점을 또 방문했을 경우는 최단거리가 될 수 없다고 판단하여 queue에 넣어주면 안되는데, 그것을 visit 배열에 저장하여 판단한다.

 그런데 이 문제의 경우는 기존에 지나간 점을 또 방문했을 때도 최단거리가 될 수도 있는데 그 이유는 벽을 뚫고 갈 수 있기 떄문에 어떤 경우에서는 이미 지나간 점을 지나고 벽을 뚫고 가는 것이 최단거리가 될 수도 있기 때문이다. 따라서 구현의 문제가 생기는데 이 문제를 visit 배열을 3차원으로 정의하여 풀었다.

 

int visit_once[1001][1001][2];

ex) visit_once[ny][nx][wall_visit]=1

 

 만약 맨 마지막 []이 0이라면 아직 벽을 뚫지 않은 경로인 것이고 1이라면 벽을 뚫은 경우이다. 벽을 뚫고 지나간 경로와 벽을 뚫고 지나가지 않는 경로를 각각 visit 배열에 저장하여 기록해주고 이 기록을 저장하였다가 마지막에 최단거리를 구하면 된다. 

 

Queue!

 queue에 넣어주는 조건도 잘 살펴봐야한다. 

 

queue에 넣을 수 없는 조건

1. graph 범위 바깥 지점

 if(nx<1 ||nx>x_max ||ny<1 ||ny>y_max)

 

2. 벽 뚫은 경우와 뚫지 않는 경우 각각에서의 경로의 이미 방문했을 경우

if(visit_once[ny][nx][wall_visit]==1)

 

3. 이미 벽을 뚫었는데 벽을 만났을 경우

if(wall_visit==1 && graph[ny][nx]==1)

 

이 같은 경우에는 continue를  사용해 현재 반복문을 종료하고 그 다음 반복문으로 넘겨서 queue의 삽입을 막아야한다.

 

queue에 넣을 때 구분해야하는 조건

1. 벽을 안뚫은 경우에 벽을 만난 경우

if(wall_visit==0 && graph[ny][nx]==1)

 

2. 벽이 아닌 곳을 만난 경우 (이미 벽을 만났든 안만났든)

if(graph[ny][nx]==0)

 

각각 1,2 번 조건에 맞게 queue의 값을 update 하여 만들어주면 push 해주면 된다

 

마지막으로 도착점 끝까지 도달해야 not_enter의 값이 1로 바뀌게 되고 만약 도달하지 못할 경우에는 -1을 출력하도록 하면 된다.

 

 

소스코드

 

#include <iostream>
#include <algorithm>
#include<queue>
#include<tuple>
#include <string.h>
#include <map>


using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int not_enter=0;//끝까지 왔나 안왔나

int graph[1001][1001];
queue<tuple<int,int,int,int>>q1; //좌표와 벽을 부섰는지의 여부!
int visit_once[1001][1001][3]; //visit도 3차원으로 만들어서 벽을 부수고 온 애랑 아닌 애랑 구별했으면 됐음...
int x_coordinate[4]={0,1,0,-1};
int y_coordinate[4]={-1,0,1,0};

int BFS(int x_max,int y_max) //벽을 뚫었을 떄랑 안뚫었을 경우를 나눠서 같은 queue에 넣어주기(visit한 것을 따로 생각하기)
{
  int min_distance=10000001;
  q1.push(make_tuple(1,1,0,1));
  visit_once[1][1][0]=1;
  while(q1.size()!=0){
    int nx=get<0>(q1.front());
    int ny=get<1>(q1.front());
    int distance=get<3>(q1.front());
    if(nx==x_max && ny==y_max) //만약 끝에 지점에 도달하면 최댓값인지 확인해보고 pop
    {
      not_enter=1;
      if(distance<min_distance)
        min_distance=distance;
      q1.pop();
      continue;
    }
    
    for(int i=0;i<4;i++){         
      nx=get<0>(q1.front())+x_coordinate[i];
      ny=get<1>(q1.front())+y_coordinate[i];
      int wall_visit=get<2>(q1.front());
      distance=get<3>(q1.front());

      if(nx<1 ||nx>x_max ||ny<1 ||ny>y_max) //graph 밖에 공간
        continue;      
      if(visit_once[ny][nx][wall_visit]==1) //이미 벽 뚫었을때/안뚫었을때 각각 지나간 곳
        continue;            
      if(wall_visit==1 && graph[ny][nx]==1) //이미 벽을 뚫었는데 벽을 만났을 때
        continue;      
        
      visit_once[ny][nx][wall_visit]=1;
      if(wall_visit==0 && graph[ny][nx]==1) //벽은 안뚫었는데 뚫어야할때    
        q1.push(make_tuple(nx,ny,1,distance+1));      
        
      if(graph[ny][nx]==0) //벽이 없는 곳으로 갈때      
        q1.push(make_tuple(nx,ny,wall_visit,distance+1));               
    }    
    q1.pop();      
  }
  return min_distance;
}

int main() {
 int y_max,x_max;
  cin>>y_max>>x_max;
  for(int j=1;j<=y_max;j++)
    {
      string arr;
      cin>>arr;
      for(int i=1;i<=x_max;i++){
        if(arr[i-1]=='0')
          graph[j][i]=0;
        else
          graph[j][i]=1;
      }
    }  
  int result=BFS(x_max,y_max);
  if(not_enter==0)
    cout<<-1;
  else
   cout<<result;
}