글 읽기 - 시간을 어떻게 하면 줄일 수 있을까요?

tlonist_harry 7년 전 0

계속 시간초과가 뜹니다.

100ms 안으로 푸는 방법도 궁금하고, 여기서 어떤 방식으로 시간을 줄일 수 있을지 궁금해서 고수분들의 의견을 구합니다.

#include <stdio.h>
#define enq(X) (queue[wt++] = (X))
#define deq(X) ((X) = queue[rd++])
#define qne (wt>rd)
#define INF (0x7fffffff)

//아예 바이킹의 시야에서 사라져야 한다.
int wt, rd;
int R, C;
int dr[] = { 1, -1, 0, 0 };
int dc[] = { 0, 0, 1, -1 };
char a[705][705];
int visited[3][705][705];
int yr, yc;
int vr, vc;
int tr, tc;

typedef struct
{
	int r;
	int c;
	char p;
}QUEUE;
QUEUE queue[700 * 700 * 7];
QUEUE data, ndata;

void mark_visited(int r, int c)
{
	int i;
	for (i = c; a[r][i] != 'I' && i <= C; i++)  visited[0][r][i] = -1;
	for (i = c; a[r][i] != 'I' && i >= 1; i--)  visited[0][r][i] = -1;
	for (i = r; a[i][c] != 'I' && i <= R; i++)  visited[0][i][c] = -1;
	for (i = r; a[i][c] != 'I' && i >= 1; i--)  visited[0][i][c] = -1;
}


void Input_Data(void)
{
	//항상 수아를 먼저 enqueue
	int i, j;
	scanf("%d %d", &R, &C);
	for (i = 1; i <= R; i++)
	{
		scanf("%s", &a[i][1]);
		for (j = 1; j <= C; j++)
		{
			if (a[i][j] == 'Y')
			{
				yr = i;
				yc = j;
			}
			if (a[i][j] == 'V')
			{
				vr = i;
				vc = j;
			}
			if (a[i][j] == 'T')
			{
				tr = i;
				tc = j;
			}
		}
	}
	data.r = yr;
	data.c = yc;
	data.p = 'Y';
	enq(data);
	visited[2][yr][yc] = 1;
	data.r = vr;
	data.c = vc;
	data.p = 'V';
	enq(data);
	visited[1][vr][vc] = 1;
}

int Pirate_Move(void) 
{
	register int i , j;
	while (qne)
	{
		deq(data);	
		if (data.p == 'Y' && visited[0][data.r][data.c] == -1) continue;
		if (data.p == 'Y' && a[data.r][data.c] == 'T') return 1;

		ndata.p = data.p;
		for (i = 0; i < 4; i++)
		{
			ndata.r = data.r + dr[i];
			ndata.c = data.c + dc[i];

			if (ndata.r<1 || ndata.r>R || ndata.c<1 || ndata.c>C) continue;
			if (a[ndata.r][ndata.c] == 'I') continue;

			if (ndata.p == 'Y')
			{
				if (visited[2][ndata.r][ndata.c]) continue;
				if (visited[0][ndata.r][ndata.c] == -1)	continue;					
				visited[2][ndata.r][ndata.c] = 1;
				enq(ndata);
			}
			if (ndata.p == 'V')
			{
				if (visited[1][ndata.r][ndata.c]) continue;
				mark_visited(ndata.r, ndata.c);
				if (visited[0][tr][tc] == -1 || visited[1][ndata.r][ndata.c]) return 0;
				visited[1][ndata.r][ndata.c] = 1;
				enq(ndata);
			}
		}
	}

	return 0;
}

int main(void)
{
	Input_Data();	
	if (Pirate_Move())
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	return 0;
}

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

문제

문제

출처

ICPC

시간을 어떻게 하면 줄일 수 있을까요?

tlonist_harry 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말