728x90
문제
N×M크기의 배열로 표현되는 미로가 있다.
1 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int N, M;
int arr[101][101];
int cache[101][101];
int ans = 9999999;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
void bfs(int x, int y){
queue<pair<int,int>> q;
memset(cache, 0, sizeof(cache));
q.push({x,y});
cache[x][y] = 1;
while(!q.empty()){
pair<int, int> here = q.front();
q.pop();
for(int i=0; i<4; ++i){
int nx = here.first + dir[i][0];
int ny = here.second + dir[i][1];
if(nx == N && ny == M){
int there = cache[here.first][here.second];
if(cache[N][M] == 0){
cache[N][M] = there + 1;
}
else{
if(cache[N][M] > there+1){
cache[N][M] = there+1;
}
}
continue;
}
if(arr[nx][ny] == 1 && cache[nx][ny] == 0){
q.push({nx, ny});
cache[nx][ny] = cache[here.first][here.second] + 1;
}
}
}
}
int main(void){
cin >> N >> M;
for(int i=1; i<N+1; ++i){
for(int j=1; j<M+1; ++j){
scanf("%1d", &arr[i][j]);
}
}
bfs(1, 1);
cout << cache[N][M];
return 0;
}
이 문제는 BFS + 유사 dp 를 활용해서 풀었다.
bfs는 위에서부터 하나하나씩 차근차근 내려오기 때문에 최적해를 찾을 수 있다.
이 문제의 경우 dfs를 찾으면 경로가 아주 많을 수 있어 시간복잡도가 커질수 있지만 bfs는 최단거리(최적해)에 유용하기 때문에 bfs를 활용해 주었다.
또한 최소값을 찾아주는 문제이기 때문에 cache를 활용해서 dp라기엔 애매하지만 각 위치마다 이동한 값을 저장시켜 가장 최소값을 구해주었다.
dfs와 bfs를 사용하는 경우를 잘 파악해야 된다.
bfs는 최단거리를 찾을 때 유용하다!!
728x90
반응형
'PS > DFS, BFS' 카테고리의 다른 글
[7576] 토마토 (0) | 2023.06.03 |
---|---|
[1697] 숨바꼭질 (1) | 2023.05.30 |
[2667] 단지번호붙이기 (0) | 2023.05.23 |
[24444] 알고리즘 수업 - 너비 우선 탐색 1 (1) | 2023.05.23 |
[24479] 알고리즘 수업 - 깊이 우선 탐색 1 (1) | 2023.05.23 |