글 읽기 - 시간 초과가 어디서 나는걸까요!?

kij0621 4년 전 0

-1이 있는지 검사하는 부분에서 나는 걸까요...!?

/*
 * 7576.c++
 *
 *  Created on: 2019. 7. 23.
 *      Author: Seonggyeong
 */

#include<stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;

int M,N; // M : 세로, y , N : 가로, x
vector<int> tomatoX;
vector<int> tomatoY;
vector<vector<int>> tomatos(1001, vector<int>(1001,0));
vector<vector<int>> visit(1001, vector<int>(1001,0));
struct xy {int x; int y;};
queue<xy> q;

void bfs(){

	int xs[] = {-1, 0, 1, 0};
	int ys[] = {0, -1, 0, 1};

	for(int t=0; t<tomatoX.size(); t++){ //  1인 원소를 모두 시작점으로
		int xx = tomatoX[t];
		int yy = tomatoY[t];
		//printf("%d", xx);
		//printf("%d", yy);
		q.push({tomatoX[t], tomatoY[t]});
		visit[tomatoX[t]][tomatoY[t]] = 1; // 방문 처리

	}

		while(!q.empty()){
			int x = q.front().x;
			int y = q.front().y;
			q.pop();


			for(int i=0; i<4; i++){
				int a = x + xs[i];
				int b = y + ys[i];

				if(a < 0 || a>=N || b < 0 || b>=M ){
					continue;
				}

				if(tomatos[a][b] == 0 && !visit[a][b]){
					q.push({a,b});
					tomatos[a][b] =1;
					visit[a][b] = visit[x][y]+1;
					//printf("횟수는 : %d", visit[a][b]);
				}
			}
	}

}


int main(){
	bool can = true;
	scanf("%d %d", &M, &N);
	
	for(int i=0; i<N; i++){ // 0 ~ 3 // x
		for(int j=0; j<M; j++){ // 0 ~ 5 // y
			int num;
			scanf("%d", &num);
			//cin >> num;
			tomatos[i][j] = num;
			if(num == 1){
				tomatoX.push_back(i);
				tomatoY.push_back(j);
			}
		}
	}



	bfs();
    

	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			sort(visit[i].begin(), visit[i].end(), greater<int>());
		}
	}


	for(int i=0; i<N; i++){  //-1이 있는지 검사
		for(int j=0; j<M; j++){
			if(tomatos[i][j] == -1){
				can=false;
				break;
			}
		}
	}


	if(can){
		printf("%d", visit[0][0]-1);
	}else{
		printf("%d", -1);
	}
}

djm03178 4년 전 1

90~94번째 줄은 N*M번 루프를 돌면서 O(M)개의 원소를 O(MlogM) 시간에 정렬하고 있기 때문에 O(NM^2logM)입니다. 애초에 visit[i]에 대해 정렬은 한 번만 하면 되는데 안쪽 루프에서 불필요하게 M번 루프를 돌고 있네요.

kij0621 4년 전 0

MAX 변수를 따로 두고

if(MAX < visit[a][b]){

MAX = visit[a][b];

}

이렇게 코드 추가했더니 맞았다고 나오네요...감사합니다!!

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

문제

문제

출처

ICPC

시간 초과가 어디서 나는걸까요!?

kij0621 4년 전 0

djm03178 4년 전 1

kij0621 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말