Beakjoon] 미로 탐색 (백준 2178 코테) - 탐색

---

🅰️문제주소 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

🚩문제 

 

 

🪡풀이 

 - 최단경로를 구하는 문제로 BFS를 사용해서 도달한 깊이값을 사용하면 됨. 
 - 상, 하, 좌, 우 이동이 가능하고 이 이동을 하기위한 값을 미리 저장해 둠.
 - 방문한 위치는 depth값을 기록하면서 해당 위치에 도달하기 위한 최솟값을 저장해 둠

 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>
#include <queue>
#include <string>

static std::vector<std::vector<int>> map;
static std::vector<std::vector<bool>> visited;
static int depth=1;
static int dx[] = { 0, 1, 0 ,-1 };
static int dy[] = { 1, 0, -1, 0 };
static int N, M;

void BFS(int x, int y) {
	std::queue<std::pair<int, int>> myQ;
	
	myQ.push(std::make_pair(x, y));
	visited[x][y] = true;

	while (!myQ.empty()) {
		std::pair<int, int> now = myQ.front();
		myQ.pop();
		for (int i = 0; i < 4; ++i) {
			int fir = now.first + dx[i];
			int sec = now.second + dy[i];

			if (fir >= 0 && sec >= 0 && fir < N && sec < M) { //유효성
				if (map[fir][sec] != 0 && visited[fir][sec] == false) { //방문할 필요가 있는지, 방문이미 했는지
					visited[fir][sec] = true;
					//map[fir][sec]++;
					map[fir][sec] = map[now.first][now.second] + 1;
					myQ.push(std::make_pair(fir, sec));
				}
			}
		}
	}

	
}


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

	std::cin >> N >> M;
	map.resize(N, std::vector<int>(M, 0));
	visited.resize(N, std::vector<bool>(M, false));
	
	for (int i = 0; i < N; ++i) {
		std::string temp;
		std::cin >> temp;
		for (int j = 0; j < M; ++j) {
			map[i][j] = temp[j] - '0';
		}
	}

	BFS(0,0);
	std::cout << map[N - 1][M - 1];

	return 0;
}

 

💡알게 된 것 

 - 최단경로 구하기는 해당 깊이에 대해 전체 탐색을 끝내게 되는 BFS가 적합함
 - 경로가 겹치는 것을 걱정하였으나 이미 최초 해당경로 도달 시 도달 가능한 최솟값이기에 별도의 작업은 필요 없이 방문여부만 체크하면 됨
 - 상수로 배열의 길이를 선언할 수 있다면 vector를 안 쓰는 게 더 빠르긴 함

---