백준 1520번 _ 내리막 길

2020-05-04 · 배운 것 · 4분 읽기

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

접근

주어진 조건들을 먼저보자.
시간은 2초, MxN 행렬 (M, N <=500), 다음 위치는 현재위치보다 무조건 낮다.

먼저 생각해 볼수 있는건 DFS다. 그런데 잘 생각해보면 이게 방향이 우측, 아래로만 간다는 조건도 없고 사방으로 갈수있기 때문에 대충 생각해봐도 시간오바다. ( 계산을 해서 보여주고 싶지만... 어떻게 계산해야될지도 모르겠다. 하지만, 2초라는 시간 안에는 수행할수 없다는것은 당연히 직관적으로 이해될 것임으로 넘어가겠다. )

그렇다면 시간을 줄여야 할까?
잘 생각해보면 도착점까지 간 경로에 포함된 곳에 다시 가는것은 시간낭비라는것을 알수있다. (이해가 안된다면 밑에 그림 참조)

풀이방법

정답부터 말하자면 DFS에 DP를 더해서 푸는 방법으로 풀 수있는 문제다.
그렇다면 어떻게 DP를 적용할수 있을까?

바로 도착점에 도달했던 경로에 겹치게 되면 바로 RETURN시켜 필요없는 연산을 하지 않는것이다. ( 가지치기 )
DP[i][j] : i, j 지점에서 도착지점까지 갈수있는 경로의 개수 , 처음에 가보지 않은 지점은 -1로 초기화 할것.

(동작에 대한 GIF가 있으니 밑의 블로그에서 보면 이해가 빠를것이다.)

https://wootool.tistory.com/83

(백준)(1520번)(DP) 내리막길

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int map[501][501];
int visited[501][501];
int M, N;
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

void visitedInit()
{
	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			visited[i][j] = -1;
}

void Input()
{
	cin >> M >> N;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
		}
	}
}

bool inRange(int y, int x)
{
	if (y >= 0 && x >= 0 && y < M && x < N)
		return true;
	return false;
}

int dfs(int y, int x)
{
	//목적지 도착
	if (y == M - 1 && x == N - 1)
		return 1;
	//이미 도착점에 도착했던 경로가 있을때
	if (visited[y][x]!=-1)
		return visited[y][x];
	
	visited[y][x] = 0;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (inRange(ny, nx) == false)
			continue;
		//항상 더 낮은 지점으로만 움직일수 있다.
		if (map[y][x] <= map[ny][nx])
			continue;

		visited[y][x] += dfs(ny, nx);
	}

	return visited[y][x];
}

int main()
{
	Input();
	visitedInit();
	cout << dfs(0, 0);

	return 0;
}

후기

비슷한 카카오 문제를 풀어본적 있는데 그것과는 다른 방식으로 문제를 풀었다.