글 읽기 - 시간초과가 발생하는데 지적해주세요.

rnfkcu 4년 전 0

65퍼정도까지 채점되다가 시간초과 발생합니다.

원인을 알려주시면 감사하겠습니다.

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int y;
	int dist;
};

int board[102][102];
int dist[102][102];
bool vis[102][102];

int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };

int main()
{
	int L;
	int gcnt = 0;
	queue<Que> Q,GQ;
	int min = 100;
	cin >> L;
	for (int i = 0; i < L; i++) {
		for (int j = 0; j < L; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) {
				GQ.push({ i,j,0 });
			}
		}
	}
	for (int i = 0; i < L; i++) {
		for (int j = 0; j < L; j++) {
			if (board[i][j] == 1 and vis[i][j] == false) {
				gcnt++;
				Q.push({ i,j,0 });// 거리
				board[i][j] = gcnt;
				vis[i][j] = true;
				while (!Q.empty()) {
					auto cur = Q.front();
					Q.pop();
					for (int k = 0; k < 4; k++) {
						int nx = cur.x + dx[k];
						int ny = cur.y + dy[k];
						if (nx<0 or nx>L - 1 or ny<0 or ny>L - 1)continue;
						if (board[nx][ny] == 1 and vis[nx][ny] == false) {
							Q.push({ nx,ny,0 });
							vis[nx][ny] = true;
							board[nx][ny] = gcnt;
						}
					}
				}

			}
		}
	}

	for (int i = 0; i < L; i++) {
		for (int j = 0; j < L; j++) {
			vis[i][j] = false;
		}
	}
	
	while (1) {
		int size = GQ.size();

		while (size--) {
			auto cur = GQ.front();
			GQ.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx<0 or nx>L - 1 or ny<0 or ny>L - 1)continue;
				if (board[nx][ny] == 0 and vis[nx][ny] == false) {
					GQ.push({ nx,ny,cur.dist + 1 });
					vis[nx][ny] = true;
					board[nx][ny] = board[cur.x][cur.y];
					dist[nx][ny] = cur.dist + 1;
				}
				else if (board[nx][ny] != 0 and vis[nx][ny] == true and board[nx][ny] != board[cur.x][cur.y]) {
					if (min > cur.dist + dist[nx][ny]) {
						min = cur.dist + dist[nx][ny];
					}
				}
			}
		}
		if (min != 100) {
			cout << min << endl;
			break;
		}
	}
}

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

문제

문제

출처

ICPC

시간초과가 발생하는데 지적해주세요.

rnfkcu 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말