#2178 미로 탐색

# 문제

# 입력 및 출력

# 풀이

처음엔 DFS로 풀어야 하나 했는데

분류를 보니까 BFS로 풀라고 적혀있어서 BFS로 풀어봤다

시작점의 상하좌우를 보면서 길이 있는지 확인해야하는데

이때 상하좌우를 보는 걸 하나하나 구현해야 싶어서 또 구글링,,ㅋㅋㅋㅋ

찾아보니까 dx, dy배열을 만들어서 반복문으로 구현한 사람이 있어서 그 코드를 따라했다

큐에 넣고 빼는 동작 뿐이라 코드가 길진 않다

 

코드 아래 블로그 참고

https://cocoon1787.tistory.com/115

[C/C++] 백준 2178번 미로탐색 (BFS, DFS)

 

1) 시작점 (1,1)를 큐에 넣기

2) 큐의 첫번째 순서쌍의 상하좌우 접근 -> 길이 있으면 방문했다고 하고 큐에 넣은 다음 dis 배열을 현재 +1로 설정

3) 2번을 큐가 빌 때까지 반복

---

나는 위의 사진처럼 조건문으로 배열 인덱스 초과 에러를 잡기 보다는 배열의 크기를 상하, 좌우로 한 칸씩 늘려서

크기를 102칸으로 만들고 늘린 칸들은 전부 길이 없다는 뜻인 0으로 채워놓았다

그러면 따로 추가 조건문 없이 배열 인덱스 초과 에러를 잡을 수 있음

 

#include <iostream>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
int miro[102][102];
int dis[102][102];
int visit[102][102];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
queue<pair<int, int>> q;

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%1d", &miro[i][j]);
		}
	}
	dis[1][1] = 1;
	visit[1][1] = 1;
	q.push(make_pair(1, 1));
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (!visit[nx][ny] && miro[nx][ny]) {
				visit[nx][ny] = 1;
				q.push(make_pair(nx, ny));
				dis[nx][ny] = dis[x][y] + 1;
			}
		}
	}
	cout << dis[N][M] << "\n";
}