[백준/c++] 2178 - 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

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) 참고자료