글 읽기 - 시간초과 질문입니다

hswsua 6년 전 0

테스트 케이스는 맞는 것 같은데

7%에서 시간초과가 납니다..ㅠ

왜 이러는지 알려주세요..

#include <stdio.h>
#define MAX_SIZE 10000

typedef struct Queue {
	int front, rear;
	int arr[MAX_SIZE];
}Queue;

void init(Queue *q) {
	q->front = q->rear = 0;
}

int is_empty(Queue *q) {
	return q->front == q->rear;
}

int is_full(Queue *q) {
	return q->front == (q->rear + 1) % MAX_SIZE;
}

void enqueue(Queue *q, int value) {
	if (is_full(q)) {

	}
	else {
		q->arr[q->rear] = value;
		q->rear = (q->rear + 1) % MAX_SIZE;
	}
}

int dequeue(Queue *q) {
	int temp = 0;
	if (is_empty(q)) {
		return  -2;
	}
	else {
		temp = q->arr[q->front];
		q->front = (q->front + 1) % MAX_SIZE;
		return temp;
	}
}

int R = 0, C = 0;
char map[1010][1010] = { 0 };

int main(void) {

	Queue jq1, fq1;
	init(&jq1);
	init(&fq1);
	int check = 0;

	int r = 0, c = 0;
	int size = 0;
	int success = 0;
	int result = 0;
	int exit = 0;

	scanf("%d %d", &R, &C);


	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) { // 맵 그리기, 불과 지훈 위치 기억
			scanf(" %c", &map[i][j]);
			if (map[i][j] == 'F') {
				enqueue(&fq1, i * 10000 + j); // 불 삽입
			}
			else if (map[i][j] == 'J') {
				enqueue(&jq1, i * 10000 + j); // 지훈 삽입
			}
		}
	}

	while (1) {

		result++;

		//printf("?\n");

		// 불 먼저
		size = fq1.rear - fq1.front;
		if (size != 0) {
			//printf("fire size = %d\n", size);
			for (int i = 0; i < size; i++) {

				exit = dequeue(&fq1);// 불 위치
				r = exit / 10000;
				c = exit % 10000;

				//printf("fire   r = %d   c = %d\n", r, c);

				if (r - 1 >= 0 && map[r - 1][c] != '#' && map[r - 1][c] != 'F') { // 지훈이 or 빈 공간일 때 map 확장
					map[r - 1][c] = 'F';
					enqueue(&fq1, (r - 1) * 10000 + c);
				}
				if (r + 1 < R && map[r + 1][c] != '#' && map[r + 1][c] != 'F') {
					map[r + 1][c] = 'F';
					enqueue(&fq1, (r + 1) * 10000 + c);
				}
				if (c - 1 >= 0 && map[r][c - 1] != '#' && map[r][c - 1] != 'F') {
					map[r][c - 1] = 'F';
					enqueue(&fq1, r * 10000 + c - 1);
				}
				if (c + 1 < C && map[r][c + 1] != '#' && map[r][c + 1] != 'F') {
					map[r][c + 1] = 'F';
					enqueue(&fq1, r * 10000 + c + 1);
				}
			}
		}

		// 지훈
		size = jq1.rear - jq1.front;
		for (int i = 0; i < size; i++) {

			exit = dequeue(&jq1);
			r = exit / 10000; // 지훈이 위치
			c = exit % 10000;

			//printf("지훈   r = %d   c = %d\n", r, c);

			if (r - 1 < 0 || r + 1 >= R || c - 1 < 0 || c + 1 >= C) { // 탈출 조건
				success = 1;
				break;
			}

			if (map[r - 1][c] == '.') { // 빈 공간이면 확장
				map[r - 1][c] = 'J';
				enqueue(&jq1, (r - 1) * 10000 + c);
			}
			if (map[r + 1][c] == '.') {
				map[r + 1][c] = 'J';
				enqueue(&jq1, (r + 1) * 10000 + c);
			}
			if (map[r][c - 1] == '.') {
				map[r][c - 1] = 'J';
				enqueue(&jq1, r * 10000 + c - 1);
			}
			if (map[r][c + 1] == '.') {
				map[r][c + 1] = 'J';
				enqueue(&jq1, r * 10000 + c + 1);
			}
		}

		if (success == 1) {
			break;
		}

		//printf("jq.front = %d   jq.rear = %d\n", jq1.front, jq1.rear);
		if (jq1.front == jq1.rear) { // 지훈이 큐가 비어있으면 탈출
			break;
		}
	}

	if (success == 1) {
		printf("%d\n", result);
	}
	if (success == 0)
		printf("IMPOSSIBLE\n");

	return 0;

}

sgchoi5 6년 전 0

waterloo 문제는 대회에서 사용했던 TC 가 공개되어 있으니 써 보세요..

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

시간초과 질문입니다

hswsua 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말