글 읽기 - dp말고 우선순위 큐로 풀순없나요?

hbk388 5년 전 0

우선순위 큐 + 다익스트라를 이용해서 풀어보려고 했습니다.

그런데 9%에서 시간초과가 뜹니다.

제가 푼 방식이 어디서 시간이 많이걸리길래 시간초과가 뜨는걸까요... 도와주세요.ㅠ

갔던 곳을 다시 가지않기 위해 왔던 방향을 저장해서 다시 그곳으로 안가도록 했습니다.

#include <stdio.h>
int arr[1010][1010];
int ans[1010][1010][3]; // ans[x좌표][y좌표][0 : 아래로 온 경우, 1 : 오른쪽에서 온 경우 2 : 왼쪽에서 온 경우]
int N, M, st, ed,tval,tx,ty,tfrom;
struct ss {
	int x, y, value,from; // x , y 좌표 value 가치 , from 어디서왔는지
}q[1000000],sst;

void push() // 우선순위 큐 삽입.
{
	int temp = ed;
	while (temp >= 2)
	{
		if (q[temp].value > q[temp / 2].value)
		{
			sst = q[temp], q[temp] = q[temp / 2], q[temp / 2] = sst;
			temp = temp / 2;
		}
		else
			break;
	}
}

void pop() // 우선순위 큐 제거.
{
	int temp = 1;
	sst = q[1], q[1] = q[ed], q[ed] = sst;
	q[ed--].value = -1111111111;

	while (temp <= ed / 2)
	{
		if (q[temp].value < q[temp * 2].value || q[temp].value < q[temp * 2 + 1].value)
		{
			if (q[temp * 2].value > q[temp * 2 + 1].value)
			{
				sst = q[temp], q[temp] = q[temp * 2], q[temp * 2] = sst;
				temp = temp * 2;
			}
			else
			{
				sst = q[temp * 2 + 1], q[temp * 2 + 1] = q[temp], q[temp] = sst;
				temp = temp * 2 + 1;
			}
		}
		else
			break;
	}
}

int main(void)
{
	int i, j, k;
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= M; j++)
		{
			scanf("%d", &arr[i][j]);
			for (k = 0; k < 3; k++)
				ans[i][j][k] = -1111111111; // 모든 값 최소 값으로 초기화
		}
	}
	q[++ed].x = 1, q[ed].y = 1;
	ans[1][1][0] = arr[1][1];
	q[ed].from = 0; q[ed].value = arr[1][1];

	while (ed != 0)
	{
		if (q[1].value < ans[q[1].x][q[1].y][q[1].from])
		{
			pop();
			continue;
		}
		tval = q[1].value;
		tx = q[1].x, ty = q[1].y;
		tfrom = q[1].from;
		pop();
		if (tx != N) // 아래 방향으로 갈 때
		{
			if (tval + arr[tx + 1][ty] > ans[tx + 1][ty][0])
			{
				q[++ed].x = tx + 1;
				q[ed].y = ty;
				q[ed].value = tval + arr[q[ed].x][q[ed].y];
				ans[q[ed].x][q[ed].y][0] = q[ed].value;
				q[ed].from = 0;
				push();
			}
		}
		if (tfrom != 2 && ty != 1) // 왼쪽 방향으로 갈 때
		{
			if (tval + arr[tx][ty - 1] > ans[tx][ty - 1][1])
			{
				q[++ed].x = tx;
				q[ed].y = ty - 1;
				q[ed].value = tval + arr[q[ed].x][q[ed].y];
				ans[q[ed].x][q[ed].y][1] = q[ed].value;
				q[ed].from = 1;
				push();
			}
		}
		if (tfrom != 1 && ty != M) // 오른쪽 방향으로 갈 때
		{
			if (tval + arr[tx][ty + 1] > ans[tx][ty + 1][2])
			{
				q[++ed].x = tx;
				q[ed].y = ty + 1;
				q[ed].value = tval + arr[q[ed].x][q[ed].y];
				ans[q[ed].x][q[ed].y][2] = q[ed].value;
				q[ed].from = 2;
				push();
			}
		}
	}
	int max = -1111111111;
	for (i = 0; i < 3; i++)
		if (max < ans[N][M][i])
			max = ans[N][M][i];
	printf("%d", max);
	return 0;
}

juhongkim2 5년 전 0

반례는 아니고

3 3

1 1 1

(1,1)에서 출발해서 먼저 아래로 세번 가서 (3,1) ans[3][1][0]=3이 됩니다.(pq에 들어가겠죠)

그 다음에 또 여러번 돌다가 r d d l 방향으로 움직여서 ans[3][1][1]=5가 됩니다.(마찬가지로 pq에 또 들어갑니다) 다른 경로로 탐색으로 하면 ans[3][1][1]=7로 갱신되면서 또 pq에 들어갑니다.

다른 방향으로 탐색을 하면 ans[3][1][0]=5로 갱신되면서 또 pq에 들어갑니다.

대충 돌려봐도 (3,1)좌표에 대한 ans값이 4번 갱신됩니다. 올려주신 코드를 보니 (x,y)에 대해 ans[x][y]가 갱신될때마다 pq에 들어가니 4번 들어가겠네요

중복방문을 걸러주시려고 했는데 4번이나 들어가는거네요

이 N이 커질수록 같은좌표가 pq에 여러번 들어가는 빈도가 늘어날테고 이런이유로 시간초과가 나는것 같습니다...

juhongkim2 5년 전 0

입력된 map을 그래프처럼 생각하시고 다익스트라 알고리즘을 사용하시려고 한 것 같은데

다익스트라 알고리즘은 최단거리를 구하는 알고리즘이고 이 문제map을 그래프처럼 생각하고 풀려면 최단경로가 아닌 최장경로를 구해야하는 문제아닐까요?(이부분은 고수님들 의견이 궁금합니다.)

저는 이 문제 그래프처럼 생각하면 최장경로를 구해야한다고 생각해서 다익스트라를 쓰지 않았습니다.

그리고 최단경로를 구하는 문제였다고 해도 이 문제는 map에 음수값도 들어오고 이를 그래프라 생각하면 음수간선이 존재하기때문에 다익스트라 알고리즘은 사용할 수 없을 것 같습니다.

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

문제

문제

출처

ICPC

dp말고 우선순위 큐로 풀순없나요?

hbk388 5년 전 0

juhongkim2 5년 전 0

juhongkim2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말