https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
1) 풀이
이 문제를 풀고 얻은 교훈이 있다면...
문제를 잘 읽자!!!! 😂
이 문제에서 진한 글씨로 강조된 부분이 있는데 난 문제를 대강 읽고 문제 풀는 데에 바빠서
강조되어있는줄도 몰랐다.... 이거 때문에 나처럼 헤매거나 틀리는 사람이 없었으면 좋겠다!!
이 문제는 내가 이전에 풀이해놨던 문제를 응용하면 된다!
미로의 제일 첫번째칸으로부터 마지막칸까지의 거리를 측정하는 문제라고 생각하면 되기 때문이다.
시작점에서부터 상하좌우로 탐색을 하고 방문을 한 뒤 방문한 칸은 탐색의 기준점으로부터 1만큼의 거리 차이가 나므로,
1을 더해주면 된다.
(이 말이 무슨 의미인지 이해가 어렵다면 이전 글을 보고 오자)
2021.06.01 - [알고리즘 | 자료구조/백준] - [백준/c++] 7576 - 토마토
그거 외에는 어려운 점이 딱히 없는 문제이지만, 앞서 말했듯이 문제를 잘 읽어야 하는 문제!!
다른 BFS 문제들과는 다르게, 이 문제에서는 미로가 string의 형태로 주어진다!
따라서 배열도 string으로 받아야 한다.....
나는 이걸 못 봐서 거의 하루동안 헤맸는데, 진짜 기초적인 자료형에 대한 실수로 하루종일 헤맸다는 거에
현타가 오더라.. 다들 주의하자!
2) 최종 소스코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dist[102][102]; //지나야 하는 칸수(거리) 저장
int nx[4] = { 0,1,0,-1 }; //상하좌우 x 좌표
int ny[4] = { 1,0,-1,0 }; //상하좌우 y 좌표
int n;
int m;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector<string>v; //미로 배열
cin >> n >> m;
for (int i = 0; i < n; i++) fill(dist[i], dist[i] + m, -1);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
v.push_back(s);
}
queue <pair<int, int>>q;
q.push({ 0,0 }); //첫번째 칸이 무조건 이동할 수 있는 칸이기 때문
dist[0][0] = 1; //시작위치를 1로 설정
while (!q.empty()) {
pair<int, int>cur = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int dx = cur.first + nx[k];
int dy = cur.second + ny[k];
if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue; //미로에서 벗어나면
if (dist[dx][dy] > 0 || v[dx][dy] != '1') continue; //방문했거나 이동할 수 있는 칸이 아닌 경우
dist[dx][dy] = dist[cur.first][cur.second] + 1;
q.push({ dx,dy });
}
}
cout << dist[n - 1][m - 1];
}
3) 참고자료
728x90
'Problem Solving > 백준' 카테고리의 다른 글
[백준/c++] 1697 - 숨바꼭질 (0) | 2021.06.06 |
---|---|
[백준/c++] 4179 - 불! (0) | 2021.06.04 |
[백준/c++] 7576 - 토마토 (0) | 2021.06.01 |
[백준/c++] 1926 - 그림 (0) | 2021.05.31 |
[백준/c++] 2217 - 로프 (0) | 2021.05.29 |