글 읽기 - 시간초과가 어디서 발생하는지 알 수 있을까요....? ㅜㅜ

wony6731 4년 전 0

이 코드가 정확히 맞는지 모르겠지만,,, 시간초과가 발생하고 있습니다.

혹시 어디서 시간초과가 나는지 알 수 있을까요...?

그리고 만약에 제 코드가 틀리다면 반례도 알 수 있을까요 ㅜㅜ

#include <iostream>
#include <queue>

using namespace std;

struct Node {
	int x, y;
};
int light_cnt;
int N, M;
int board[101][101];	// 1은 불을 킴, visitNum은 방문
int arr[20001][4];
bool visited_switch[20001];
queue<Node> Q;
bool gotoStart;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
/*
	Name : visitNum
	Description
	: BFS를 불을 킬 때마다 (1,1)에서 시작하면 board에 지나간 곳 표시한 것을 모두 계속 초기화를 시켜주어야 한다.
	그러므로 visitNum을 통해 (1,1)에서 다시시작할때마다 방문 표시 값을 1씩 증가시켜 초기화를 하지 않도록 한다.
	처음에는 2가 지나간 곳이나 다시 (1,1)에서 BFS를 시작하면 3으로 방문표시를 한다.
*/
int visitNum;

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

	cin >> N >> M;
	for (int i = 1; i <= M; i++){
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2] >> arr[i][3];
	}

	// BFS 시작
	light_cnt = 1;
	visitNum = 2;
BACK:
	gotoStart = false;
	struct Node start;
	start.x = 1;
	start.y = 1;
	board[1][1] = visitNum;
	Q.push(start);

	while (!Q.empty()){
		struct Node cur = Q.front();
		Q.pop();

		// 현재 방에서 킬 수 있는 모든 불을 킴
		for (int i = 1; i <= M; i++){
			if (visited_switch[i] == true) continue;
			int y1 = arr[i][0];
			int x1 = arr[i][1];
			int y2 = arr[i][2];
			int x2 = arr[i][3];

			// 불을 킴
			if (x1 == cur.x && y1 == cur.y){
				if (board[y2][x2] == 0){
					board[y2][x2] = 1;
					light_cnt++;
					gotoStart = true;	// (1,1)에서 다시 시작
				}
				visited_switch[i] = true;
			}
		}
		if (gotoStart == true){
			visitNum++;
			while (!Q.empty())
				Q.pop();
			goto BACK;
		}

		// 현재 방에서 킨 불이 없으면 BFS 계속
		for (int dr = 0; dr < 4; dr++){
			int nx = cur.x + dx[dr];
			int ny = cur.y + dy[dr];

			if (nx<1 || ny<1 || nx>N || ny>N) continue;
			if (board[ny][nx] == 0) continue;	// 꺼진 방이면
			if (board[ny][nx] == visitNum) continue; // 방문한 곳이면

			struct Node next;
			next.x = nx;
			next.y = ny;
			Q.push(next);
			board[ny][nx] = visitNum;
		}
	}
	cout << light_cnt << "\n";
}

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

문제

문제

출처

ICPC

시간초과가 어디서 발생하는지 알 수 있을까요....? ㅜㅜ

wony6731 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말