글 읽기 - 25%에서 막히는데 혹시 문제점이 있는지 봐주실수 있으실까요..

pok35 1년 전 0

계속 고민하고 있는데 문제가 있는 부분이 보이지를 않습니다..

게시판 내에 있는 반례는 다 찾아봤는데 도와주시면 감사하겠습니다 50 * 50 데이터도 넣어봤는데

2차원 배열에서는 튀는 부분은 없는 거 같은데 말입니다... 감사합니다.

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>

using namespace std;

int map[50][50];
int map_visit[50][50];
int map_visit_original[50][50];

int map_checked_recursive[50][50];


int N;
int M;

queue<pair<int, int>> q;

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

int min_time = 999999;

int possible = -1;

void bfs(int start_x, int start_y) {
	int count = 1;

	memcpy(map_visit, map_visit_original, sizeof(map_visit));

	q.push({ start_x, start_y });
	map[start_y][start_x] = -1;
	map_visit[start_y][start_x] = 1;

	int start_flag = 0;


	while (!q.empty()) {

		int temp_x = q.front().first;
		int temp_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int moved_x = temp_x + dx[i];
			int moved_y = temp_y + dy[i];

			if (moved_x < 0 || moved_x >= N || moved_y < 0 || moved_y >= N) {
				continue;
			}
			else if (map_visit[moved_y][moved_x] == 1) {
				continue;
			}
			else {
				q.push({ moved_x ,moved_y });
				map_visit[moved_y][moved_x] = 1;
				if (map[moved_y][moved_x] == 0 || map[moved_y][moved_x] == -1 || map[moved_y][moved_x] >= map[temp_y][temp_x]) {
					if (start_flag == 0) {
						map[moved_y][moved_x] = 1;
					}
					else {
						map[moved_y][moved_x] = map[temp_y][temp_x] + 1;
					}
				}


			}
		}

		start_flag = 1;

	}

}

void start_check_virus_spread_time(int left_virus, int start_x, int start_y) {

	/*printf("%d ", left_virus);*/

	if (left_virus == 0) {

		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map_visit_original[i][j] == -1) {
					map[i][j] = -1;
				}
			}
		}


		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 999) {
					continue;
				}
				if (map[i][j] == 0) {
					return;
				}
				if (max < map[i][j]) {
					max = map[i][j];
				}
			}
		}

		possible = 1;

		if (max < min_time) {
			min_time = max;
		}

		return;
	}
	else {

		int current_x = start_x;
		int current_y = start_y;


		while (1) {


			if (current_y > N - 1) {
				break;
			}


			if (map_visit_original[current_y][current_x] == -1) {

				int map_prev[50][50];

				memcpy(map_prev, map, sizeof(map_prev));
				/*printf("%d %d\n", current_x, current_y);*/
				bfs(current_x, current_y);

				map_checked_recursive[current_y][current_x] = 1;

				if (current_x == N - 1) {
					/*printf("%d %d\n", current_y, current_x);*/
					start_check_virus_spread_time(left_virus - 1, 0, current_y + 1);
				}
				else {
					/*printf("%d %d\n", current_y, current_x);*/
					start_check_virus_spread_time(left_virus - 1, current_x + 1, current_y);
				}
				map_checked_recursive[current_y][current_x] = 0;

				memcpy(map, map_prev, sizeof(map));


			}

			if (current_x == N - 1) {
				current_y += 1;
				current_x = 0;
			}
			else {
				current_x += 1;
			}


		}
	}
	
}



int main() {

	freopen("텍스트.txt", "r", stdin);

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			scanf("%d", &map[i][j]);

			if (map[i][j] == 1) {
				map_visit_original[i][j] = 1;
				map[i][j] = 999;
			}
			else if (map[i][j] == 2) {
				map_visit_original[i][j] = -1;
				map[i][j] = -1;
			}

		}
	}

	start_check_virus_spread_time(M, 0, 0);

	if (possible == -1) {
		printf("-1");
	}
	else {
		printf("%d", min_time);
	}



	return 0;
}

pok35 1년 전 0

54 ~ 60 줄에서 bfs를 돌릴 때 이전에 있는 값 중에서 최솟값으로 교체해주는 분에서 기존에서 이동했을 때 +1이 되므로 이 값과 비교를 했어야 했는데

그부분을 망각하고 비교를 해서 문제가 답이 틀렸습니다. 반례가 되는 조건들이 다 통과를 해서 찾는데 오래걸렸네요....

혹시 10%에서 틀리는 분이 계시다면 참고하면 좋을 듯 합니다.

if (map[moved_y][moved_x] == 0 || map[moved_y][moved_x] == -1 || map[moved_y][moved_x] >= map[temp_y][temp_x]+1)// 이부분에 +1을 추가 {
					if (start_flag == 0) {
						map[moved_y][moved_x] = 1;
					}
					else {
						map[moved_y][moved_x] = map[temp_y][temp_x] + 1;
					}

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

문제

문제

출처

ICPC

25%에서 막히는데 혹시 문제점이 있는지 봐주실수 있으실까요..

pok35 1년 전 0

pok35 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말