글 읽기 - 시간초과가 뜹니다. 한번만 읽어주세요!

bgjuw12 5년 전 0

제출을 했을때 시간 초과가 나옵니다.

테스트케이스를 돌리면 올바른 답이 나옵니다

다만 보통 복붙을 하면 바로바로 답이 나와야하는데

이 문제는 제가 복붙을 하는순간 마지막 케이스꺼에서 커서가 띄워져있고 엔터를 쳐줘야 나오더라구요

이게문제인걸까요??

최대한 시간을 줄여보려고 if문에 덕지덕지 붙였는데 계속 초과가 뜨네요.

이유를 알고싶습니다 ㅠㅠ

도와주세요!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int w, h;

char (*fire_expand(char (*fire)[1002]))[1002]
{
	vector<pair<int, int>> point;
	for (int i = 1; i < h+1; i++)
	{
		for (int j = 1; j < w + 1; j++)
		{
			if (fire[i][j] == '*')				point.push_back(make_pair(i, j));
		}
	}

	for (int i = 0; i < point.size(); i++)
	{
		int x = point[i].first, y = point[i].second;
		//위로 확장
		if (x - 1 != 0 && fire[x - 1][y] != '#' && fire[x - 1][y] != '*')			fire[x - 1][y] = '*';
		//아래로 확장
		if (x + 1 != h + 1 && fire[x + 1][y] != '#' && fire[x + 1][y] != '*')			fire[x + 1][y] = '*';
		//왼쪽으로 확장
		if (y - 1 != 0 && fire[x][y - 1] != '#' && fire[x][y - 1] != '*')			fire[x][y - 1] = '*';
		//오른쪽으로 확장
		if (y + 1 != w + 1 && fire[x][y + 1] != '#' && fire[x][y + 1] != '*')			fire[x][y + 1] = '*';
	}
	return fire;
}

int dfs(char (*room_temp)[1002], pair<int, int> person, int cnt)
{
	int result[4] = { 1000000,1000000,1000000,1000000 }, x = person.first, y = person.second, answer= 1000000;
	char (*fire_expanded_room)[1002] = fire_expand(room_temp);
	//탈출했을때
	if (x < 1 || y < 1 || x > h || y > w)		return cnt;

	//위로 이동
	if (fire_expanded_room[x - 1][y] != '#' && fire_expanded_room[x - 1][y] != '*')			result[0] = dfs(fire_expanded_room,make_pair(x-1,y),cnt+1);
	//아래로 이동
	if (fire_expanded_room[x + 1][y] != '#' && fire_expanded_room[x + 1][y] != '*')			result[1] = dfs(fire_expanded_room, make_pair(x + 1, y), cnt + 1);
	//왼쪽으로 이동
	if (fire_expanded_room[x][y - 1] != '#' && fire_expanded_room[x][y - 1] != '*')			result[2] = dfs(fire_expanded_room, make_pair(x, y - 1), cnt + 1);
	//오른쪽으로 이동
	if (fire_expanded_room[x][y + 1] != '#' && fire_expanded_room[x][y + 1] != '*')			result[3] = dfs(fire_expanded_room, make_pair(x, y + 1), cnt + 1);
	
	answer = min(result[0], result[1]);
	answer = min(answer, result[2]);
	answer = min(answer, result[3]);

	return answer;
}

int main()
{
	int T, answer;
	char room[1002][1002] = {' ',};
	
	cin >> T;

	while (T--)
	{
		pair<int, int> person; // 사람 위치 좌표로 저장
		cin >> w >> h;
		for (int i = 1; i < h + 1; i++)
		{
			for (int j = 1; j < w + 1; j++)
			{
				cin >> room[i][j];
				if (room[i][j] == '@')		person = make_pair(i, j);
			}
		}

		answer = dfs(room, person, 0);
		if (answer == 100000)		cout << "IMPOSSIBLE" << endl;
		else
		{
			cout << answer << endl;
		}
	}
}

djm03178 5년 전 1

최단 경로 문제는 DFS가 아니라 BFS로 풀어야 합니다. 알고리즘 분류에도 BFS만 있는 것을 볼 수 있습니다.

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

문제

문제

출처

ICPC

시간초과가 뜹니다. 한번만 읽어주세요!

bgjuw12 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말