글 읽기 - 테스트 케이스가 1000/1000일때만 틀립니다

rlawnddnjs12 2년 전 0

http://acm.student.cs.uwaterlo...

(다른 분들 테스트 케이스 참고하실 때 B.x가 이 문제의 테스트 케이스입니다)

이곳에 있는 테스트 케이스 중 2개만 잘못나오는데 둘다 R,C값이 1000일때만 잘못나옵니다.

제 코드에 어떤 오류가 있는지 조언을 얻고자 질문드립니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define MAX_SIZE 1003
struct node {
	int x;
	int y;
};

int size = 0, fire = 0;
int head = 0, tail = 0;
struct node queue[MAX_SIZE];

void enque(int x_, int y_) {
	struct node t;
	t.x = x_;
	t.y = y_;
	queue[tail] = t;
	tail = (tail + 1) % MAX_SIZE;
	size++;
}

struct node deque() {
	struct node temp = queue[head];
	head = (head + 1) % MAX_SIZE;
	size--;
	return temp;
}

int Is_Empty() {
	if (head == tail) {
		return 0;
	}
	else {
		return 1;
	}
}

int head1 = 0, tail1 = 0;
struct node queue1[MAX_SIZE];

void enque1(int x_, int y_) {
	struct node t;
	t.x = x_;
	t.y = y_;
	queue1[tail1] = t;
	tail1 = (tail1 + 1) % MAX_SIZE;
	fire++;
}

struct node deque1() {
	struct node temp = queue1[head1];
	head1 = (head1 + 1) % MAX_SIZE;
	fire --;
	return temp;
}

int Is_Empty1() {
	if (head1 == tail1) {
		return 0;
	}
	else {
		return 1;
	}
}

int R, C;
char Graph[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int cnt=1;

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool flag;

int BFS() {
	int nextX, nextY;

	int res;
	while (1) {
		//불부터 번지기 시작
		if (fire == 0 && size == 0) {
			break;
		}
		int fire_e = fire;
		for (int i = 0; i < fire_e; i++) {
			struct node t = deque1();

			for (int i = 0; i < 4; i++) {
				nextX = t.x + dx[i];
				nextY = t.y + dy[i];

				if (0 <= nextX && nextX < R && 0 <= nextY && nextY < C) {
					if (visited[nextX][nextY] == 0 || visited[nextX][nextY] == 1) {
						enque1(nextX, nextY);
						visited[nextX][nextY] = 4;
					}
				}
			}
		}

		int e = size;
		for (int i = 0; i < e; i++) {
			struct node k = deque();

			if (k.x == 0 || k.x == R - 1 || k.y == 0 || k.y == C - 1) {
				flag = true;
				res = cnt;
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				nextX = k.x + dx[i];
				nextY = k.y + dy[i];

				if (0 <= nextX && nextX < R && 0 <= nextY && nextY < C) {
					if (visited[nextX][nextY] == 0) {
						enque(nextX, nextY);
						visited[nextX][nextY] = 1;
					}
				}
			}
		}
		if (flag) {
			break;
		}
		cnt++;
	}
	if (flag) {
		return res;
	}
	else {
		return -1;
	}
}

int main() {
	scanf("%d %d", &R, &C);

	for (int x = 0; x < R; x++) {
		scanf("%s", Graph[x]);
	}

	bool judge = false;
	for (int x = 0; x < R; x++) {
		for (int y = 0; y < C; y++) {
			if (Graph[x][y] == '#') {
				visited[x][y] = -1;
			}
			else if (Graph[x][y] == '.') {
				visited[x][y] = 0;
			}
			else if (Graph[x][y] == 'J') {
				if (x == 0 || x == R - 1 || y == 0 || y == C - 1) {
					judge = true;
				}
				enque(x, y);
				visited[x][y] = 1;
			}
			else {
				enque1(x, y);
				visited[x][y] = 4;;
			}
		}
	}
	if (judge) {
		printf("1\n");
	}
	else {
		int result = BFS();
		if (result < 0) {
			printf("IMPOSSIBLE\n");
		}
		else {
			printf("%d\n", result);
		}
	}

	return 0;
}

djm03178 2년 전 0

크기가 1000x1000인 격자판에서 BFS를 하면 큐에 동시에 1000개보다 훨씬 많은 칸이 동시에 들어가있어야 하는 경우가 생길 수 있습니다.

rlawnddnjs12 2년 전 0

@djm03178 감사합니다! 덕분에 해결하였습니다. 한가지 더 여쭤보고 싶은데 저 코드에서 말씀 하신대로 큐의 Size를 더욱 크게해주어 정답을 받았습니다.

하지만 메모리가 지금껏 보던 문제들과 다르게 많이 크게 나왔습니다. 메모리 효율성이 좋은 코드는 아닌 것 같은데 효율성을 높이기 위한 수정사항이나 조언같은 거 해주실 수 있나요,, 부탁드립니다!!

rlawnddnjs12 2년 전 0

@djm03178 큐의 최대크기를 바꿔가면서 제출하여 메모리 사용량을 확인해보니 큐의 크기에 따라 메모리 사용량이 달라지는 게 보입니다. 제 코드가 효율적인 측면에서 비효율적인지 여쭤보고싶습니다!!

djm03178 2년 전 0

메모리 사용량 자체가 얼마나 메모리를 많이 할당받았느냐를 의미하기 때문에 배열을 크게 잡으면 그 자체로 메모리 사용량이 크게 나오게 됩니다.

또한 이 문제 자체가 100만 칸이라는 큰 격자를 사용하기 때문에 다른 문제에 비해 필요한 메모리 자체가 많은 것은 어쩔 수 없다고 봅니다. 굳이 메모리를 줄이자면 좌표값이 그렇게 크지 않으니까 int 대신 short를 사용하는 방법 등이 있을 수 있겠지만, 일반적으로 메모리는 문제 풀이에서 크게 신경써야 하는 부분이 아니기 때문에 제한 내에만 넉넉하게 들었다면 그다지 줄이려고 노력하지 않아도 됩니다.

rlawnddnjs12 2년 전 0

@djm03178 답해주셔서 감사합니다

죄송하지만 하나 더 여쭤봐도 될까요 이 문제와 같은 유형의 문제<5427 - 불>을 풀고 있습니다 저는 같은 유형이라고 생각이 들어 이 문제에서 변형된 부분만 수정하고 코드를 제출하였습니다 근데 계속 틀려서 ,,,문제의 질문검색에 코드와 질문을 올렸는데 딥변 부탁드려도 될까요 ,,

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

문제

문제

출처

ICPC

테스트 케이스가 1000/1000일때만 틀립니다

rlawnddnjs12 2년 전 0

djm03178 2년 전 0

rlawnddnjs12 2년 전 0

rlawnddnjs12 2년 전 0

djm03178 2년 전 0

rlawnddnjs12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말