[코드업 4039] 놀이공원

https://codeup.kr/problem.php?id=4039&rid=

입력

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

풀이

문제 이해에 정말 애먹은 근래의 탑 1 문제.

상하좌우로 탐색해가지만 i,j의 값이 1이상 차이나면 갈 수 없는 조건에서 최단거리를 보장하며 이동해야한다.

i,j,dist 총 3개를 묶어 큐에 넣으며 이동시마다 +=1,
이동 할 때 현재의 arr[i][j]의 값과 1차이 나면 이동하는 로직을 넣으면된다.

또한 복잡도 때문에 n-1,m-1일때 바로 return으로 함수를 종료하지 않으면 초과가 된다.```

코드

#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
#include<queue>
#include <climits>
#include<tuple>
#include<limits.h>
using namespace std;
int arr[1001][1001];
int visitied[1001][1001] = { false, };
int x[4] = { 0,1,0,-1 };
int y[4] = { -1,0,1,0 };
int n, m;
struct distq {
	int i; int j; int dist;
};
void bfs()
{
	queue<distq>queue;
	queue.push({ 0, 0, 1 });
	while (!queue.empty())
	{
		int a = queue.front().i;
		int b = queue.front().j;
		int n_dist = queue.front().dist;
		queue.pop();
		visitied[a][b] = true;
		if (a == n - 1 && b == m - 1)
		{
			cout << n_dist;
			return;
		}
		for (int i = 0; i < 4; i++)
		{
			int xx = a + x[i];
			int yy = b + y[i];
			if (xx >= 0 && yy >= 0 && yy < m && xx < n &&(arr[xx][yy]==arr[a][b]|| arr[xx][yy]+1 == arr[a][b]|| arr[xx][yy]-1 == arr[a][b]))
			{
				if (!visitied[xx][yy] )
				{
					visitied[xx][yy] = true;
					queue.push({ xx,yy ,n_dist+1});
				}
			}
		}
	}
	cout << "0";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);

	cin >> n >> m;

	for (int i=0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> arr[i][j];
		}
	}
	bfs();
	
}