백준[BOJ] 1520번 : 내리막길

1520번: 내리막 길

 

처음 문제의 이미지를 보자마자 깊이우선탐색/넓이우선탐색 문제일것이라는 생각이 들었다.

경로의 개수를 찾아야하는 이 문제에서는 DFS가 적합하다는 직감이 느껴졌다.

이 문제에서는 여러 종류의 경로가 서로 중첩되는 경우를 반드시 고려해야한다.

 

만약 BFS로 탐색을 진행하게 되면

가능한 모든 경로를, 같은 깊이로, 탐색을 진행한다.

이 때에는 (다른 깊이, 같은 지점)에서 만났을 경우를 처리하는 게 복잡하다고 생각된다.

이 글 쓰고 나서 시도해봐야겠다.

 

DFS로 가능한 하나의 경로를 찾은 다음 그 정보를 저장한다.

다른 경로를 찾다가 이미 지났던 경로를 마주치면

그 지점에서 목표하는 지점까지의 경로의 개수를 더해주고 다른 경로를 찾으러 간다.

 

1) 이전에 탐색했던 길에 대한 정보를 저장한다.

2) 해당 지점을 다시 방문하게 되면, 그 지점부터 목표지점까지의 탐색을 다시 진행하지 않아도 된다.

  저장되어 있는 정보를 불러오고 현재 경로 탐색은 끝난다. 다른 경로를 탐색한다.

3) 가능한 모든 길을 가봤으면 탐색을 종료한다. 

 

그러면 이제 정보를 저장하는 방법을 생각해야한다.

이 부분이 이 문제의 핵심지점이라고 생각이 든다.

어떤 정보를 저장해야하는가? 어떻게 활용하는게 효과적인가?

개인적으로는 이 방법을 고민하는데에 가장 많은 시간을 사용했다.

 

경로 자체(방문 순서)를 저장해야할까?

아니면 경로의 개수를 저장해야할까??

 

처음 생각했던 것 > "변수를 하나 선언, 유효한 길을 찾을 때마다 1씩 더해주자!"

                          경로가 겹칠 때에는,, 1을 더해주고 탐색을 종료... 하면 안되는데??

                          겹치는 지점에서 목표지점까지 몇개의 경로가 있을지 모른다.

                          따라서 필요한 정보는, 어떤 지점에서 목표지점까지의 경로 개수이다.

 

다시 경로가 겹치는 상황을 생각해보자.

1) 내가 나아가려는 지점(오른쪽 위쪽 왼쪽 아래쪽)을 살펴본다.

2-1) 이미 그곳에서 탐색을 진행했었으면, 그곳에 저장된 경로 개수를 현재 지점에 추가해준다.

2-2) 처음 방문하는 곳, 계속 탐색을 진행, 나중에 스택에서 빠져나오면서 종합된 경로 개수를 현재 지점에 추가해준다. 

그래야 '현재 지점에 저장된 정보'가 위에서 정의한대로 "현재 지점에서 목표지점까지의 경로 개수"로 정의된다.

 

 

따라서 필요한 변수는 

 - bool visited[i][j] : ( i , j ) 지점 방문여부를 저장하는 배열 (default = false)

 - int dp[i][j] : ( i , j ) 에서 목표지점( M, N )까지의 가능한 경로의 개수 (default는 false)

 - int path[i][j] : ( i , j )의 높이 (입력받을 배열)

  (default =INT_MAX, 낮은 길로 가야한다. 입력범위 밖으로 진행하지 않기 위해 가장 높게 설정)

 

#include <iostream>
#include <climits>
using namespace std;

bool visited[510][510];
int path[510][510];
int dp[510][510];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int dfs(int cur_row, int cur_col, int fin_row, int fin_col);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   
    for (auto cur : path)
        *cur = INT_MAX;

    int m, n;

    cin >> m >> n;

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            cin >> path[i][j];
        }
    
    cout << dfs(1, 1, m, n);
}

// (i,j)에서 (m,n)까지의 가능한 경로의 개수를 반환
int dfs(int i, int j, int m, int n) {

	// Terminal Case1 : 방문했던 곳이면 경로 개수를 리턴
    if (visited[i][j])  return dp[i][j]; 
    
    else {
  
        visited[i][j] = true;
		
        // Terminal Case2 : 목표지점에 도달
        if (i == m && j == n) {
            dp[i][j] += 1;

            return dp[i][j];
        }
        
        // Terminal Case3 : 직사각형 영역을 빠져나갔을 경우
        else if (i > m || i < 1 || j > n || j < 1)   

            return dp[i][j] = 0;
        
        
        // NOT Terminal Case
        else {
            for (int t = 0; t < 4; t++)           
            	// 낮은 곳이면 진행, 유효한 경로 개수를 다 더해준다.
                if (path[i + dx[t]][j + dy[t]] < path[i][j]) 
                    dp[i][j] += dfs(i + dx[t], j + dy[t], m, n);
                
            
            return dp[i][j];
        }
    }
}