[코드업] 4039 - 놀이공원

문제 설명  

어린이 놀이동산에 돌-블록이 타일처럼 배치되어 있는 마당이 있다. 이 마당은 아래 그림처럼 n×m 크기의 격자로 표시된다. 격자의 칸에 있는 값은 돌-블록의 높이이다.

 

이 마당의 입구는 (1,1) 위치이고, 출구는 (n,m) 위치이다. 이 마당에서 즐길 수 있는 놀이 중에는 입구에서 출구까지 길을 찾는 게임이 있다. 게임 참가자는 각 블록에서 동서남북으로 인접한 블록으로 점프하여 건너갈 수 있는데, 높이 차이가 1보다 큰 경우에는 건너갈 수 없다. 또한 출구를 제외하고는 마당 밖으로 나갈 수 없다. 위 예에서 출구인 (4,4) 블록까지 이동하기 위해서는 (1,1), (2,1), (3,1), (3,2), (2,2), (2,3), (3,3), (4,3), (4,4) 블록을 순서대로 지나가면 된다. 이 놀이는 입구에서 시작하여 출구로 나갈 때까지 밟고 지나간 블록의 개수가 작을수록 높은 점수를 얻게 된다.

 

게임 참가자가 마당의 입구에서 시작하여 가장 작은 개수의 블록을 밟으면서 출구로 도착할 수 있는 길을 찾는 프로그램을 작성하시오.

입력

1. 첫째 줄에 마당의 크기 n×m을 나타내는 두 개의 정수 n과 m이 차례대로 주어진다. (2≤n≤1,000, 2≤m≤1,000)

2. 그 다음 n개의 줄에는 m개의 정수가 주어지는데, i+1번째 줄의 j-번째 정수는 i-번째 행 j-번째 열에 있는 블록의 높이를 나타낸다. 돌 블록의 높이는 1 이상 9이하이다.

출력

1. 게임 참가자가 출구까지 갈 수 없으면 첫 줄에 0을 출력한다.

2. 만약 출구가 가는 길이 있으면, 가장 작은 개수의 블록으로 구성된 길을 찾아서 그 길을 구성하는 블록의 개수를 첫 줄에 출력한다.

입력 예시

4 4
7 9 8 5
6 3 2 4
5 4 1 5
2 6 1 1

출력 예시

9

---

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

const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};

int n, m, result;
vector<vector<int>> board;
vector<vector<bool>> visited;
vector<vector<int>> cnt;

bool boarderCheck(int y, int x, int value){
	if(y < 0 || x < 0 || y >= n || x >= m) return false;
	else if(visited[y][x] == true) return false;
	else if(!(board[y][x] <= value + 1 && board[y][x] >= value - 1)) return false;
	else return true;
}

void bfs(){
	queue<pair<int, int>> que;
	que.push({ 0, 0 });
	cnt[0][0] = 1;
	visited[0][0] = true;

	while(!que.empty()){
		auto elem = que.front();
		que.pop();

		if(elem.first == n - 1 && elem.second == m - 1)	break;

		int beforeValue = board[elem.first][elem.second];
		for(int d = 0; d < 4; d++){
			int nextY = elem.first + dy[d];
			int nextX = elem.second + dx[d];
			if(boarderCheck(nextY, nextX, beforeValue)){
				que.push({ nextY, nextX });
				visited[nextY][nextX] = true;
				cnt[nextY][nextX] = cnt[elem.first][elem.second] + 1;
			}
		}
	}
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
	cin >> n >> m;
	board.resize(n);
	visited.resize(n);
	cnt.resize(n);
	for(int i = 0; i < n; i++){
		board[i].resize(m);
		visited[i].resize(m);
		cnt[i].resize(m);
	}

	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> board[i][j];

	bfs();

	if(visited[n - 1][m - 1])
		cout << cnt[n - 1][m - 1];
	else
		cout << 0;

	return 0;
}