백준 2178번: 미로 탐색

백준 온라인 저지(BOJ) 2178번 문제

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

1. 문제 요약

미로의 첫 블럭에서 지정된 블럭까지 가는 데 최소 소요 칸 수 구하기

2. 알고리즘

가장 기본적인 BFS 문제이다.

최종 구하려는 블럭의 depth값을 출력하면 된다.

큐에 저장해줄 때는 i * 100 + j의 값을 사용하였다.

3. 코드

#include <iostream>
#include <queue>

int main() {
	char maze[100][100];
	int depth[100][100];

	int N, M;

	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i) scanf("%s", maze[i]);

	int d = 1;
	maze[0][0] = '0';
	depth[0][0] = 1;
	queue<int> q;
	q.push(0);
	int i, j, u;
	while (q.empty() == false) {
		u = q.front();
		q.pop();
		i = u / 100;
		j = u % 100;
		if (i > 0 && maze[i - 1][j] == '1') {
			maze[i - 1][j] = '0';
			depth[i - 1][j] = depth[i][j] + 1;
			q.push((i - 1) * 100 + j);
		}
		if (i < 99 && maze[i + 1][j] == '1') {
			maze[i + 1][j] = '0';
			depth[i + 1][j] = depth[i][j] + 1;
			q.push((i + 1) * 100 + j);
		}
		if (j > 0 && maze[i][j - 1] == '1') {
			maze[i][j - 1] = '0';
			depth[i][j - 1] = depth[i][j] + 1;
			q.push(i * 100 + j - 1);
		}
		if (j < 99 && maze[i][j + 1] == '1') {
			maze[i][j + 1] = '0';
			depth[i][j + 1] = depth[i][j] + 1;
			q.push(i * 100 + j + 1);
		}
	}

	printf("%d\n", depth[N - 1][M - 1]);

	return 0;
}