글 읽기 - 시간초과가 걸릴수 밖에 없게 짠건가요?

dhedaa 7년 전 0

벽을 한번만 부술수 있으니까 쉽게 생각해서 벽을 한개씩 부순다음에 bfs 돌려봤거등요?

이러면 당연히 시간초과가 날수밖에 없는건가요?

5 8
01000000
01010000
01010000
01010011
00010010

이 테스트 케이스 때문에 제대로 못풀겠네요...ㅠ

#include <iostream>
#include <queue>

using namespace std;

int map[1000][1000], visited[1000][1000];
int n, m, cnt;
queue<pair<int, int>> q;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void bfs(int x, int y)
{	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			visited[i][j] = 0;
		}
	}
    cnt = 0;
	visited[y][x] = 1;
	q.push(make_pair(x, y));
	while (!q.empty())
	{
		int a = q.front().first;
		int b = q.front().second;
		if (a == m - 1 && b == n - 1)
		{
			cnt = visited[b][a];			
		}
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = a + dx[i];
			int ny = b + dy[i];
			if (nx > -1 && ny > -1 && nx < m && ny < n && map[ny][nx] == 0 && visited[ny][nx] == 0)
			{
				visited[ny][nx] = visited[b][a] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}

}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);

	int res = n * m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 1)
			{
				map[i][j] = 0;				
				bfs(0, 0);
				if (res > cnt && cnt > 0)
				{
					res = cnt;
				}
				map[i][j] = 1;
			}
		}
	}
	bfs(0, 0);
	
	if (cnt > 0)
	{
		if (res > cnt)
		{
			res = cnt;
		}		
	}
	if(res > 0) cout << res << endl;
	else cout << "-1" << endl;

}

dotorya 7년 전 0

벽을 하나씩 부숴보고 진행하는 알고리즘의 시간복잡도를 생각해 보면,

부숴봐야 할 벽의 개수 : 최대 O(NM)

BFS 한 번에 필요한 시간 : O(NM)

-> 총 시간복잡도 O(N^2M^2) ~ 10^12

1초에 대략 10^8번 정도의 연산을 수행할 수 있으니까, 이 풀이는 확실히 TLE가 날 것 같넨요.

이 문제는 BFS 한 번만 수행해도 풀 수 있는 문제입니다.

좀 더 생각해 보세요!

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

문제

문제

출처

ICPC

시간초과가 걸릴수 밖에 없게 짠건가요?

dhedaa 7년 전 0

dotorya 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말