백준 2178번: 미로 탐색

[문제 링크]

2178번: 미로 탐색

---

(0, 0) 위치에서 시작하여 동 서 남 북 방향을 확인하면서 이동 가능한 방향에 아직 방문하지 않고 값이 '1'인 위치가 있다면 queue에 추가해주는 너비 우선 탐색으로 구현하였다.

---

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

int N, M;
vector<string> board(100);
bool discovered[100][100];

int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

struct Point
{
	int y;
	int x;

	Point(int _y = 0, int _x = 0) : y(_y), x(_x) { }

	bool operator== (const Point& rhs) {
		if (y == rhs.y && x == rhs.x) return true;
		return false;
	}
};

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

	Point target = { N - 1, M - 1 };

	while (!q.empty()) {
		Point here = q.front().first;
		int move = q.front().second;

		q.pop();

		if (target == here)
			return move;

		for (int i = 0; i < 4; i++)
		{
			int ny = here.y + dy[i];
			int nx = here.x + dx[i];

			if (ny < N && ny >= 0 && nx < M && nx >= 0)
				if (!discovered[ny][nx] && board[ny][nx] == '1') {
					discovered[ny][nx] = true;
					q.push({ { ny, nx }, move + 1 });
				}
		}
	}

	return -1;
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		cin >> board[i];

	cout << bfs() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day