[백준 1520] 내리막길

klean·2021년 6월 22일
0

문제요약

M*N 사이즈의 2차원 배열 지도의 칸 별 높이가 주어집니다.
이 배열에서 세준이는 내리막길로만 움직이려고 합니다.
사실 경로의 길이라든가 내리막의 경사라든가 하는 건 세준이는 개나 줘버렸습니다.
세준이가 (0,0)에서 출발해서 (M-1,N-1)로 갈 수 있는 경우의 수를 구하세요.

아이디어

DFS 를 재귀적으로 구현하여 DP와 혼용해서 사용했다. DFS 함수의 리턴값은 "해당 위치에서 (M-1,N-1) 위치로 갈 수 있는 방법의 수"로 하였다.

DP와 혼용?

거창한 기법 같지만 그냥 별거 없다. DFS를 이미 수행한 지점을 다시 만났을 때를 대비하여 "해당 위치에서/출발해서 (M-1,N-1) 위치로 갈 수 있는 방법의 수"(함수의 리턴값)를 저장하는 것이다.

삽질

1. 스택을 써서 DFS를 구현

스택을 쓰면 DFS의 구현은 쉬워지지만 (0,0) 위치에서 모든 경우의 수를 리턴 받아야하는 이 코드의 경우 좋지 않다.

2. 경우의 수를 축적하는 위치 : (M-1,N-1) VS (0,0) , visited 배열의 의미

DFS를 수행할 때 각 위치에 도착했을 때마다 visited 배열을 1씩 증가시키는 것도 하나의 방법이다.(즉 visited 배열은 (0,0)에서 해당 위치까지 도달 가능한 경우의 수로 마지막엔 visited[m-1][n-1] 참고)

그런데 그렇게 했을 때 위에 말한 DP적으로 이미 순회한 데이터를 참고하는 방법이 통하기 어렵고 직접 반복적으로 방문을 해서 +1을 해줘야한다는 생각이 들었다.(해결 방법을 아신다면 댓글로 공유해주심 감사하겠습니다.)

그래서 차라리 리턴하면서 가능했던 경우의 수를 합산해주자는 생각을 했다.

소스코드

#include<iostream>
#include<memory.h>
#include<iomanip>
using namespace std;
struct pos {
	int i, j;
};
int m, n;
bool inbox(int i, int j) {
	return i >= 0 && i < m&& j >= 0 && j < n;
}
int tab[500][500];
//dp적으로 dfs
int visited[500][500];
int di[] = { 1,-1,0,0 };
int dj[] = { 0,0,1,-1 };

int dfs(pos cur) {
	int sum_children = 0;
	for (int k = 0; k < 4; k++) {
		pos ch = pos{ cur.i + di[k],cur.j + dj[k] };
		
		if (inbox(ch.i, ch.j)&&tab[ch.i][ch.j]<tab[cur.i][cur.j]) {
			if (visited[ch.i][ch.j] == -1) {
				sum_children += dfs(ch);
			}
			else {
				sum_children += visited[ch.i][ch.j];
			}
		}
	}
	visited[cur.i][cur.j] = sum_children;
	//cout << "합산후 : " << cur.i << " , " << cur.j << endl;
	//print_visited();
	return visited[cur.i][cur.j];
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tab[i][j];
			visited[i][j] = -1;//init as unvisited
		}
	}
	visited[m - 1][n - 1] = 1;
	dfs(pos{ 0,0 });
	//print_visited();
	cout << visited[0][0];
}

미래의 나에게

이 문제는 아이디어 내느라고 다양한 해결방법이 적용 가능한지 고민했던 문제이므로 파랑색 노트를 보도록하렴

0개의 댓글