글 읽기 - 보물섬 틀린 이유를 모르겠습니다!!

king102900 8년 전 0

BFS 를 우선 한번 돌려서 가장 긴 육지 끝점중 하나를 찾습니다.

그리고 다시 그점에서 BFS를 하며 time 을 비교합니다.

그래서 가장 큰 time 값을 출력하게 했습니다!!ㅠ

그런데 기본 테스트케이스랑 몇가지 넣어본 예제는 맞았는데

제출은 오답이네요ㅠㅠ 도와주시면 감사하겠습니다!!

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX_M_COUNT 50
#define MAX_N_COUNT 50


struct treasure
{
	int idx;
	int x,y;
	int time;

	treasure(){};
	treasure(int _idx, int _x, int _y, int _time) : idx(_idx), x(_x), y(_y), time(_time){};
};

char map[MAX_N_COUNT][MAX_M_COUNT];
int visited[MAX_N_COUNT][MAX_M_COUNT] = {0, };
treasure tr[MAX_N_COUNT*MAX_M_COUNT];

int maxPow[MAX_N_COUNT*MAX_M_COUNT][3] = {0, };

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

int main()
{
	int N,M;
	int step=1;
	int max_time = -1;

	queue<treasure> q;

	scanf("%d %d",&N, &M);

	for(int i=0; i<N; i++)
	{
		scanf("%s",map[i]);
	}

	// 구조체에 좌표, 시간, idx 를 담아서 순회를 하고 순회가 끝났을때 가장 시간이 높은 곳의 좌표를 받는다.
	// 그리고 가장 높은곳에서 다시 같은 idx 무리들을 순회해서 시간을 새로 담고, 순회가 끝났을때 가장 시간이 큰값이 그 무리의 최단거리이다.
	// 그리고 맵의 모든 여러 무리들을 다 순회한다.

	for(int k=0; k<N; k++)
	{
		for(int p=0; p<M; p++)
		{
			if(map[k][p]=='L' && visited[k][p]== 0 )
			{
				tr[step].idx = step;
				tr[step].x = p;
				tr[step].y = k;
				tr[step].time = 0;

				q.push( tr[step] );
				visited[k][p] = step;
				maxPow[step][2]=-1;

				while( !q.empty() )
				{
					int idx = q.front().idx;
					int x = q.front().x;
					int y = q.front().y;
					int time = q.front().time;
					if( time > maxPow[step][2] )
					{
						//max_time = time;
						maxPow[step][0] = x;
						maxPow[step][1] = y;
						maxPow[step][2] = time;
						//if(max_time >=6)
						//{
						//	printf("%d, %d, %d\n",x,y,max_time);
						//}
					}

					q.pop();
					
					for(int i=0; i<4; i++)
					{
						int next_x = x + dx[i];
						int next_y = y + dy[i];
						if(next_x < 0 || next_y < 0 || next_x >= M || next_y >= N ) continue;
						if(map[next_y][next_x]=='L' && visited[next_y][next_x] == 0)
						{
							visited[next_y][next_x] = step;
							q.push( treasure(idx,next_x,next_y,time+1) );
						}
					}
				}
				// 가장높은 지점에서 다시 bfs 를 한다.
				//max_time = -1;

				tr[step].idx = step;
				tr[step].x = maxPow[step][0];
				tr[step].y = maxPow[step][1];
				tr[step].time = 0;

				q.push( tr[step] );
				visited[maxPow[step][1]][maxPow[step][0]] = -1;

				while( !q.empty() )
				{
					int idx = q.front().idx;
					int x = q.front().x;
					int y = q.front().y;
					int time = q.front().time;
					if( time > max_time )
					{
						max_time = time;
					}

					q.pop();
					
					for(int i=0; i<4; i++)
					{
						int next_x = x + dx[i];
						int next_y = y + dy[i];
						if(next_x < 0 || next_y < 0 || next_x >= M || next_y >= N ) continue;
						if(map[next_y][next_x]=='L' && visited[next_y][next_x] == step)
						{
							visited[next_y][next_x] = -1;
							q.push( treasure(idx,next_x,next_y,time+1) );
						}
					}
				}

				step++;
			}
		}
	}

	//for(int i=0; i<N; i++)
	//{
	//	for(int j=0; j<M; j++)
	//	{
	//		//printf("visited[%d][%d] : %d ",i,j,visited[i][j]);
	//		printf("%d ",visited[i][j]);
	//	}
	//	printf("\n");
	//}
	//for(int i=0; i<N; i++)
	//{
	//	for(int j=0; j<M; j++)
	//	{
	//		printf("map[%d][%d] : %c",i,j,map[i][j]);
	//	}
	//	printf("\n");
	//}
	//
	printf("%d ",max_time);

	return 0;
}

hj_d 8년 전 2

음... 제가 봤을때는요....... 모든 지상에서 탐색을해서 최대 시간을 구해야 할거 같은데요? 크기도 50*50 이라서 시간 초과 안뜰거 같은데.....

일단 그렇게 해보세요.

king102900 8년 전 0

@hj_d 감사합니다!

red5857 8년 전 0

커헉.. 저도 섬당 2번씩 돌려서 최단거리를 찾는 방법으로 했다가 댓글 보고 깨닫고 갑니다 ㅠㅠ

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

문제

문제

출처

ICPC

보물섬 틀린 이유를 모르겠습니다!!

king102900 8년 전 0

hj_d 8년 전 2

king102900 8년 전 0

red5857 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말