[백준] 2178번 - 미로 탐색

이 문제는 위의 그림과 같이 입구(0,0)에서 출구(N-1,M-1) 까지의 거리를 찾는 문제이다.

거리를 찾는 문제이기 때문에 너비우선탐색을 이용해서 푸는 방법을 쉽게 생각 할 수 있었다.

 

matrix를 이용해서 문제를 풀면 간다하며 마지막으로 저장되어진 dist 행렬에서 N-1,M-1번째 수만 결과를 출력하면 간단하게 풀 수 있다.

 

여기서 더욱 더 시간을 줄이기 위해 방향을 아래와 같이 행렬에 저장하였다.

int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} };

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

int N, M;
int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} };
vector<vector<int>> adj;
vector<vector<int>> dist;

void bfs(int startx, int starty) {
	dist = vector<vector<int>>(N, vector<int>(M, -1));
	queue<pair<int, int>> q;
	dist[startx][starty] = 1;
	q.push(make_pair(startx, starty));

	while (!q.empty()) {
		
		int here_x = q.front().first;
		int here_y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int there_x = here_x + dir[i][0];
			int there_y = here_y + dir[i][1];
			if (there_x >= 0 && there_y >= 0 && there_x < N && there_y < M && dist[there_x][there_y] == -1 && adj[there_x][there_y] == 1) {
				q.push(make_pair(there_x, there_y));
				dist[there_x][there_y] = dist[here_x][here_y] + 1;

			}
		}
	}
}

int main() {
	cin >> N >> M;
	adj = vector<vector<int>>(N, vector<int>(M, 0));
	for (int i = 0; i < N; ++i) {
		string str;
		cin >> str;
		for (int j = 0; j < M; ++j) {
			if (str[j] == '1') {
				adj[i][j] = 1;
			}
		}
	}	
	
	bfs(0, 0);
	cout << dist[N - 1][M - 1];

}

 

소스코드 : https://github.com/withseungryu/Algorithms

withseungryu/Algorithms

궁금하신 것이 있으시다면 댓글로 남겨주세요!~