글 읽기 - 이 방법으론 시간 초과가 날 수 밖에 없나요?

zygmunt137 4년 전 0

제가 짠 코드에서 취하고 있는 방법으로는

시간 초과가 날 수 밖에 없나요

아니면 다른 원인이 있나요

코드를 간략히 설명하자면

isReachable 함수는 (0,0)에서 (n,m)에 도달할 수 있는지 여부를 반환하는 함수이고 (vector<int> wall도 이 함수 내에서 갱신해줍니다)

전체적인 흐름은 room 배열에서 부술 수 있는 벽들(vector<int> wall)을 하나씩만 깨면서 각각을 큐에 넣어놓고 pop하는 bfs 방식을 취하고 있습니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class StateOfMap {
private:
	char * room;
	int n;
	int m;
	int cnt;
public:
	StateOfMap(char * new_room, int p, int q, int new_cnt) {
		int i;
		n = p; m = q;
		room = new char[n*m];
		for (i = 0; i < n*m; i++) {
			room[i] = new_room[i];
		}
		cnt = new_cnt;
	}
	bool operator==(StateOfMap temp) {
		for (int i = 0; i < n*m; i++) {
			if (room[i] != temp.room[i]) return false;
		}
		return true;
	}
	void getRoom(char * ret_room) {
		for (int i = 0; i < n*m; i++) {
			ret_room[i] = room[i];
		}
	}
	int getCount() {
		return cnt;
	}
};

bool isReachable(char room[], vector<int> linkedVertex[], vector<int> * wall, int n, int m) {
	int cur = 0, i, j = 1, k;
	vector<int> reachable;
	reachable.insert(reachable.end(), 0);
	bool * visited = new bool[n*m];
	for (i = 0; i < n*m; i++) {
		visited[i] = false;
	}

	while (1) {
		for (i = 0; i < (signed int)linkedVertex[cur].size(); i++) {
			k = linkedVertex[cur][i];
			if (room[k] == '0' && !visited[k]) {
				reachable.insert(reachable.end(), k);
				visited[k] = true;
			}
			if (room[k] == '1') {
				(*wall).insert((*wall).end(), k);
			}
		}
		if (j >= reachable.size()) break;
		cur = reachable[j++];
	}

	for (i = 0; i < (signed int)reachable.size(); i++) {
		if (reachable[i] == n*m - 1) return true;
	}
	return false;
}

int numOfWalls(char room[], vector<int> linkedVertex[], int n, int m) {
	int cnt = 0, i, j;
	queue<StateOfMap> stateQ;
	vector<StateOfMap> visited;

	while (1) {
		vector<int> wall;
		if (isReachable(room, linkedVertex, &wall, n, m)) break;
		cnt++;
		for (i = 0; i < wall.size(); i++) {
			room[wall[i]] = '0';
			StateOfMap temp(room, n, m, cnt);
			for (j = 0; j < (signed int)visited.size(); j++) {
				if (visited[j] == temp) break;
			}
			if (j == (signed int)visited.size()) {
				stateQ.push(temp);
				visited.insert(visited.end(), temp);
			}
			room[wall[i]] = '1';
		}
		stateQ.front().getRoom(room);
		cnt = stateQ.front().getCount();
		stateQ.pop();
	}

	return cnt;
}

int main() {
	int n, m, i;
	cin >> m >> n;
	char * room = new char[n*m];
	vector<int> * linkedVertex = new vector<int>[n*m];

	for (i = 0; i < n*m; i++) {
		cin >> room[i];
	}
	for (i = 0; i < n*m; i++) {
		if(i%m > 0) linkedVertex[i].insert(linkedVertex[i].end(), i - 1);
		if(i > m - 1) linkedVertex[i].insert(linkedVertex[i].end(), i - m);
		if (i%m < m - 1) linkedVertex[i].insert(linkedVertex[i].end(), i + 1);
		if(i < n*m - m) linkedVertex[i].insert(linkedVertex[i].end(), i + m);
	}

	cout << numOfWalls(room, linkedVertex, n, m) << '\n';

	return 0;
}

dohoon 3년 전 0

bfs면 시간초과가 나긴 할 텐데, 코드가 너무 길어서 다른 방식으로 최적화하셨는지는 잘 모르겠네요...

미로가 너무 꼬여있어서 빙빙 돌아가야 하는 경우, 거의 (100^2)/2 정도의 방을 탐색해야 되는데 매번 4개로 다음 노드가 갈리니까

불가능해 보이기는 합니다.

참고로 이 문제는 다익스트라 알고리즘을 이용하는 것이 좋습니다.

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

문제

문제

출처

ICPC

이 방법으론 시간 초과가 날 수 밖에 없나요?

zygmunt137 4년 전 0

dohoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말