글 읽기 - 시간초과

gokimkq123 3년 전 0

코드업에서 146ms로 정풀이 떴는데 백준에서는 시간초과가 뜨네요 뭐가 도대체 문제인가요?? 구현은 bfs로 큐에 넣고 방문 체크 했습니다.

#include <bits/stdc++.h>
using namespace std;
int a,b,c,d,cnt,cnt1;
unordered_map<int, unordered_map <int,int> > check;
queue<pair<int,int> > q;
pair<int,int> p;


int bfs(void){
	q.push(make_pair(0,0));    //큐에 0,0 넣기
	check[0][0]=1;                //방문 체크
	while(!q.empty()){        //큐가 비어질때까지
		int size=q.size();    //사이즈 저장
		
		for(int i=0;i<size;i++){        //사이즈 만큼 돌리기
			p=q.front();                //큐 꺼내기
			q.pop();                    //무한방문 제거
			
			int nx=p.first,ny=p.second;        //pair nx= 첫번째 E(x)값 ny= 두번째 E(y)값
	
			if(nx==c&&ny==d)	return cnt1-2;
			
			int sz=0;
			
			if(nx<=a&&ny<=b&&check[sz+a][ny]!=1){    //E(x) fill:X
				q.push(make_pair(sz+a,ny));	
				check[sz+a][ny]=1;	
			}
			
			if(nx<=a&&ny<=b<b&&check[nx][sz+b]!=1){   // E(y) fii:y
				q.push(make_pair(nx,sz+b));
				check[nx][sz+b]=1;
			}
			
			if(nx<=a&&ny<=b<b&&check[sz][ny]!=1){    //E(x) empty:x
				q.push(make_pair(sz,ny));
				check[sz][ny]=1;	
			}
			
			if(nx<=a&&ny<=b&&check[nx][sz]!=1){    //E(y) empty:y
				q.push(make_pair(nx,sz));
				check[nx][sz]=1;	
			}	
			
			int lightsum=a-nx,leftsum=b-ny;
			
			if(nx<=a&&ny<=b&&ny+nx<=a&&check[nx+ny][0]!=1){   // M(x,y) : Move water from x to y
				q.push(make_pair(nx+ny,0));
				check[nx+ny][0]=1;
			}
			else if(nx<=a&&ny<=b<b&&ny+nx>a&&check[nx+lightsum][ny-lightsum]!=1){   // M(x,y) : Move water from x to y
				q.push(make_pair(nx+lightsum,ny-lightsum));
				check[nx+lightsum][ny-lightsum]=1;
			}
			
			if(nx<=a&&ny<=b&&check[0][ny+nx]!=1&&ny+nx<=b){    //M(y,x) : Move water from y to x
				q.push(make_pair(0,nx+ny));
				check[0][ny+nx]=1;
			}
			else if(nx<=a&&ny<=b&&ny+nx>b&&check[nx-leftsum][ny+leftsum]!=1){    //M(y,x) : Move water from y to x
				q.push(make_pair(nx-leftsum,ny+leftsum));
				check[nx-leftsum][ny+leftsum]=1;
			}
		}
		cnt++;
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> a >> b >> c >> d;
	
	int z=bfs();
	if(z!=-2)	cout << "-1"; //만약 반환 되는값이 없으면 -1
	else cout << cnt;    //아니면 출력
}

jjang36524 3년 전 0

a*b가지의 상태가 나올 수 있으므로, 시간초과입니다.

코드업에서 맞는 것은 코드업의 잘못입니다.

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

문제

문제

출처

ICPC

시간초과

gokimkq123 3년 전 0

jjang36524 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말