글 읽기 - 고수분들 환영합니다 ㅜ

dong149 5년 전 0

테스트케이스는 다맞는데 메모리초과가 뜨네요 ㅜㅜㅜ 고수분들 뭐가 문제인지 알려주세요 ㅜㅜ

#include <iostream>
#include <queue>

using namespace std;
typedef pair<int, int> p;
int r, c;
char map[51][51];
//물이 차있는 좌표
queue<p> waterq;
queue<p> nextq;
queue<p> q;
queue<p> nq;
//물이 찼거나 방문했던 적이 있는곳을 체크해준다.
bool check[51][51];
int dx[] ={ -1,1,0,0 };
int dy[] ={ 0,0,-1,1 };
int cnt=0;
//D부분을 막아줘야하고 물을 채우면 그부분에 체크를 true 로 바꾸어야한다.
void waterBFS() {
	//큐가 빌때까지
	int x, y;
	int tx, ty;
	while(!waterq.empty()) {
		x = waterq.front().first;
		y = waterq.front().second;
		waterq.pop();
		//물이 찼으므로 방문한걸로 친다.
		//check[x][y] = true;
		map[x][y] = '*';
		for(int i=0; i<4; i++) {
			tx = x+dx[i];
			ty = y+dy[i];
			if(tx<0||tx>=r||ty<0||ty>=c)
				continue;
			if(map[tx][ty]=='.'||map[tx][ty]=='S') {
				nextq.push(p(tx, ty));
				check[tx][ty] = true;
			}
		}

	}
	//waterq에 옮겨닮는다.
	while(!nextq.empty()) {
		int ax = nextq.front().first;
		int ay = nextq.front().second;
		nextq.pop();
		waterq.push(p(ax, ay));
	}
}

int BFS() {
	int x, y;
	int tx, ty;

	while(!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		swc=0;
		check[x][y] = true;
		for(int i=0; i<4; i++) {
			tx = x+dx[i];
			ty = y+dy[i];

			if(tx<0||tx>=r||ty<0||ty>=c)
				continue;
		
			if(map[tx][ty]=='D') {
				return cnt;
			}
			if(!check[tx][ty]) {
				nq.push(p(tx, ty));
			}

		}
	}
	//q에 옮겨닮는다.
	while(!nq.empty()) {
		int ax = nq.front().first;
		int ay = nq.front().second;
		nq.pop();
		q.push(p(ax, ay));
	}

	return 0;
}
int main() {
	cin>>r>>c;
	//입력을 받는다.
	for(int i=0; i<51; i++) {
		for(int j=0; j<51; j++) {
			map[i][j] = '*';
		}
	}

	for(int i=0; i<r; i++) {
		for(int j=0; j<c; j++) {
			cin>>map[i][j];
			//물이 차있는 곳의 좌표를 큐에 저장한다.
			if(map[i][j] == '*') {
				waterq.push(p(i, j));
				check[i][j] = true;
			}
			if(map[i][j]=='X') {
				check[i][j] = true;
			}
			if(map[i][j]=='S') {
				q.push(p(i, j));
			}

		}
	}
	
	int c=0;
	while(1) {
		cnt++;
		waterBFS();
		c = BFS();
		if(c!=0) {
			cout<<c;
			break;
		}
		if(q.empty()&&c==0) {
			cout<<"KAKTUS";
			break;
		}


	}



	return 0;
}

djm03178 5년 전 1

애초에 59번째 줄 때문에 컴파일이 안 됩니다. 질문을 올릴 때는 틀린 코드를 한 자도 다름 없이 그대로 올려 주세요.

그 줄을 지우고 테스트 하면, 다음과 같은 케이스에서 메모리만 늘어나고 시간 내에 답을 내지 못하는 것을 볼 수 있습니다. 원인을 잘 생각해보세요.

20 20
S...................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
...................D

dong149 5년 전 1

아앗! 제가 코드정리하다가 잘못 올렸네요ㅜ 정말 감사합니다 ! 잘생각해볼게요!!

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

문제

문제

출처

ICPC

고수분들 환영합니다 ㅜ

dong149 5년 전 0

djm03178 5년 전 1

dong149 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말