글 읽기 - stl을 썻을때랑 안썻을때의 차이인가요..

jeff90hbk 5년 전 0

stl을 사용해서 큐를 만들고 제출을하면 맞았습니다! 라고 뜨는데

저는 큐를 제가 간단하게 만들어서 쓰거든요..

이게 큐의 문제인가요..?

#include<iostream>

using namespace std;


typedef struct Position {
	int x;
	int y;
}Pos;

Pos swan_pos[2];
/*------------Queue-----------------*/
//const int MAX_Q = 1 << 20;
const int MAX_Q = 2250001;

Pos cur_swan_Q[MAX_Q]; int csf, csr;
void cur_swan_push(int y, int x) {
	if (csr == MAX_Q) csr = 0;
	cur_swan_Q[csr].y = y;
	cur_swan_Q[csr].x = x;
	csr++;
}
Pos cur_swan_pop() {
	Pos d;
	if (csf == MAX_Q) csf = 0;
	d.y = cur_swan_Q[csf].y;
	d.x = cur_swan_Q[csf].x;
	csf++;
	return d;
}

Pos next_swan_Q[MAX_Q]; int nsf, nsr;
void next_swan_push(int y, int x) {
	if (nsr == MAX_Q) nsr = 0;
	next_swan_Q[nsr].y = y;
	next_swan_Q[nsr].x = x;
	nsr++;
}
Pos next_swan_pop() {
	Pos d;
	if (nsf == MAX_Q) nsf = 0;
	d.y = next_swan_Q[nsf].y;
	d.x = next_swan_Q[nsf].x;
	nsf++;
	return d;
}

Pos cur_water_Q[MAX_Q]; int cwf, cwr;
void cur_water_push(int y, int x) {
	if (cwr == MAX_Q) cwr = 0;
	cur_water_Q[cwr].y = y;
	cur_water_Q[cwr].x = x;
	cwr++;
}
Pos cur_water_pop() {
	Pos d;
	if (cwf == MAX_Q) cwf = 0;
	d.y = cur_water_Q[cwf].y;
	d.x = cur_water_Q[cwf].x;
	cwf++;
	return d;
}

Pos next_water_Q[MAX_Q]; int nwf, nwr;
void next_water_push(int y, int x) {
	if (nwr == MAX_Q) nwr = 0;
	next_water_Q[nwr].y = y;
	next_water_Q[nwr].x = x;
	nwr++;
}
Pos next_water_pop() {
	Pos d;
	if (nwf == MAX_Q) nwf = 0;
	d.y = next_water_Q[nwf].y;
	d.x = next_water_Q[nwf].x;
	nwf++;
	return d;
}
/*------------Queue-----------------*/

const int MAX_R_C = 1500; // width R, height C 
int R, C;
char map[MAX_R_C][MAX_R_C];
bool Find;
bool visit[MAX_R_C][MAX_R_C];
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };

/*------------BFS-----------*/
/*
 *백조에 대한 BFS
 *if(인접한방향이 물) 백조의 현재큐에 push후 진행
 *if(인접한방향이 빙판) 백조의 다음큐에 push후 진행
 *if(인접한방향이 다른백조) 서로 만남 check 종료
 *
 *물에 대한 BFS
 *if(인접한방향이 물) 물의 현재큐에 push후 진행
 *if(인접한방향이 빙판) 물의 다음큐에 push후 해당 정점 물로 바꿈
 */
void swan_BFS() {
	int ny, nx, nday;

	while (csf != csr && !Find) {
		Pos cur = cur_swan_pop();

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				ny = cur.y + dy[i];
				nx = cur.x + dx[i];

				if (ny >= 0 && nx >= 0 && ny < R&&nx < C) {
					if (!visit[ny][nx]) {
						if (map[ny][nx] == '.') {
							cur_swan_push(ny, nx);
							visit[ny][nx] = true;
						}
						else if (map[ny][nx] == 'X') {
							next_swan_push(ny, nx);
							visit[ny][nx] = true;
						}
						else if (map[ny][nx] == 'L') {
							visit[ny][nx] = true;
							Find = true;
							break;
						}
					}
				}
			}
		}
	}
}

void water_BFS() {
	while (cwf != cwr) {
		Pos cur = cur_water_pop();
		int ny, nx;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				ny = cur.y + dy[i];
				nx = cur.x + dx[i];
				if (ny >= 0 && nx >= 0 && ny < R&&nx < C) {
					if (map[ny][nx] == 'X') {
						map[ny][nx] = '.';
						next_water_push(ny, nx);
					}
				}
			}
		}

	}
}
/*------------BFS-----------*/

void search() {
	Find = false;
	int c = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j] != 'X') cur_water_push(i, j);
			if (map[i][j] == 'L') {
				swan_pos[c].x = i;
				swan_pos[c].y = j;
				c++;
			}
		}
	}
}
//while문을 계속 돌리면서 백조에 대한 BFS(), 물에대한 BFS()를 한번씩 실행시킨다.
//백조가 서로 만나면 종료
void solution() {
	int day = 0;
	//찾은 백조 좌표를 현재 백조 큐에 푸시
	cur_swan_push(swan_pos[0].y, swan_pos[0].x);
	visit[swan_pos[0].y][swan_pos[0].x] = true;

	while (!Find) {
		//현재 백조가 다른백조를 찾음
		swan_BFS();
		//만약 못찾았다면 
		if (!Find) {
			//빙판을 찾아서 next_water_Q에 푸시
			//빙판을 물로 바꿈
			water_BFS();

			//다음 큐에 있던 정보들을 현재 큐로 몽땅 집어넣음
			while (nwf != nwr) {
				Pos p = next_water_pop();
				cur_water_push(p.y, p.x);
			}
			while (nsf != nsr) {
				Pos p = next_swan_pop();
				cur_swan_push(p.y, p.x);
			}
			day++;

		}
	}
	cout << day;
}
int main()
{
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		cin >> map[i];
	}
	search();
	solution();
	return 0;

}

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

문제

문제

출처

ICPC

stl을 썻을때랑 안썻을때의 차이인가요..

jeff90hbk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말