[bfs 최단거리] 2178 미로

미로 (2178)

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 2178 미로
// '최단' '최소' 가 나오는 문제는 BFS 이다.
// 가중치가 1일 때만 구할 수 있다.


int main(){
	int n, m;
	int board[100][100];
	int distance[100][100];
	
	fill_n(&distance[0][0], 10000, -1);
	
	queue<pair<int, int>> q;
	pair<int, int> np[4] = {
		make_pair(0, 1),
		make_pair(0, -1),
		make_pair(1, 0),
		make_pair(-1, 0)
	};
	
	scanf("%d %d",&n, &m);
	
	for(int i = 0; i < n; i++){
		for(int j = 0 ; j < m; j++){
			scanf("%1d", &board[i][j]);
		}
	}
	
	// bfs
	
	// 시작 부분
	distance[0][0] = 1;
	q.push(make_pair(0, 0));
	
	while(!q.empty()){
		int currentY = q.front().first;
		int currentX = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int ny = currentY + np[i].first;
			int nx = currentX + np[i].second;
			
			// 범위
			if(ny >= 0 && ny < n && nx >= 0 && nx < m){
				// 이동가능한 칸인지 / 방문안했는지
				if(board[ny][nx] == 1 && distance[ny][nx] == -1){
					q.push(make_pair(ny, nx));
					distance[ny][nx] = distance[currentY][currentX] + 1;
				}
			}
		}	
	}
	cout << distance[n - 1][m - 1] << endl;
	
	
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 최단 경로 / 최소 거리를 찾는 문제이다.

- BFS 는 단계적으로 진행되기 때문에 이러한 문제에 최적이다. 단, 가중치가 1인 경우일 때이다.

2. 시작점에서부터 현재 위치까지의 거리를 나타내주는 distance 2차원 배열을 생각해보자.

- distance 의 초기값은 -1 이므로, -1이라면 미방문인 것이다. 그러므로, 이전 문제들의 isVisit 배열 즉, 방문 여부를 판단할 수 있음과 동시에, 거리를 나타내주기도 한다.

- 이전 위치 distance 값에 1을 더해주면 다음 위치의 distance 값이 된다.

- 초기화를 잘해주어야 한다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

 

n과 m 을 잘못 써서 한번 틀렸다. 상수 오타 조심하자