글 읽기 - 시간초과 질문드립니다ㅠㅠ 도와주세요 (bfs)

darius2003 6년 전 0

2%에서 시간 초과가 나는데 어떻게 해야할지 도저히 모르겠습니다ㅠ. 도와주세요 고수님들ㅠ

#include<iostream>
#include<string>
#include<algorithm>
#include<memory.h>
#include<vector>
#include<map>
#include<queue>

using namespace std;

typedef pair<int, int> pos;
int two_arr[1000][1000];
int dx[4] = { 0,-1,0 ,1 };
int dy[4] = { -1,0,1, 0 };
int m,n,check;
map<pos, int> date;
queue<pos> qu;
int bfs() {
	
	while (!qu.empty()) {
		pos temp = qu.front();
		qu.pop();

		for (int i = 0; i < 4; i++) {
			int left = temp.first + dx[i];
			int right = temp.second + dy[i];
				
			if (left >= n || left < 0 || right < 0 || right >= m) continue;
			if (two_arr[left][right] == 0 && date[{left, right}] == -1) {
				date[{left, right}] = date[{temp.first, temp.second}] + 1;
				qu.push({ left, right });
			}
		}
	}

	check = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (two_arr[i][j] == 0 && date[{i, j}] == -1) return 0;
			else return 1;
		}
	}
}
int main() {

	cin >> m >> n; check = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &two_arr[i][j]); date[{i, j}] = -1;
			if (two_arr[i][j] == 1) {
				check++;
				qu.push({ i,j });
				date[{i, j}] = 0;
			}
		}
	}
	if (check == m*n) cout << 0 << endl;
	else {
		int temp = bfs();
		if (!temp) cout << -1 << endl;
		else
			cout << date.begin()->second << endl;
	}
}

jh05013 6년 전 0

date를 map으로 할 필요가 없습니다. 그냥 2차원 배열을 만들면 됩니다.

답도 틀립니다. 질문 검색을 누르면 반례가 달린 글이 많이 나옵니다.

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

문제

문제

출처

ICPC

시간초과 질문드립니다ㅠㅠ 도와주세요 (bfs)

darius2003 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말