문제
대나무가 더 많은 쪽으로만 이동하면서 살아갈 수 있는 판다
최대 며칠 살 수 있을까?!
생각
DP라니까 뭐 각 위치를 끝 지점으로 살 수 있는 최대 일 수을 저장하고 있자
현재 위치에서 가지고 있는 대나무가 그 바로 근처에 대나무보다 많다면,
현재 위치에선 근처에서 살 수 있는 최대 일 수보다 하루 더 살 수 있으니까
상하좌우 근처 보면서 근처가 작으면
그 근처의 최대 살 수 있는 날을 구하러 떠나고 (재귀) 돌아오면
상하좌우 다녀온거 중 가장 오래 살 수 있는 최대 일 수 + 1의 값 저장!
for (int i = 0; i < 4; i++) { // 상하좌우 보자
if (map[nx][ny] < map[x][y]) {
//바로 근처에서 가지고 있는 대나무가 현재 위치 대나무보다 적다면
day[x][y] = max(day[x][y], findDay(nx, ny) + 1);
//근처에서 최고 살 수 있는 날보다 하루 더 살 수 있음
}
}저렇게 day 배열을 업데이트 하는 건 금방 떠올렸는데,
상세한 구현 고민을 좀 했었다
주절 주절이니까 맨 밑에 코드만 보셔두 돼요
고민 1 - 재귀 함수 어떻게?
난 재귀함수 헤이러다.
그래서 DP문제는 왠만하면 재귀 안 쓰고 점화식 생각해서 단순히 돌면서 저장하면서 푸는데
이 문제는 재귀를 사용해봐야하더군...
모든 위치에서 살아남을 수 있는 날을 알아야 최대 날을 아는데,
근처 위치에서 살아남을 수 있는 날을 알면 현 위치에서 살 수 있는 날을 아니까
옆에 날짜 구하러 가자~ 또 옆에도 구하러 가자~ 하고 재귀를 써야하는 건 알겠어
값을 저장을 해서 이미 구한 곳은 다시 또 계산 안 하게 하는 것도 알겠고!
의문 1. 딱히 날짜를 맨날 반환해줄 필요가 있나?
그냥 함수들 다 타고 들어가서 더 들어갈 곳 없으면 값 바꿔놓고
다시 돌아와서 옆에 값 보고 자기꺼 업데이트하는 식으로 하면 안돼?
답 1. 위에 같은 의문때문에 아무것도 반환 안 하고 함수 실행! 돌아오면 값 봐! 이렇게 했는데
이렇게 해두 되더라 그래도 해당하는 값을 반환하고 그거 사용해서 구하는게 좀 더 목적에 맞는것같다..
의문 2. 이 재귀 함수들을 메인에서 이중 for문으로 모든 곳을 다 돌아줘야하나?
한 곳에서 날짜 구하기 시작하면 다 구해지는거 아닌가..
답 2. 근처의 대나무가 다 현재 위치보다 많으면 재귀 함수의 대가 끊기더라!!
(다 안 타고 들어간다는 뜻) 그래서 모든 곳에서 값을 구했었는지 확인은 해야하는군! 을 느낌
고민 2 - 그래서 maxDay는?
최종적으로 얻고자 하는 최대 일수는 언제 어디서 어떻게 저장하는게 좋을지 고민했다.
day[x][y] = max(day[x][y], findDay(nx, ny) + 1);
maxDay = max(maxDay, day[x][y]);처음엔 day[x][y]를 찾을 때 마다 최대 일수 인지 확인을 했는데
사실 day[x][y]는 동서남북을 다 다녀와야 원하는 최대 값이 저장되기 때문에
동서남북 다 다녀와서 업데이트를 하는 걸로 했는데
그러면 그냥 함수 반환하기 바로 전이더군?
int findDay(int x, int y) {
if (day[x][y] == 0) {
day[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
continue;
}
if (map[nx][ny] < map[x][y]) {
day[x][y] = max(day[x][y], findDay(nx, ny) + 1);
}
}
}
maxDay = max(maxDay, day[x][y]);
return day[x][y];
}
그래서 재귀 함수 반환 전에 업데이트하고 반환하게 했다가..
생각해보니 계속 타고 들어간 재귀 함수 반환보다,
맨 처음 불린 재귀함수에서 최대 일수를 반환하기 때문에
(근처보다 날 다 구하고 근처에서 보다 더 오래 산 곳이기 때문에)
재귀 함수 안에서 maxDay값 구하지 말고,
메인에서만 반환값으로 최대 일수를 비교해도 되더라! (전체 코드 확인하세요오)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
maxDay = max(maxDay, findDay(i, j));
}
}코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, maxDay, nx, ny;
int map[505][505], day[505][505];
//day[][]에 여기에서 출발해서 살 수 있는 최대날 넣어놔!!
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { -1, 1, 0, 0 };
int findDay(int x, int y) {
if (day[x][y] == 0) {
day[x][y] = 1;
for (int i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
continue;
}
if (map[nx][ny] < map[x][y]) {
day[x][y] = max(day[x][y], findDay(nx, ny) + 1);
}
}
}
return day[x][y];
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
int maxDay = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
maxDay = max(maxDay, findDay(i, j));
}
}
cout << maxDay;
return 0;
}