글 읽기 - c++ 시간초과가 뜨네요 ㅠㅠ

shwjdgh3842 2년 전 1

일반적인 bfs코드인데 이게 왜 시간초과가 걸리는지 모르겠어요.

예제는 잘 통과됩니다.

50^2칸에 대해서 육지인 점마다 bfs를 시행하는데 최대 시행횟수는 2500번일테고 각 시행마다 시간복잡도도 2500언저리여서 시간초과걸릴거같지 않은데 어느부분에서 최적화를 해야할까요..?

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <queue>
#include <vector>
#include <string>
using namespace std;
int n, m;
char board[50][50];

//12시부터 시계방향
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int max_val = 0;

//x,y에서 최장경로를 구해서 max_val에 저장하는 함수
void bfs(int x, int y) {
	queue<pair<int, int>> q;
	bool visited[50][50];
	int cnt[50][50];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = false;
			cnt[i][j] = 0;
		}
	}
	q.push({ x,y });
	visited[x][y] = true;
	//cnt[x][y] = 1;
	while (!q.empty()) {
		int herex = q.front().first;
		int herey = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nowx = herex + dx[i];
			int nowy = herey + dy[i];
			if (nowx < 0 || nowy < 0 || nowx >= n || nowy >= m) {
				//판 밖으로 나간경우
				continue;
			}
			else if (board[nowx][nowy] == 'L' && visited[nowx][nowy] == false) {
				//땅이고 방문한 적이 없는경우 -> 탐색
				q.push({ nowx,nowy });
				visited[nowx][nowy] = true;
				cnt[nowx][nowy] = cnt[herex][herey] + 1;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (max_val < cnt[i][j]) {
					max_val = cnt[i][j];
				}
			}
		}
		
	}

}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'L') {
				bfs(i, j);
			}
		}
	}
	cout << max_val;
}

dnjstjr0227 2년 전 1

아래 카운트 세는 코드가 queue에서 pop할때마다 할 이유가 없어보입니다~!

이 코드때문에 2500^3 급의 시간복잡도가 나올것같아요

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (max_val < cnt[i][j]) {
            max_val = cnt[i][j];
        }
    }
}

shwjdgh3842 2년 전 0

감사합니다!!!

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

문제

문제

출처

ICPC

c++ 시간초과가 뜨네요 ㅠㅠ

shwjdgh3842 2년 전 1

dnjstjr0227 2년 전 1

shwjdgh3842 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말