포스팅 할 문제는 백준2206 벽 부수고 이동하기라는 문제입니다.
문제링크: https://www.acmicpc.net/problem/2206
해당문제의 난이도는 골드 4입니다.
최단 경로를 구해야 하는 문제이고+간선의 가중치가 없기때문에 전형적인 bfs문제라 볼수 있습니다.
이 문제에서 처리하기 어려운 부분은 벽을 한개 부수고 이동할 수 있다는 것 입니다.
처음에는 벽을 부신적 있는지만 큐에 좌표값과 함께 저장하면 될거 같았지만, 한가지 간과한것이 있었습니다.
그것은 bfs로 문제를 풀면서 중복접근을 하지 않도록 배열을 하나 만들어 중복방문을 방지하도록 코드를 작성하는데, 그것을 벽을 부순적 있는 좌표값과 벽을 부순적 없는 배열을 따로 관리해줘야 한다는것 입니다.
벽을 부순적이 있거나 없을경우 방문여부를 확인해주는 배열을 3차원 배열로 선언해 따로 관리했습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int dx[4]={-1,0,0,1};
int dy[4]={0,1,-1,0};
//구조체 선언
struct qu{
int x,y,cnt,ch;
};
queue<qu>q;
int arr[1001][1001];
int n,m;
int ch[1001][1001][2];
int res=2147000000;
void bfs(){
//x좌표 ,y좌표 ,cnt는 탈출하기 까지 이동한 수, flag는 벽을 부순적 있는지 확인용 변수
//flag=0일경우 아직 벽을 부수지 x
int x,y,cnt,flag;
while(!q.empty()){
x=q.front().x;
y=q.front().y;
cnt=q.front().cnt;
flag=q.front().ch;
q.pop();
//목표지점에 도착했을 경우
if(x==n&&y==m){
res=min(res,cnt);
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>0&&ny>0&&nx<=n&&ny<=m){
//이동할 수 있는 곳으로 이동 ,벽을 부순적 x
if(arr[nx][ny]==0&&ch[nx][ny][0]==0&&flag==0){
q.push({nx,ny,cnt+1,flag});
ch[nx][ny][0]=1;
}
//이동할 수 있는곳으로, 벽을 부순적 있음
else if(arr[nx][ny]==0&&ch[nx][ny][1]==0&&flag==1){
q.push({nx,ny,cnt+1,flag});
ch[nx][ny][1]=1;
}
//벽을 부순적없지만 벽을 부실예정
if(arr[nx][ny]==1&&ch[nx][ny][1]==0&&flag==0){
q.push({nx,ny,cnt+1,1});
ch[nx][ny][1]=1;
}
}
}
}
}
int main(){
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
cin>>n>>m;
string s;
for(int i=1;i<=n;i++){
cin>>s;
for(int j=1;j<=m;j++){
arr[i][j]=s[j-1]-'0';
}
}
q.push({1,1,1,0});
ch[1][1][0]=1;
bfs();
//탈출구로 갈 수 없는 경우
if(res!=2147000000){
cout<<res<<"\n";
}
else{
cout<<-1<<"\n";
}
return 0;
}
주석을 참고해 코드를 보면 될거 같습니다!
😊
