글 읽기 - dfs + dp 말고 bfs + pq 로 풀었습니다만,

phcdream 3년 전 3

순서

1. bfs+pq 아이디어

2.비슷한 문제와 의문점

3.dfs + dp와의 bfs + pq 알고리즘 효율성

1. bfs+pq 아이디어는 밑의 예제에서

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

문제의 3가지 경로에서 2번째경로(50->...->32->20->...)랑 3번째 경로(50->...->32...->25->20->...)가 겹치는 부분에서,

.........현재칸-> 가능한다음칸

현재칸 32 -> 30, 20 가능한 다음칸 우선순위큐 삽입

다음탐색: 30 -> 25 삽입

다음탐색:25->20 (이전에 탐색된값 삽입X)

이런식으로 다른경로에서 마저 도착할수있도록 우선순위큐로 기다려주게 했습니다.

2. 유사한 문제가 있습니다.

4485번: 녹색 옷 입은 애가 젤다지? (acmicpc.net)

이문제는 분류가 다익스트라 입니다.

4485번 젤다 문제는 지나간 합이 최소가 되게하는것이고,

1520번 내리막길은 시작점으로 부터 현재칸과의 차이가 최소가 되는 칸을 선택했습니다.

즉, 우선순위큐에는 현재칸의 높이를 넣어, 큰값부터 빠져나오게했습니다.(max-heap)

visited(다음칸)가 0일때만 우선순위큐에 넣어주고, visited(다음칸)+=visited(현재칸)로 visited갱신헀습니다.

내리막길문제는 시작점50->끝점10까지의 거리가 무조건 40인 그래프문제이고,

경로탐색할때, 차이가 작은값(50-N이 작아야하니까 이문제에서는 칸의 값이 큰값)부터 탐색하는 다익스트라가 아닌가 생각이듭니다.

젤다문제를 보고 나니까 이문제도 다익스트라가 될수있는지 궁금합니다.

3. 잘못된 풀이라면 해당 알고리즘에서 빠진조건(저격데이터)이 있는지,

올바른 풀이라면 이렇게 풀어도 되는지,

아니라면, N,M 값이 커지게 되면, dfs+dp 보다 느려서 시간초과가 날지 궁금합니다.

24240333번 소스 코드 (acmicpc.net)

/**
 *    BOJ 1520
 *    - 내리막 길
 *    author:  phcdream
 *    created: 오후 9:14 2020-12-06
**/

#include <iostream>
#include <queue>

typedef long long ll;

using namespace std;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };

struct MyPoint
{
	int y;
	int x;
	int n;
	bool operator<(const MyPoint& mp)const {		//	less -> max-heap
		return n < mp.n;
	}
};

void in(int& N, int& M, int**& arr)
{
	cin >> N >> M;
	arr = new int* [(ll)N + 2];
	fill(arr, arr + N + 2, nullptr);
	for (int i = 0; i < N + 2; i++)
	{
		arr[i] = new int[(ll)M + 2];
		fill(arr[i], arr[i] + M + 2, -1);
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
			cin >> arr[i][j];
	}
}

void print(int N, int M, int** visited)
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cout << visited[i][j] << " ";
		}cout << "\n";
	}cout << "\n";
}

void bfs(int N, int M, int**& arr, int**& visited)
{
	MyPoint st = MyPoint({ 1,1,arr[1][1] });
	priority_queue<MyPoint> pq;
	visited[st.y][st.x] = 1;
	pq.push(st);
	while (true)
	{
		if (pq.empty())
			break;
		st = pq.top();
		pq.pop();
		for (int i = 0; i < 4; i++)
		{
			int nY = st.y + dy[i];
			int nX = st.x + dx[i];
			if (arr[nY][nX] != -1 && arr[st.y][st.x] > arr[nY][nX])
			{
				if (visited[nY][nX] == 0)
				{
					pq.push({ nY,nX,arr[nY][nX] });
				}
				visited[nY][nX] += visited[st.y][st.x];
			}

		}
	}
}

int solve(int N, int M, int**& arr)
{
	int** visited = new int* [(ll)N + 2];
	fill(visited, visited + N + 2, nullptr);
	for (int i = 0; i < N + 2; i++)
	{
		visited[i] = new int[(ll)M + 2];
		fill(visited[i], visited[i] + M + 2, 0);
	}

	bfs(N, M, arr, visited);

	//print(N, M, visited);

	return visited[N][M];
}

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

	int M, N;
	int** arr;
	in(N, M, arr);

	int re = solve(N, M, arr);
	cout << re << "\n";

	return 0;
}

phcdream 3년 전 0

이게 바텀업 방식일까요??

baekjoon 3년 전 7

문제에 나와있는 이동 조건을 이용해 그래프를 그리면 DAG가 나오기 때문에 BFS로 풀 수 있습니다.

구현하신 것 처럼 우선 순위 큐를 사용해도 되고, 모든 칸의 값을 별도의 배열에 저장한 다음, 내림차순 정렬해 그 순서로 문제를 해결해도 됩니다.

내리막길은 경로의 개수를 구하는 문제니 다익스트라를 사용할 수 없습니다.

올바른 풀이입니다.

댓글을 작성하려면 로그인해야 합니다.