[BOJ][골5][1937] 욕심쟁이 판다

문제 링크

문제링크

첫 번째 풀이 : DFS

알고리즘

시간초과 코드부터 생각해보겠습니다. dfs는 기본적으로 모든 노드를 한 번씩만 확인하는 코드입니다. 노드를 방문할 때마다 visited를 true로 바꾸어줍니다. 만약 visted를 다시 false로 바꾸는 경우가 없다면 모든 노드를 한 번씩만 방문합니다.

그런데 위 문제를 완전탐색으로 접근할 때 모든 노드를 한 번씩만 방문해서는 모든 경우를 따져볼 수 없습니다. 따라서 n자리 k진수에서 배웠던 것처럼 recur()을 호출한 이후 visited를 false로 바꿔주면 백트래킹을 이용해서 모든 경우를 따져볼 수 있습니다. false로 바꿔주는 것의 의미는 ‘해당 노드를 방문하지 않는 것으로 생각한다.’ 입니다. 이렇게 접근해서 시간초과를 받은 코드는 위 링크의 댓글에 있습니다.

시간초과가 나는 이유는 대나무의 수가 회오리모양으로 존재할 때, 가장 긴 life를 구하는 방법은 회오리 모양으로 따라가면서 먹는 방법이 유일합니다. 그런데 visited를 false로 바꾸는 방법으로 진행하면 1. 회오리를 처음부터 끝까지 따라가는 경우 2. 회오리의 중간부터 들어와서 끝까지 따라가는 경우 모두 dfs를 반복해서 진행합니다. 따라서 “갔던 길은 다시 가지 않는 dfs”가 필요해집니다.

모든 경우를 따져보면서 갔던 길을 다시 가지 않는 방법은 “갔던 길에 표시를 해두고 표시가 있는 노드를 방문 했을 때는 다시 가지 않고 신호만 보고 return 한다.”입니다. 표시를 저장하는 배열을 dp라고 할 때 아래와 같이 정의합니다.

1. dp[x][y] = N : map[x][y]에 도착하면 N일을 살 수 있다. 또는
2. dp[x][y] = N : map[x][y]에 ‘사방으로 진행할 수 있는 가장 긴 날짜 + 오늘’을 살 수 있다.

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

1. 15에서 시작한다면 사방으로 진행할 수 없기 때문에 0 + 1을 저장하고 return 합니다.
2. 12에서 시작한다면 사방으로 진행할 수 없기 때문에 0 + 1을 저장하고 return 합니다.
3. 10에서 시작한다면 12로 진행할 수 있기 때문에, 12가 return하는 값(1) + 1을 저장하고 return합니다.

여기까지 dp[x][y]에 대한 정의를 이해하고 코드를 보면 이해할 수 있습니다.

정답 코드

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int n = 0, input = 0, ans = 0;
int map[501][501];
int dp[501][501];
bool visited[501][501];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1, 0,0 };

int max(int a, int b) {
  return a < b ? b : a;
}

int dfs(int x, int y){
  if (dp[x][y]) return dp[x][y];

  for (int k = 0; k < 4; k++) {
    int nx = x + dx[k];
    int ny = y + dy[k];
    if (nx < 0 || nx >= n) continue;
    if (ny < 0 || ny >= n) continue;
    if (map[nx][ny] > map[x][y]) {
      dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
    }
  }
  return dp[x][y];
}

int main(void) {
  cin.tie(NULL);
  ios::sync_with_stdio("false");
  //freopen("input.txt", "r", stdin);
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> map[i][j];
    }
  }
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans = max(ans, dfs(i, j));
    }
  }
  cout << ans + 1 << "\n";
  return 0;
}

Success Notice: 수고하셨습니다.