1949 등산로 조성

0이상이라면 최대 깊이 K로 한 곳의 경사를 내릴 수 있다. 어렵게 생각했던 점은 bfs를 돌리면서 경사를 깎아 내리려고 했다. 쉽게 생각하면 사전에 하나씩 줄여나가면서 bfs를 돌리면 깔끔하게 해결할 수 있다

 

문제: https://www.swexpertacademy.com/main/code/problem/problemDetail.do

깃허브주소: https://github.com/surinoel/boj/blob/master/swea1949.cpp

 

	#include <queue>
	#include <tuple>
	#include <vector>
	#include <cstring>
	#include <iostream>
	using namespace std;
	#define max(n, m) n > m ? n : m
	int mat[8][8];
	int tmpmat[8][8];
	int dist[8][8];
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int tc;
	cin >> tc;
	for (int test_case = 1; test_case <= tc; test_case++) {
	memset(mat, 0, sizeof(mat));
	int n, m;
	int maxheight = -1;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	cin >> mat[i][j];
	maxheight = max(maxheight, mat[i][j]);
	}
	}
	vector<pair<int, int>> maxpos;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	if (mat[i][j] == maxheight) {
	maxpos.push_back(make_pair(i, j));
	}
	}
	}
	int ans = 0;
	for (int k = 0; k < maxpos.size(); k++) {
	int x, y;
	x = maxpos[k].first, y = maxpos[k].second;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	if (i == x && j == y) continue;
	for (int z = 1; z <= m; z++) {
	if (mat[i][j] - z < 0) break;
	memcpy(tmpmat, mat, sizeof(tmpmat));
	memset(dist, -1, sizeof(dist));
	tmpmat[i][j] -= z;
	int tmpmax = -1;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	dist[x][y] = 1;
	tmpmax = dist[x][y];
	while (!q.empty()) {
	int tx, ty;
	tie(tx, ty) = q.front();
	q.pop();
	for (int u = 0; u < 4; u++) {
	int ttx = tx + dx[u];
	int tty = ty + dy[u];
	if (ttx < 0 || tty < 0 || ttx > n - 1 || tty > n - 1) continue;
	if (tmpmat[ttx][tty] >= tmpmat[tx][ty]) continue;
	if (dist[ttx][tty] == -1 || dist[tx][ty] + 1 > dist[ttx][tty]) {
	dist[ttx][tty] = dist[tx][ty] + 1;
	q.push(make_pair(ttx, tty));
	tmpmax = max(tmpmax, dist[ttx][tty]);
	}
	}
	}
	ans = max(ans, tmpmax);
	}
	}
	}
	}
	cout << "#" << test_case << " " << ans << '\n';
	}
	return 0;
	}

view raw swea1949.cpp hosted with ❤ by GitHub