문제 풀이
미로가 주어진 경우에 최단 경로를 구하는 문제이다.
아주 간단하게 최단경로를 구하는 문제이므로 BFS를 생각해볼 수 있다. 미로 상태를 2차원 배열 map에 bool 형태로 저장해두고(1 : true, 0 : false) $(1,1)$에서부터 $(N,M)$까지 true인 경우에만 탐색을 진행하면 된다.
시행착오
한 점으로 이동하는 방법이 여러가지일 수 있는데, 최소로 가는 경로로 업데이트 해주는 작업을 빼먹어서 값이 이상하게 나왔다. 다행히 한 번 컴파일 하고 알아차려서 디버깅하는데 시간이 적게 걸렸다.
코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
bool map[102][102];
int dis[101][101];
void bfs()
{
queue<pair<int, int>> q;
q.push(make_pair(1,1));
dis[1][1] = 1;
while(!q.empty())
{
pair<int,int> x;
x = q.front();
q.pop();
if(map[x.first][x.second+1]&&dis[x.first][x.second+1] > dis[x.first][x.second] + 1)
{
dis[x.first][x.second+1] = dis[x.first][x.second] + 1;
q.push(make_pair(x.first,x.second+1));
}
if(map[x.first+1][x.second]&&dis[x.first+1][x.second] > dis[x.first][x.second] + 1)
{
dis[x.first+1][x.second] = dis[x.first][x.second] + 1;
q.push(make_pair(x.first+1,x.second));
}
if(map[x.first][x.second-1]&&dis[x.first][x.second-1] > dis[x.first][x.second] + 1)
{
dis[x.first][x.second-1] = dis[x.first][x.second] + 1;
q.push(make_pair(x.first,x.second-1));
}
if(map[x.first-1][x.second]&&dis[x.first-1][x.second] > dis[x.first][x.second] + 1)
{
dis[x.first-1][x.second] = dis[x.first][x.second] + 1;
q.push(make_pair(x.first-1,x.second));
}
}
}
int main()
{
char state;
int N,M,i,j;
cin>>N>>M;
for(i=1;i<=N;i++)
{
for(j=1;j<=M;j++)
{
cin>>state;
if(state == '1')
{
map[j][i] = true;
}
}
}
memset(dis,10000,sizeof(dis));
bfs();
cout<<dis[M][N];
}
'Computer Science > BOJ' 카테고리의 다른 글
BOJ 1011. Fly me to the Alpha Centauri (1) | 2024.02.08 |
---|---|
BOJ 1654. 랜선 자르기 (0) | 2024.01.27 |
BOJ 1713. 후보 추천하기 (1) | 2024.01.06 |
BOJ 2302. 극장 좌석 (1) | 2023.12.17 |
BOJ 17615. 볼 모으기 (1) | 2023.12.17 |