문제 이해
- N * M 크기의 배열이 주어진다.
- 배열의 값이 1이면 이동 가능하고, 0일경우 불가능하다.
- (1,1)에서 출발하여 (N, M)까지 가야한다.
- 이 때 지나야하는 최소의 칸 수를 구하라.
<조건>
- 시간 제한: 1초
- 메모리 제한: 192MB
<입력>
- N: 행 (2 ~ 100, 10^2)
- M: 열 (2 ~ 100, 10^2)
- 미로의 맵(공백없이 주어진다)
<출력>
- (1, 1)에서 (N, M)까지 갈 때 지나는 칸의 최솟값을 구하라.
※ 단, 입력은 항상 도착 가능하도록 주어진다.
문제 풀이
지금 되돌아보면 너무 답답하지만
끝까지 빠르게 도달해야 하니까 깊이 우선 탐색을 해야겠다! 그럼 DFS네 라고 생각했다.
깊이 우선 탐색이 돌아갈 수 있다는 걸 전혀 생각하지 못했다...
하지만 코드로 구현해 본 결과 돌아가는 경우가 있기에 당연히 원하는 출력이 나오지 않았다.
그래서 나온 접근이
그럼 각 경우의 수를 다 해보고 최솟값을 갱신하면 되겠네
백트래킹을 해야겠다
라는 것이다...
이 접근의 경우 출력은 원하는 값이 나왔지만 시간 초과로 AC를 받지 못했다.
마지막으로 생각난 것이 바로 문제의 정해인 BFS이다.
예시를 하나 들어보면
1 1 1
1 1 1
1 1 1
위의 배열이 주어지고 (1,1)에서 (3,3)까지 경로를 구한다면
1 2 3
2 3 4
3 4 5
위와 같이 지나온 칸 수 배열이 생길 것이다.
이번 문제와 같이 지나온 칸 수의 최솟값 문제의 경우 BFS를 이용하는 게 맞았던 것이다...
전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321
struct Pos{
int y;
int x;
int cnt;
};
char map[105][105];
bool visited[105][105];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
int n, m, ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>map[i][j];
}
}
queue<Pos> q;
q.push({1, 1, 1});
while(!q.empty()){
int y = q.front().y;
int x = q.front().x;
int cnt = q.front().cnt;
q.pop();
if(y == n && x == m){
ans = cnt;
}
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny >= 1 && ny <= n && nx >= 1 && nx <= m){
if(!visited[ny][nx] && map[ny][nx] == '1'){
visited[ny][nx] = true;
q.push({ny, nx, cnt+1});
}
}
}
}
cout<<ans;
return 0;
}
배운 점
그저 단순하게 생각하고 무작정 구현하려고 하는 버릇을 반성할 수 있었던 문제이다.
또한, 그래프 탐색에서 지나온 칸 수의 최솟값을 구하는 문제는 BFS를 사용해야 함을 배울 수 있었다.