[C++] 2178: 미로탐색

실버 Ⅰ

 

#include <iostream>
#include <queue>
using namespace std;

int N, M;
int map[100][100];
bool visit[100][100];
int didj[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

void bfs() {
	queue<pair<int, int>> q;
	q.push({ 0, 0 });
	visit[0][0] = true;

	while (!q.empty()) {
		int cur_i = q.front().first;
		int cur_j = q.front().second;

		q.pop();

		if (cur_i == N - 1 && cur_j == M - 1) return;

		for (int k = 0; k < 4; k++) {
			int new_i = cur_i + didj[k][0];
			int new_j = cur_j + didj[k][1];

			if (new_i < 0 || new_i >= N || new_j < 0 || new_j >= M) continue;
			if (visit[new_i][new_j]) continue;

			if (map[new_i][new_j] == 1) {
				map[new_i][new_j] = map[cur_i][cur_j] + 1;
				visit[new_i][new_j] = true;
				q.push({ new_i, new_j });
			}
		}
	}
}

int main() {
	scanf("%d%d", &N, &M);

	char row[101];
	for (int i = 0; i < N; i++) {
		scanf("%s", &row);
		for (int j = 0; j < M; j++) {
			map[i][j] = row[j] - '0';
		}
	}

	bfs();
	printf("%d", map[N - 1][M - 1]);
}

 

bfs 최단거리 기본

bfs 최단거리 경로 기본도 풀어볼 것~

 

가중치 없는 그래프에서의 최단경로(거리) -> bfs