[bfs] 1261 알고스팟

알고스팟 1261

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
// 1261 알고스팟

const int MAX = 555;
const int INF = 123456789;

int main(){
	int n, m;
	int destroy[MAX + 1][MAX + 1];
	int board[MAX + 1][MAX + 1];
	int dy[4] = {0, 0, 1, -1};
	int dx[4] = {1, -1, 0, 0};
		
	// 입출력 부분에 주의하자. 가로 세로가 무엇인지 잘 파악해야한다.
	cin >> m >> n;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%1d", &board[i][j]);
			destroy[i][j] = -1;
		}
	}
	
	//bfs
	deque<pair<int, int>> deq;
	
	destroy[1][1] = 0;
	deq.push_back(make_pair(1,1));
	
	while(!deq.empty()){
		int currentY = deq.front().first;
		int currentX = deq.front().second;
		deq.pop_front();
		
		
		for(int i = 0; i < 4; i++){
			int nextY = currentY + dy[i];
			int nextX = currentX + dx[i];
			pair<int, int> nextNode = make_pair(nextY, nextX);
			
			// 범위 체크
			if(nextY > 0 && nextY <= n && nextX > 0 && nextX <= m){
			// 방문 여부 체크
				if(destroy[nextY][nextX] == -1){
					// 빈 방이라면 : 0이라면
					if(board[nextY][nextX] == 0){
						deq.push_front(nextNode);
						destroy[nextY][nextX] = destroy[currentY][currentX];
					}	
					// 벽이라면 : 1이라면
					else if(board[nextY][nextX] == 1){
						deq.push_back(nextNode);
						destroy[nextY][nextX] = destroy[currentY][currentX] + 1;
					}
				}
			}
		}
	}
	cout << destroy[n][m] << endl;

}

 

해설

---

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

- 비슷한 문제를 풀었었다. deque 를 활용한 bfs 최단 비용 구하기.

풀이

1. 위의 비슷한 문제를 참고해보자.

2. 가중치가 0과 1인 문제이다.

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

1. 입출력 실수

- 이 문제는 입력이 (가로 크기, 세로 크기) 으로 주어진다. 이 점을 간과하고 당연히 (세로, 가로) 라고 입력을 받았었다. 이러한 입출력 실수를 범해서 bfs 논리를 아무리 파헤쳐봐도 알 수 없는 "틀렸습니다" 지옥에 빠졌었다.