백준 1937번: 욕심쟁이 판다

1) 문제 분석

  1. 첫 번째 시도
      내가 짚은 문제의 핵심은 판다는 대나무가 지금 칸보다 더 많은 칸으로 밖에 이동할 수 없으며, 판다가 살 수 있는 최대 일수를 구해야 한다는 것이었다. 최대 일수를 구하라는 점과 대나무숲이 directional graph로 표현될 수 있다는 점에서 착안해서, 각 노드에서 dfs를 수행했을 때 생성되는 tree에서 가장 depth가 깊은 경우를 찾는 문제로 해석하였다. 이 때 n*n 2차원 배열을 하나 더 만들어서, 그 노드에서 시작하는 subtree의 depth를 저장하여 계산이 중복되지 않도록 하였다. 다르게 말하면 spanning tree에서 가장 긴 path의 길이를 찾는 문제라고 할 수 있다. 기록을 보니까 무려 1년전에 시도해서 틀렸던 문제였는데 해결할 수 있어서 뿌듯했다 :3
  2. 최적화
      그런데 정답은 맞았지만 다른 사람들이 풀어놓은 결과를 확인하니 수행 시간에서 꽤 차이가 있었다. 그리고 문제 분류를 확인하니까 다이나믹 프로그래밍, LIS(longest increasing subsequence), 정렬에 속해있었다. 혹시나해서 더 빠른 다른 풀이가 있는지 고민해보았는데, 분류가 그러할 뿐 결국 내가 작성한 코드도 다이나믹 프로그래밍 원리를 사용하는거라고 생각해서 의아했었다.
      그런데 ios_base::sync_with_stdio(false); cin.tie(0);를 추가하니까 놀랍게도 수행시간이 124ms 에서 32ms로 줄었다. 혹시나해서 int 값을 반환하는 원래 dfs 코드에도 ios_base::sync_with_stdio(false); cin.tie(0); 아무래도 입력이 최대 2500개여서 stdio와 iostream 입출력 스트림을 비동기화 함으로써 수행시간이 감소되는 효과가 있었던 것 같다. 또한, dfs라고 이름 붙였을 뿐이지 기본 뼈대는 다른 사람들이 구현한 알고리즘과 비슷하였다.

2) 코드

#include <iostream>

using namespace std;

int dir_x[] = {-1,0,1,0};
int dir_y[] = {0,1,0,-1};

int forest[500][500];  //대나무숲 각 칸의 대나무 수
int path[500][500];    //각 칸에서 시작했을 때 판다가 살 수 있는 최대 일수
int n;                 //대나무숲 크기
int max_dist = 0;      //판다가 살 수 있는 최대 일수

/**
 * (x,y)가 n*n 배열 범위 내에 있는지 확인한다
 * @param x 행
 * @param y 열
 * @return (x,y)가 n*n 배열 범위 내에 있으면 true, 아니면 false
 */
bool inRange(int x, int y){
    return (0<=x && x<n && 0<=y && y<n);
}

/**
 * (x,y)에서 이동 가능한 모든 칸을 탐색하고, 최대 일수를 구한다
 * @param x 현재 위치한 행
 * @param y 현재 위치한 열
 * @return 현재 칸에서부터 시작했을 때의 최대 일수
 */
int dfs(int x, int y){
    int temp;
    path[x][y] = 1;

    //동서남북 방향으로 이동 했을 때의 최대 일수를 각각 구하고
    //그 값들 중에서 최대값을 구해서 path[x][y]에 저장한다
    for(int i=0; i<4; i++){
        int nx = x+dir_x[i]; int ny = y+dir_y[i];
        //이웃 노드로 이동 가능한 경우
        if(inRange(nx,ny) && forest[nx][ny]>forest[x][y]) {
            //이미 최대 일수가 계산되어 있을 때 (이미 방문한 칸)
            if (path[nx][ny] != 0)
                temp = path[nx][ny]+1;
            //최대 일수가 계산되어 있지 않을 때
            else
                temp = dfs(x + dir_x[i], y + dir_y[i])+1;
            //최댓값을 구해준다
            if(temp>path[x][y])
                path[x][y] = temp;
        }
    }
    //현재 칸에서 시작했을 때의 최대일수를 반환해준다
    return path[x][y];
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int dist;

    //대나무 숲에 대한 정보를 입력 받는다
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            cin >> forest[i][j];
    }

    //각 칸 별로 dfs()를 수행해서 각 칸에서 시작했을 때의 최대 일수를 구한다
    //이미 구한 경우, path[i][j]를 이용한다
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(path[i][j]==0)
                dist = dfs(i,j);
            else
                dist = path[i][j];
            //최대값을 구해준다
            if(dist>max_dist)
                max_dist = dist;
        }
    }

    cout<<max_dist;
}