[C/C++] 코드업(codeup) 4039번 놀이공원

▽문제 바로가기

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

놀이공원

---

입력

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

 

문제 풀이

 

지나가는 블록의 개수가 가장 작은 값을 출력해야 합니다. 최단 길이를 보장하는 BFS로 풀 수 있습니다. (처음에 DFS로 풀어봤으나 시간초과 발생...)

 

▽너비 우선 탐색(BFS) 바로가기

https://swblossom.tistory.com/49

[C/C++] 너비 우선 탐색(BFS)

문제 풀이법은 다음과 같습니다. 탐색을 할 때 큐에 행, 열, 이동 횟수까지 저장해야 해서 클래스를 따로 만들었습니다.

 

1. 시작점을 큐에 넣고 방문 체크

2. 큐 pop

3. pop값을 기준으로 동서남북으로 탐색

3-1. 범위 안으로 유효하게 탐색

3-2. 블록이 1 이하로 차이나고 방문 안 했으면 큐에 넣고 방문 체크

4. 2, 3번을 반복하면서 도착했는지 확인하고 도착했으면 최솟값 계산

 

#include <stdio.h>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

int n, m;
int arr[1002][1002] = {0,};
int ret = 987654321;
int dy[4] = {0, 0, 1, -1};	//동서남북 4방향
int dx[4] = {1, -1, 0, 0};	//동서남북 4방향
bool check[1002][1002] = {false,};	//방문체크

//절댓값 계산
int myabs(int a, int b){
	int c = a-b;
	return c>=0? c:c*-1;
}

//최솟값 계산
int myMIN(int a, int b){
	return a>b? b:a;
}

//큐에 넣을 데이터
class myClass{
public:
	int row, col, cnt;
	myClass(int row, int col, int cnt){
		this->row = row;
		this->col = col;
		this->cnt = cnt;
	}
};

//탐색
void bfs(){
	
	queue<myClass> q;
	q.push(myClass(1, 1, 1));	//1행 1열 넣기 
	check[1][1] = true;
	
	while(!q.empty()){
		int row = q.front().row;
		int col = q.front().col;
		int cnt = q.front().cnt;
		q.pop();
		//도착했다면 최솟값 계산
		if(row==n&&col==m) ret = myMIN(ret, cnt);
			
		//동서남북 탐색
		for(int i=0;i<4;i++){
			//범위안으로 유효하게
			if(row+dy[i]==0||row+dy[i]>n||col+dx[i]==0||col+dx[i]>m) continue;
			
			//블록이 1보다 적게 차이나면 
			if(myabs(arr[row][col], arr[row+dy[i]][col+dx[i]])<=1){
				//방문안했으면 방문하고 queue에 push 
				if(!check[row+dy[i]][col+dx[i]]){
					q.push(myClass(row+dy[i], col+dx[i], cnt+1));
					check[row+dy[i]][col+dx[i]] = true;
				}
			}
		}
		
	}
	
}

int main(){
	
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	
	bfs();
	
	if(ret==987654321) printf("0");
	else printf("%d", ret);
	
	return 0;
}