[C++] 2178번 : 미로탐색

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

2178번: 미로 탐색

풀이

우선 첫 번째는 입력에서 볼드체로 '붙어서'를 강조하는 모습을 볼 수 있습니다.

string으로 받아야겠다는 생각은 했지만, getline으로 받을 생각이었습니다.

이후.. for(auto c : s)를 통해 접근하고자 했지만 이렇게 구현할 경우 index에 접근이 불가하여 미로의 개념이 구현되지 않습니다.

이 부분은 고민하다가 해답을 참고했습니다.

string s[100] 이라 함은 string 객체를 담는 1차원 배열 s를 선언하는 것과 같습니다.

이를 이용하면 마치 char 2차원 배열을 선언하는 것과 같은 효과를 가집니다. 실제 index 접근도 2차원 배열처럼 할 수 있습니다. (적고보니 char 2차원 배열로 구현하면 됬겠네요.)

 

두 번째 그렇담 최단거리를 어떻게 구할 것인가?입니다. 따로 변수를 선언하여 모든 거리를 저장해놓는 것은 불가능합니다.

조금만 다르게 생각하면?

미로 하나를 더 만들어 각 distance를 누적합 시키면 구하고자 하는 distance를 얻을 수 있습니다.

마침 반드시 0,0에서 시작하여 N-1,M-1에서 끝나는군요.

 

내 코드

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int vis[101][101];
int dis[101][101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	string s[102]; //102개의 string object를 저장
	for (int i = 0; i < N; i++) {
		cin >> s[i];
	}
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	dis[0][0] = 1; vis[0][0] = 1;
			while (!q.empty()) {
				pair<int, int> cur = q.front(); q.pop();
				for(int dir = 0; dir < 4; dir++) {
					int x = cur.X + dx[dir];
					int y = cur.Y + dy[dir];
					if (x < 0 || y < 0 || x >= N || y >= M) continue;
					if (vis[x][y] || s[x][y] == '0') continue;
					q.push(make_pair(x, y));
					dis[x][y] = dis[cur.X][cur.Y] + 1;
					vis[x][y] = 1;
				}
			}
	cout << dis[N-1][M-1];
}