글 읽기 - "5247-불" 시간초과 문제

wony6731 5년 전 0

항상 시간복잡도를 생각하고 풀지 않다가 시간초과가 뜨니깐 막막하네요 ㅜㅜ

혹시 시간복잡도를 따진다면 input을 보고 이 문제는 어느 정도의 시간복잡도가 허용되어야 하니깐

어떠한 알고리즘을 써야겠다 라는 식의 사고가 진행되는건가요??

저는 시간복잡도 생각안하고 구현만 생각해서 시간복잡도 생각하며 푸는 사고의 흐름이 궁금하네요 ㅜㅜ

그리고 해당 코드에서 어떤 부분이 시간 초과가 나는지 알 수 있을까요???

대략적인 흐름은 이렇습니다.

상근이의 첫 시작 위치를 큐에 삽입합니다.
boardUpdate()를 이용하여 1초 지난 불의 번짐을 적용합니다.
상근이의 이동을 적용합니다.
2~3번을 반복합니다.(여기서 주의할 점이, 1초 지나고 나면 상근이의 움직임에 따라 큐에 1~4개가 삽입됩니다. 하지만 모두 2번이 그대로 적용되면 큐에 삽입되어 있는 상근이는 1초가 지난 상근이지만 불의 상태는 2초, 3초, 4초가 지난 상태로 계속 번지게 됩니다. 이 부분을 코드에서 93번째 줄 "flag 변수"를 통해 조절하였습니다.)
마지막 노드의 상태를 보고 time 또는 "IMPOSSIBLE"을 출력합니다.

혹시 어디에서 시간초과가 발생하는지, 어떠한 사고방식으로 시간복잡도를 생각하며 접근하는지를 알 수 있을까요???? ㅜㅜ

/*
	Title : 불
	Description : 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하라(초)
*/
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

struct Node {
	int x;
	int y;
	int time;
};
int testCase_cnt;	// input
int boardSize_x; int boardSize_y;	// input
string board[1001];
int visit[1001][1001] = { 0, };
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
struct Node dogLocation;
queue<Node> bfsQ;
vector<int> V_answer;

void boardUpdate();
void dogMove();

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> testCase_cnt;
	for (int k = 0; k < testCase_cnt; k++)
	{
		// Initialization
		cin >> boardSize_x >> boardSize_y;
		for (int i = 0; i < boardSize_y; i++)
		{
			cin >> board[i];
			for (int j = 0; j < boardSize_x; j++)
				visit[i][j] = 0;
		}
		while (!bfsQ.empty())
			bfsQ.pop();

		// 상근이 위치 초기화
		for (int i = 0; i < boardSize_y; i++)
		{
			for (int j = 0; j < boardSize_x; j++)
			{
				if (board[i][j] == '@')
				{
					dogLocation.x = j;
					dogLocation.y = i;
					dogLocation.time = 0;
					goto skip;
				}
			}
		}
skip:
		bfsQ.push(dogLocation);

		// 상근이 이동
		dogMove();
	}

	// 출력
	for (int i = 0; i < V_answer.size(); i++)
	{
		if (V_answer[i] == -1)
			cout << "IMPOSSIBLE\n";
		else
			cout << V_answer[i] << "\n";
	}
}

// 상근이 이동
void dogMove()
{
	int flag = 0;

	// BFS start
	struct Node currentNode;
	struct Node addNode;
	while (!bfsQ.empty())
	{
		currentNode = bfsQ.front(); bfsQ.pop();

		// 불 번짐
		if (flag == currentNode.time)
		{
			boardUpdate();
			flag++;
		}

		// 도착 여부 확인
		if (currentNode.x == 0 || currentNode.y == 0 || currentNode.x == boardSize_x - 1 || currentNode.y == boardSize_y - 1)
			break;

		// 갈 수 있는 곳 큐삽입
		for (int dr = 0; dr < 4; dr++)
		{
			int nx = currentNode.x + dx[dr];
			int ny = currentNode.y + dy[dr];

			// 못가는 곳 제외
			if (nx < 0 || ny < 0 || ny >= boardSize_y || nx >= boardSize_x) continue;
			if (visit[ny][nx] == 1) continue;
			if (board[ny][nx] == '#' || board[ny][nx] == '*') continue;

			addNode.x = nx; addNode.y = ny; addNode.time = currentNode.time + 1;
			bfsQ.push(addNode);
			visit[ny][nx] = 1;
		}
	}	// BFS end

	// 마지막 지점이 탈출구인지 Impossible인지 구분
	if (currentNode.x == 0 || currentNode.y == 0 || currentNode.x == boardSize_x - 1 || currentNode.y == boardSize_y - 1)
		V_answer.push_back(currentNode.time + 1);
	else
		V_answer.push_back(-1);
}

// 불 번짐
void boardUpdate()
{
	bool fire[1001][1001] = { 0, };

	// 번진 불 영역 확인
	for (int i = 0; i < boardSize_y; i++)
	{
		for (int j = 0; j < boardSize_x; j++)
		{
			if (board[i][j] != '*') continue;
			fire[i][j] = 1;

			for (int dr = 0; dr < 4; dr++)
			{
				int nx = j + dx[dr];
				int ny = i + dy[dr];

				if (nx < 0 || ny < 0 || nx >= boardSize_x || ny >= boardSize_y) continue;
				if (board[ny][nx] == '.' || board[ny][nx] == '@')
					fire[ny][nx] = 1;
			}
		}
	}

	// 번진 불 상태 업데이트
	for (int i = 0; i < boardSize_y; i++)
		for (int j = 0; j < boardSize_x; j++)
			if (fire[i][j] == 1) board[i][j] = '*';
}

newdeal 5년 전 4

안녕하세요.

우선 이 코드의 시간초과가 난 원인은 boardUpdate() 함수 때문인 것 같습니다.

N과M은 각각 최대 1000인데, 최악의 경우 매초마다 N*M만큼의 시간을 계속 소모하게됩니다.

하지만, 불의 시작점의 좌표를 bfs돌리면 각좌표마다 어느시간부터 불이붙어있는지 알수있습니다.

예를들어,

*..

...

의 맵이있으면,

012

123

즉, (1,2)의점은 1초후부터는 불이붙어있고, (2,3)의점은 3초후부터는 불이붙어있다 라는 정보를 매초마다 맵을 업데이트하지않아도 한번의 bfs로 알수 있게됩니다.

이 방식을 코드에 적용시키시면 문제를 풀수있을거같습니다.

그리고 시간복잡도 관련해서 말씀드리자면, 저는 아직 너무나도 부족하지만 제경험상으로는

최대한 for문을 어떻게하면 줄일수있을까? 부터시작했던것 같습니다. 좀더 나아가면 내가 찾았던 정보를 앞으로 어떻게 활용할지?

그리고 자료구조 쪽으로 넘어가면 원소삭제나 원소찾기가 빈번해지면 vector를 버린다던지..

그리고 아직 미숙하지만 조금의 빅오계산법도 천천히 익숙해지고 있는데, 역시 문제많이 푸는게 최고인것같습니다.

답변이 만족스러웠을지 모르겠지만, 작성자님의 공부에 최대한 도움이 되었으면 좋겠네요..🙏

참, 그리고 이문제 AC받으시면 4179번문제와 3055번문제가 비슷한 메커니즘을 가지고 있습니다. 이문제도 푸시면 좋으실것 같네요.

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

문제

문제

출처

ICPC

"5247-불" 시간초과 문제

wony6731 5년 전 0

newdeal 5년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말