BOJ
BOJ::17836 공주님을 구해라!
BOJ Gold 5
BOJ::17836 공주님을 구해라!
[BOJ] : https://www.acmicpc.net/problem/17836
- Level : Gold 5
시사점
- 너비 우선 탐색 기본 문제입니다.
이해(3)
- (1,1)에서 출발해서 (N,M)에 도달하려 할때 최단거리를 구하는 문제입니다.
- 한 칸의 이동에 1초가 소모되고, 최소 시간을 출력하는 문제입니다.
- 문제에서 주어진 최대 시간 이내에 도달하지 못하면 Fail을 출력합니다.
설계(2)
- 기본적인 BFS 틀에서,
- 그람을 만나는 경우만 예외처리합니다.
- 그람을 만나는 겨웅 벽이 무시되므로 해당 위치에서 공주의 위치사이의 거리를 맨해튼 거리로 바로 구합니다.
- 또한, 걸어서 벽을 피해서 가는 경우도 존재하고, 그람을 만나서 벽을 뚫고 가는 경우도 존재하므로
- 큐를 다 돌때까지 기다려줘야합니다.
시간 복잡도
- O(NM), 단순 BFS 문제입니다.
공간 복잡도
구현(5)
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 100;
const int INF = 987654321;
struct cell{int x; int y; int mv;};
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
int n, m, mxmv;
int sx, sy, ex, ey;
int a[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
queue<cell> q; // x, y, mv
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=m);}
void solve(){
int ret = INF;
visited[sx][sy] = true;
q.push({sx, sy, 0});
while(!q.empty()){
int x = q.front().x, y = q.front().y, mv = q.front().mv; q.pop();
if(x == ex && y == ey){
ret = min(ret, mv);
continue;
}
for(int i = 0; i < 4; i++){
int nx = x+dx[i], ny = y+dy[i];
if(over(nx, ny) || visited[nx][ny] || a[nx][ny] == 1) continue;
visited[nx][ny] = true;
if(a[nx][ny] == 0){
q.push({nx, ny, mv+1});
}else{
int dist = abs(nx - ex) + abs(ny - ey);
ret = min(dist + 1 + mv, ret);
}
}
}
if(ret <= mxmv)cout << ret <<"\n";
else cout << "Fail\n";
}
int main(){
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> mxmv;
sx = 0, sy = 0, ex = n-1, ey = m-1;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> a[i][j];
solve();
return 0;
}