[백준 / BOJ] C++ 1937 욕심쟁이 판다

1937번: 욕심쟁이 판다

 

문제

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

1937번: 욕심쟁이 판다

 

 

풀이

2차원 배열에서 어느 한 점에서 출발해 상하좌우로 점차 증가하는 방향으로만 이동할 수 있을 때 가장 많이 이동할 수 있는 길이를 구하는 문제다. 따라서 dfs로 배열의 모든 점에 대해 가장 긴 이동 거리를 구하고 최댓값을 구했는데 시간초과를 받았다. 시간초과를 해결하기 위해 메모이제이션을 하는 방법밖에 없다고 생각했다.

 

따라서 visited 배열을 dp 배열로 사용했다. dfs는 만약 이미 방문한 점이라면, 그 점에서 이동 가능한 가장 긴 거리를 return 해줬다. 아직 방문하지 않은 점 visited 값을 1로 할당하고 상, 하, 좌, 우를 탐색해 이동할 수 있는 점으로 향한다. 이때 재귀를 사용해 다음 점에 대해 dfs를 또 실행한다.

 

만약 더 이상 진행할 수 없는 점까지 오게 되면 그 점에서는 1(visited 값)을 return 한다. 그러면 이전 점에서는 다음 칸보다 한 칸 더 갈 수 있으니 return 받은 값 + 1을 visited 값으로 가진다. 단, 이 값이 이미 다른 방향으로 갔다가 할당된 visited 값보다 작은 경우는 무시한다.

 

위 과정을 반복하면 이미 한 번 방문한 점에 대해서는 다시 탐색하지 않고 바로 값을 얻을 수 있으므로 시간을 단축할 수 있다. 쉬운 난이도는 아니라고 생각하고 그래프 탐색과 DP를 동시에 사용해 본 적은 처음이라 구현에도 애를 먹은 문제다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, ans = 0;
int graph[500][500] = {0}, visited[500][500] = {0};
int dx[] = {1, -1, 0, -0}, dy[] = {0, 0, 1, -1};

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin >> graph[i][j];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      ans = max(ans, dfs(i, j));
  cout << ans << '\n';
  return 0;
}