글 읽기 - 백준 14502문제

streetsoul 1년 전 0

14502 문제 질문입니다.

맥에서 vi로 문제를 풀었는데, 두가지 문제가 있습니다.

1. queue 사이즈가 1000일 때 bus error
=> 다른 분들의 답을 봐도 queue 사이즈는 1000 정도면 되고, 실제 N, M 의 크기 제한을 고려했을 때도 1000이면 될 것 같은데 왜 bus error가 나는지 이해가 가질 않습니다.

2. 오답
=> 확산을 잘 하고 아무리 왜 오답인질 찾아봐도 코드 상으로 뭐가 문제인지 이해가 가질 않습니다.ㅠ.ㅠ

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

// BFS
int N, M;
int map[10][10]; // 0 is empty, 1 is wall, 2 is virus
int mapCpy[10][10];
int max;

typedef struct {
	int h;
	int w;
} Queue;

Queue queue[10000];

int rp, wp;
void push(int h, int w) {
	queue[wp].h = h;
	queue[wp].w = w;
	wp++;
}

Queue pop() {
	return queue[rp++];
}

void inputData() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

void BFS() {
	int dh[4] = { -1, 1, 0, 0 };
	int dw[4] = { 0, 0, -1, 1 };

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			mapCpy[i][j] = map[i][j];
			if (map[i][j] == 2) {
				push(i, j);
			}
		}
	}

	while (rp < wp) {
		Queue cur = pop();

		for (int i = 0; i < 4; i++) {
			int nh = cur.h + dh[i];
			int nw = cur.w + dw[i];

			if (nh < 0 || nh >= N || nw < 0 || nw >= M)
				continue;
			if (mapCpy[nh][nw] != 0)
				continue;

			mapCpy[nh][nw] = 2;
			push(nh, nw);
		}
	}

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (mapCpy[i][j] == 0)	cnt++;
		}
	}

	printf("cnt is %d\n", cnt);

	if (cnt > max)	max = cnt;
}

void solution(int wallCnt) {
	if (wallCnt == 3) {
		BFS();
		return;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				solution(wallCnt + 1);
				map[i][j] = 0;
			}
		}
	}
}

int main() {
	inputData();

	solution(0);

	printf("%d\n", max);
}

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

문제

문제

출처

ICPC

백준 14502문제

streetsoul 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말