등산 코스 레벨 (C++)

요약

memset(visited, 0, sizeOf(visited));

 메모리 초기화 / cstring 라이브러리에 있음

투포인터를 활용해서 가장 높은 곳의 높이를 기록한 후 점차 줄여가며 갈 수 있는 높이인지를 확인했다.
갈 수 있다면? BFS 활용해서 내가 원하는 점들을 다 방문했는지 확인했다.
내가 지정한 높이(mid)보다 경사가 가파르면 continue되게 설정했다.

---

문제

등산 코스는 모든 뷰포인트를 방문하기 위한 경로중 가장 큰 높이의 차이
레벨이 높을수록 위험한 등산 코스

[제약사항]
해발 높이는 0 이상, 1,000,000,000 이하이다.

[입력]
두번째 줄부터 N개의 줄에 걸쳐 M개의 정수(높이)가 공백으로 구분되어 주어진다.
그 후 N개의 줄에 걸쳐 M개의 0 또는 1이 공백으로 구분되어 주어진다.
0 : 길, 1 : 웨이포인트

[출력]
첫번째 줄에 책정된 등산 코스의 최소 레벨을 출력한다.

---

풀이

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

struct Node {
	int row, col;
};
vector< Node> v;
int map[501][501] = { 0, };
int N, M;
int maxheight = -1;
int visited[501][501] = { 0, };
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
queue<Node>q;


bool CanHike(int mid) {

	memset(visited, 0, sizeof(visited));
	q.push({ v[0].row, v[0].col });
	visited[v[0].row][v[0].col] = 1;

	while (!q.empty()) 
	{
		Node now = q.front();
		q.pop();
		int pr = now.row;
		int pc = now.col;
		for (int i = 0; i < 4; i++) {
			int nr = pr + dr[i];
			int nc = pc + dc[i];
			if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
			if (visited[nr][nc]) continue;
			if (abs(map[nr][nc] - map[pr][pc]) > mid) continue;
			q.push({ nr,nc });
			visited[nr][nc] = 1;
		}
	}
	for (int i = 0; i < v.size(); i++) {
		if (visited[v[i].row][v[i].col] == 0) return false;
	}
	return true;
}

int decision() {

	int left = 0;
	int right = maxheight;
	int mid;
	int temp = 0;

	while (left <= right)
	{
		mid = (left + right) / 2;
		if (CanHike(mid)) { 
			temp = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}
	return temp;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] > maxheight) maxheight = map[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int a;
			cin >> a;
			if (a) v.push_back({ i,j });
		}
	}

	cout << decision();
	return 0;
}