[BOJ 1937] 욕심쟁이 판다

kiraMe·2022년 11월 25일
0

Algorithm

목록 보기
2/3

문제

https://www.acmicpc.net/problem/1937

n x n 크기의 대나무 숲에서 판다는 상, 하, 좌, 우로 이동하며 대나무를 먹는다.
이때, 이동한 칸은 그 전 지역보다 대나무가 많이 있어야 한다.
판다가 이동할 수 있는 칸의 수의 최댓값을 구하자.


예시 이미지 설명 추가

풀이과정

문제를 읽고 가장 쉽게 떠올릴 수 있는 방법은 dfs를 통한 완전 탐색으로, 대나무 숲 전체를 방문하며 경로를 탐색하는 것이다. 그러나 n의 크기는 최대 500이고 2초의 시간제한이 있으므로, 이 방법으로는 해결할 수 없다.

물론 판다가 이동할 칸 수의 최댓값을 저장해야하므로 dfs를 재귀적으로 호출해야한다. 키 포인트는 dfs와 함께 dp를 사용하는 것이다. dp를 추가하면 반복되는 계산의 결과값을 이후의 계산에 이용할 수 있어, 탐색 시간을 줄일 수 있다.

코드

https://github.com/meraki6512/Algorithm/blob/master/AlgorithmProject1/1937.cpp

코드 설명 추가

#include <iostream>
#include <algorithm>
#include <vector>

#define INF 505

using namespace std;

int N;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};
int dp[INF][INF];
int v[INF][INF];

int main(void) {

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> v[i][j];
		}
	}

	int max_len = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			max_len = max(max_len, dfs(i, j));
		}
	}

	printf("%d", max_len);
}

int dfs(int x, int y) {
	if(dp[x][y]) return dp[x][y];
	dp[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || nx >=N || ny < 0 || ny >=N) continue;
		if (v[x][y] >= v[nx][ny]) continue;
		dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
	}
	return dp[x][y];
}
profile
meraki

0개의 댓글