글 읽기 - [c++] 이게 왜틀린거죠???

dkwk3028 4년 전 0

단순한 bfs문제라고 생각했는데 안풀리네요..

어차피 queue 에 넣은순서대로 검사를 하니깐

날짜 순서대로 검사를 할테고..

날짜 세는게 잘못됬나 생각해봤는데, sum == total이 되는순간 마지막 push된 PointInfo의 level은 제가 구하는 날짜가 되는게 맞는거같아요;;

탐색과정에서는 잘못된게 없는거 같은데; 고수님들 도와주세요

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
#include <utility>

typedef std::tuple<int, int, int> PointInfo;
int main(void){
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL);
	
	int n = 0 , m = 0;
	std::cin >> m >> n;
	
	int tomato[n][m] = {{0,}};
	
	//y,x,level
	int total = n*m;
	//std::cout << total << "\n";
	int sum = 0;
	std::queue<PointInfo> q;
	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			std::cin >> tomato[i][j];
			if (tomato[i][j] == 1){
				q.push(PointInfo(i,j,0));
				sum += 1;
			}else if (tomato[i][j] == -1){
				total -= 1;
				//std::cout << i << "," << j << "ij\n";
			}
		}
	}
	
	//std::cout << sum << "\n";
	int time = 0;
	bool b_end = false;
	
	int dx[4] = {0,0,-1,1};
	int dy[4] = {1,-1,0,0};
	while(!q.empty()){
		if (sum == total){
			time = std::get<2>(q.back());
			b_end = true;
			break;
		}
		auto& [y,x,l] = q.front();
		q.pop();
		


		
		for(int i=0;i<4;++i){
			int tx = x + dx[i];
			int ty = y + dy[i];
			
			if (tx >= 0 && ty >= 0 && tx < m && ty < n){
				if (tomato[ty][tx] == 0){
					q.push(PointInfo(ty,tx,l+1));
					tomato[ty][tx] = 1;
					sum += 1;
					//std::cout << tx <<  " , " << ty << " , " << l+1 << "\n";
				}
			}
		}
		
	}
	
	time = b_end ? time : -1;
	std::cout << time << "\n";
	
	return 0;
}

dkwk3028 4년 전 0

아예 처음부터 토마토가 없는 케이스에 대해서도 새로 작성했는데 틀렸네요..

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
#include <utility>

typedef std::tuple<int, int, int> PointInfo;
int main(void){
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL);
	
	int n = 0 , m = 0;
	std::cin >> m >> n;
	//n = 1000;
	//m = 1000;
	int tomato[n][m] = {{0,}};
	
	//y,x,level
	
	int total = n*m;
	//std::cout << total << "\n";
	int sum = 0;
	std::queue<PointInfo> q;
	//std::cout << q::max_size() <<"\n";

	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			std::cin >> tomato[i][j];
			//tomato[i][j] = i == 999 && j == 999 ? 1 : 0;
			//std::cout << tomato[i][j] << " ";
			if (tomato[i][j] == 1){
				q.push(PointInfo(i,j,0));
				sum += 1;
			}else if (tomato[i][j] == -1){
				total -= 1;
				//std::cout << i << "," << j << "ij\n";
			}
		}
		//std::cout << "\n";
	}
	
	//std::cout << sum << "\n";
	int time = 0;
	bool b_end = false;
	
	int dx[4] = {0,0,-1,1};
	int dy[4] = {1,-1,0,0};
	while(!q.empty()){
		if (sum == total){
			time = std::get<2>(q.back());
			b_end = true;
			break;
		}
		auto& [y,x,l] = q.front();
		q.pop();
		


		
		for(int i=0;i<4;++i){
			int tx = x + dx[i];
			int ty = y + dy[i];
			
			if (tx >= 0 && ty >= 0 && tx < m && ty < n){
				if (tomato[ty][tx] == 0){
					q.push(PointInfo(ty,tx,l+1));
					tomato[ty][tx] = 1;
					sum += 1;
					//std::cout << tx <<  " , " << ty << " , " << l+1 << "\n";
				}
			}
		}
		
	}
	
	if (total == 0){
		b_end = true;
	}
	time = b_end ? time : -1;
	std::cout << time << "\n";
	
	return 0;
}

dkwk3028 4년 전 0

n = m = 1000 이면서 i == 999 && j == 999 인 부분만 1이고 나머지는 0 인 케이스에대해서 해봤는데

다른 n=m 케이스가 n *2 -2 의 값을 내는것과 달리 1918정도의 값밖에 안내더라고요.

n = 799일때부터 이런현상이 일어나서

혹시해서 auto& [y,x,l] = q.front(); 를 auto [y,x,l] = q.front()로 바꿨는데 제대로 작동하네요..

확실치는 않지만 제가 레퍼런스로 받아서 메모리 어딘가에서 살아남은듯 하네요;

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

문제

문제

출처

ICPC

[c++] 이게 왜틀린거죠???

dkwk3028 4년 전 0

dkwk3028 4년 전 0

dkwk3028 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말