글 읽기 - 유기농배추 틀린이유를 모르겠습니다..

jy0935 3년 전 0

문제를 다시 처음부터 풀며 로직을 바꿔서 시간초과 문제는 개선했습니다.

그러니 다시 반례를 찾지 못하고 있네요ㅠ 반례를 직접 만들어서도 해보고 게시판에 있는 반례는 대부분 시도 해보았습니다.

혹시 코드상에 틀린점이 있는걸까요?

혹시 (struct Node) 이렇게 캐스팅해서 쓰는게 잘못된건가요?

#include <stdio.h>
#include <stdlib.h>

int T, M, N, K;
int W, H;
int answer;

struct Node {
	int x;
	int y;
};


//배추의 위치가 담긴 배열
int Map[51][51];

struct Node Qdata[10000];
int rear = -1;
int front = -1;


void enQueue(struct Node d) {
	rear++;
	Qdata[rear] = d;
}

struct Node deQueue() {
	front++;
	return Qdata[front];
}

int isEmpty() {
	return front == rear;
}

void bfs(int i, int j) {
	
	front = -1;
	rear = -1;

	enQueue((struct Node){i,j});

	while (isEmpty() == 0) {
		struct Node now = deQueue();

		if(now.y < N - 1){
			if (Map[now.x][now.y + 1] == 1) {
				now.y += 1;
				enQueue((struct Node){ now.x, now.y });
				Map[now.x][now.y] = 0;
			}
		}		
		if (now.y > 0) {
			if(Map[now.x][now.y - 1] == 1) {
				now.y -= 1;
				enQueue((struct Node){ now.x, now.y });
				Map[now.x][now.y] = 0;
			}
		}
		if(now.x < M - 1){
			if(Map[now.x + 1][now.y] == 1) {
				now.x += 1;
				enQueue((struct Node){ now.x, now.y });
				Map[now.x][now.y] = 0;
			}
		}
		if ((now.x > 0)) {
			if (Map[now.x - 1][now.y] == 1) {
				now.x -= 1;
				enQueue((struct Node){ now.x, now.y });
				Map[now.x][now.y] = 0;
			}	
		}
	}
}

int main() {

	scanf("%d", &T); //테스트 케이스 입력

	for (int i = 0; i < T; i++) 
	{
		scanf("%d %d %d", &M, &N, &K); //가로, 세로길이, 배추의 개수 입력


		for (int i = 0; i < K; i++) { //배추의 각 좌표를 Map에 입력함, 배추의 좌표가 들어있는 Map에는 숫자 1이 들어가있음.
			scanf("%d %d", &W, &H);
			Map[W][H] = 1;
		}


		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (Map[i][j] == 1) {
					Map[i][j] = 0;
					bfs(i, j);
					answer++;
				}
			}
		}

		printf("%d\n", answer);


		if (i != T - 1) {
			//이전 테스트 케이스에 입력된 값이 영향을 끼치지 않도록 초기화가 필요함...
			answer = 0;
		}
	}
}

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

문제

문제

출처

ICPC

유기농배추 틀린이유를 모르겠습니다..

jy0935 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말