[백준] 2178번: 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

1. 구상

 

BFS를 사용하면 된다.

BFS의 특징이 최단 경로를 찾아준다는 것이다. 

 

n, m을 통해 미로의 크기를 받고, 

graph[][]에 미로의 길을 추상화해준다.

visited[][]를 통해, 기존에 방문한 노드인지 확인해주고

check[][]에 각 노드까지의 최단 경로를 저장해준다. 

 

q는 bfs()의 지역변수로 사용해도 충분하다.

 

isInBound()를 먼저 확인해줘서, 이동 시에 범위를 벗어나지 않도록 확인해준다. 

*isInBound()로 범위 내인지 확인을 해줘야, visited[newx][newy]나 graph[newx][newy]에 접근할 때 에러가 뜨지 않는다. 안그러면 OutOfBounds 에러 뜸

 

bfs()를 int 리턴하는 것으로 정의했다가, 런타임에러가 나서 혼쭐났다...

return을 해야하는지 말아야하는지 제발 확인 좀 하자!!!

 

2. 코드

//2178

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

using namespace std;

int n, m;
int graph[101][101];
int visited[101][101] = { 0, }; // 방문 여부 표시 
int check[101][101] = { 0, }; // 최단 경로 저장 

queue<pair<int, int> > q;

bool isInBound(int x, int y){
	if(x>=0 && y>=0 && x<n &&y<m){
		return true;
	}else{
		return false;
	}
}

void bfs(int x, int y){
	
	// direction vector
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0 , 1, -1};
	
	q.push(make_pair(x, y));
	visited[x][y] = true;
	//cout << "visited: (" << x << ", " << y << ")" << endl;
	check[x][y] = 1;
	
	while(!q.empty()){
		
		pair<int, int> node = q.front();
		q.pop();
		for(int i = 0; i<4; i++){
			int newx = node.first + dx[i];
			int newy = node.second + dy[i];
			
			if(isInBound(newx, newy)){ //우선 범위 내인지 확인
				if(visited[newx][newy] != 1  && graph[newx][newy] == 1){
					visited[newx][newy] = 1;
					//cout << "visited: (" << newx << ", " << newy << ")" << endl;
					q.push(make_pair(newx, newy));
					check[newx][newy] = check[node.first][node.second] + 1;
                    	// 최단 경로를 전 위치까지의 최단경로 +1로 저장해준다.
					//cout << "shortest route: " << check[newx][newy] << endl;
				}
			}
		}
	}
	
}

int main(void){
		
	// get inputs
	cin >> n >> m;
	
	for(int i = 0; i<n; i++){
		string str;
		cin >> str;
		for(int j = 0; j<m; j++){
			graph[i][j] = str[j]-'0';
		}
	}
    
    // print to check if map is correctly saved
	/*
	for(int i = 1; i<=n; i++){
		for(int j = 1; j<=m; j++){
			cout << graph[i][j] << ' ';
		}
		cout << '\n';
	}
	*/
    
	// 목적지 정점은 (n-1, m-1)이다.
	bfs(0, 0);
	cout << check[n-1][m-1] << endl;
}