[BAEKJOON] 2178번 : 미로 탐색

문 제

 

소 스  코 드

#include <iostream>
#include <queue>
#include <algorithm>

struct Node {
	int x;
	int y;
	int level;
};

class Map {
public:
	Map() = delete;
	Map(const int& n, const int& m) : mWidth{m}, mHeight{n}{
		obs = new char*[mHeight];
		for (int i = 0; i < mHeight; ++i) obs[i] = new char[mWidth + 1];
	}
	~Map() {
		for (int i = 0; i < mHeight; ++i) delete[] obs[i];
		delete[] obs;
	}


	// Initalize
	void Init() {
		for (int i = 0; i < mHeight; ++i) std::cin >> obs[i];
	}

	//  
	void SearchRoute(int startX = 0, int startY = 0) {
		bfs.push({ startX, startY, 1 });
		obs[startX][startY] = '0';
		int minRoute		{ 0x7fff'ffff };

		while (!bfs.empty()) {
			int x{ bfs.front().x };
			int y{ bfs.front().y };
			int level{ bfs.front().level };
			bfs.pop();

			if ((mHeight - 1 == x) && (mWidth - 1 == y)) minRoute = std::min(level, minRoute);

			int fg{ 0 };

			// left
			if ((y > 0) && ('0' != obs[x][y - 1])) {
				obs[x][y - 1] = '0';
				bfs.push({ x, y - 1, level + 1 });
			}
			// right
			if ((y < mWidth - 1) && ('0' != obs[x][y + 1])) {
				obs[x][y + 1] = '0';
				bfs.push({ x, y + 1, level + 1});
			}
			// up
			if ((x < mHeight - 1) && ('0' != obs[x + 1][y])) {
				obs[x + 1][y] = '0';
				bfs.push({ x + 1, y, level + 1 });
			}
			// down
			if ((x > 0) && ('0' != obs[x - 1][y])) {
				obs[x - 1][y] = '0';
				bfs.push({ x - 1, y, level + 1 });
			}

		}

		std::cout << minRoute << '\n';
	}



private:
	int mWidth;
	int mHeight;

	char **obs;

	std::queue<Node> bfs;
};

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, M;
	std::cin >> N >> M;

	Map map{ N, M };

	map.Init();

	map.SearchRoute();

	return 0;
}

 

풀 이

 

• [BeakJoon] 1012번 : 유기농 배추

• [BaekJoon] 2667번 : 단지 번호 붙이기

위의 두 문제를 stack으로 풀었는데, BFS라고 지칭을 하였습니다.

하지만, 오늘 이 문제를 생각하였는데, 위의 두 문제는 DFS를 이용하여 구현을 했습니다.

Stack을 통하여 깊이 기반 탐색을 하였는데, 공부가 부족하여 BFS로 구현한 것이라 착각을 했습니다.

 

미로 탐색의 문제의 경우, 최단거리를 보장하는 BFS로 풀어야합니다.

하지만, 위의 두 문제와 같이 Stack을 통하여 구현을 하는데, 잘 못 되었다는 것을 알게 되었고, 

미로 탐색 FAQ

queue를 통하여 BFS로 구현 하였습니다.

출 력 값

 

 

문 제  출 처

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

2178번: 미로 탐색