[백준 2178] 미로 탐색

문제 링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

격자상의 그래프에서 bfs 탐색을 하는 문제이다

 

기존 bfs와 다른 점이라면

 

1. 그래프 이동을 격자상의 상하좌우로 한다. (dx, dy 배열)

 

2. 격자 한칸이 노드이므로 격자 정보가 x,y 두가지 정수로 다뤄진다 (node 구조체)

---

#include <iostream>
#include <queue>
#define n_ 100+5
using namespace std;

int n, m;
int arr[n_][n_];
int dp[n_][n_];
// 상하좌우 빠른 탐색을 위한 dx,dy 배열
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

typedef struct Node {
	int x, y;
}node;

queue<node> q;	// bfs용 큐 선언, 정보단위는 구조체 node

// bfs 탐색 코드
void bfs(int x, int y) {
	q.push({ 0, 0 });	// 시작하는 노드부터 큐에 push
	dp[0][0] = 1;		// 0,0에서 시작하는 시간은 1

	while (!q.empty()) {
		node now = q.front();	// 큐의 맨 앞 노드
		q.pop();

		for (int i = 0; i < 4; i++) {	// 상하좌우 dx,dy배열 활용
			node nxt = { now.x + dx[i], now.y + dy[i] };	// 다음 목표격자를 구조체로 미리 생성
			if (nxt.x < 0 || nxt.x == n || nxt.y < 0 || nxt.y == m) continue;	// 범위 밖이면 제외
			if (arr[nxt.x][nxt.y] == 0) continue;	// 벽 위치면 제외
			if (dp[nxt.x][nxt.y] != 0 && dp[nxt.x][nxt.y] <= dp[now.x][now.y] + 1) continue;	// 이미 더 빨리 도달했으면 제외

			dp[nxt.x][nxt.y] = dp[now.x][now.y] + 1;	// 걸리는 시간 업데이트
			q.push({ nxt.x, nxt.y });	// 큐에 push
		}
	}
}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}

	bfs(0, 0); // 0,0에서 미로탐색 시작
	cout << dp[n - 1][m - 1] << endl;	//미로의 출구까지 최단거리
}