글 읽기 - 미치기 일보직전이에요 (C언어)

alstjr989898 3년 전 1

좌표, 바이러스 종류 정보를 담은 큐를 생성 합니다.

지도 정보를 입력 받다가 자연수가 나오면 나오는 순서대로 큐에 삽입하고,

바이러스 종류 기준으로 큐를 오름차순으로 정렬합니다.

그리고 큐의 헤드부터 시작해 BFS를 돌리는데, 이때 지도의 정보가 0이냐 바이러스냐로 나뉘기 때문에

굳이 방문 배열은 사용하지 않고 해당 칸이 0인지 아닌지만 확인 했습니다.

(방문 배열 포함했을때도 틀렸다고 나와서 코드를 간단하게 하기 위해 뺐습니다.)

진행하던 중에 시간이 초과하면 더 진행해도 의미가 없으니 BFS를 빠져나와 (X,Y)를 출력하도록 했습니다.

마지막으로 시간이 0일때도 처리해줬습니다. 뭐가 문제인가요? 알고리즘은 맞는거 같은데ㅠㅠㅠㅠㅠㅠㅠㅠ

미칠거같아요 도와주세요...

#include <stdio.h>
#define MAX 1002
#define max 202

typedef struct {
	int y, x, virus_Num;
}point;

point queue[max * max];
point temp;
int map[max][max];
int second[MAX * MAX] = { 0, };
int virus_Count[MAX] = { 0, };
int vectY[4] = { -1,1,0,0 };
int vectX[4] = { 0,0,-1,1 };
int N, K, S, X, Y, nextY, nextX, virus_Num;
int head = -1, rear = -1;

void BFS() {		// BFS진행, 큐가 오름차순으로 정리 돼 있으니 BFS가 진행해도 전염된 위치가 오름차순으로 정렬됨. 따라서 작은 숫자부터 전염함
	while (head < rear) {
		head++;

		for (int i = 0; i < 4; i++) {		// 상 하 좌 우 살피기
			nextY = queue[head].y + vectY[i];
			nextX = queue[head].x + vectX[i];

			if (nextY >= 1 && nextY <= N && nextX >= 1 && nextX <= N && !map[nextY][nextX]) {	// 해당좌표의 값이 자연수면 어차피 전염 못하니 방문체크 없이 해당좌표가 0인지만 확인
				rear++;
				second[rear] = second[head] + 1;
				if (second[rear] > S) {			//시간이 S보다 커졌다면 더이상 진행 할 필요 없으니 종료(전염 되기 전에 종료하므로 S시간만큼 전염시킨 map 상태로 종료됨)
					head = rear + 1;	// while문 탈출
					break;
				}
				queue[rear].y = nextY;
				queue[rear].x = nextX;
				queue[rear].virus_Num = queue[head].virus_Num;
				map[nextY][nextX] = queue[head].virus_Num;		//전염 과정
			}
		}
	}
}

int main(void) {
	scanf("%d %d", &N, &K);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf(" %1d", &map[i][j]);
			if (map[i][j] != 0) {		// 자연수 나오면 큐에 좌표와 바이러스종류(자연수) 저장
				rear++;
				queue[rear].y = i;
				queue[rear].x = j;
				queue[rear].virus_Num = map[i][j];
			}
		}
	}

	for (int i = 0; i <= rear; i++) {
		for (int j = i + 1; j <= rear; j++) {
			if (queue[i].virus_Num > queue[j].virus_Num) {		// 자연수가 작은거부터 진행하므로 큐를 바이러스(자연수) 오름차순으로 정렬
				temp = queue[i];
				queue[i] = queue[j];
				queue[j] = temp;
			}
		}
	}

	scanf("%d %d %d", &S, &X, &Y);

	if (S == 0) {			// 0초면 해당 좌표 출력하고 종료
		printf("%d", map[X][Y]);
		return 0;
	}

	BFS();

	printf("%d", map[X][Y]);

	return 0;
}

kdr06006 3년 전 1

48번째 줄에 %1d가 잘못되었습니다.

k 이하의 자연수가 입력되는데 k가 1000입니다.

k가 무조건 한자리 수의 자연수가 아니라서 %d를 사용해야 합니다.

alstjr989898 3년 전 0

감사합니다 !! 설마설마 했는데.. 이틀 날렸네요

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

문제

문제

출처

ICPC

미치기 일보직전이에요 (C언어)

alstjr989898 3년 전 1

kdr06006 3년 전 1

alstjr989898 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말