글 읽기 - 틀린 이유가 무엇일까요??.

new_face 7년 전 0

풀이 방법은 아래와 같습니다.
1. 겹쳐있는 부분을 라벨링합니다.

- label_bfs함수는 라벨링하는 함수,

-min_search_bfs함수는 거리를 찾는 함수입니다.

2. 기준 라벨로 다른 라벨을 찾으면서 거리를 구합니다.

3. 최종적으로 최소 거리를 찾게 됩니다.

제가 생각하지 못한 부분이 있나요?
코멘트 부탁드립니다.
감사합니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define SIZE 103
#define QUEUE_SIZE 10000001

int curState[SIZE][SIZE];
int labelState[SIZE][SIZE];
int visit[SIZE][SIZE];
int curQUEUE[2][QUEUE_SIZE];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
int N;

void label_bfs(int x, int y, int cnt);
int min_search_bfs(int x, int y);

int main()
{
	int i, j, min = 9999, temp_min;
	int cnt = 0, label_cnt = 1, k, l;

	scanf("%d", &N);

	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			scanf("%d", &curState[i][j]);

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if ((curState[i][j] == 1) && (labelState[i][j] == 0))
			{
				label_bfs(j, i, cnt);
				memset(visit, -1, sizeof(visit));
				cnt++;
			}
		}
	}
	
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (labelState[i][j] != 0)
			{
				temp_min = min_search_bfs(j, i);
				min = temp_min < min ? temp_min : min;
			}
		}
	}	
	printf("%d", min);
	return 0;
}
int min_search_bfs(int x, int y)
{
	int j,i, here_x, here_y, next_x, next_y, min, label_num;
	int front = 0, rear = 0, ret = 9999;
	int dis_visit[SIZE][SIZE];

	memset(dis_visit, -1, sizeof(dis_visit));

	label_num = labelState[y][x];
	dis_visit[y][x] = 0;
	curQUEUE[0][front] = x;
	curQUEUE[1][front] = y;
	front++;

	while (front > rear)
	{
		here_x = curQUEUE[0][rear];
		here_y = curQUEUE[1][rear];
		rear++;

		for (i = 0; i < 4; i++)
		{
			next_x = here_x + dx[i];
			next_y = here_y + dy[i];

			if (next_x < 0 || next_y < 0 || next_x >= N || next_y >= N)
				continue;

			if (labelState[next_y][next_x] != 0 && labelState[next_y][next_x] != label_num)
			{
				min = dis_visit[here_y][here_x];
				ret = min < ret ? min : ret;
			}
			if (dis_visit[next_y][next_x] == -1 && labelState[next_y][next_x] == 0)
			{
				dis_visit[next_y][next_x] = dis_visit[here_y][here_x] + 1;
				curQUEUE[0][front] = next_x;
				curQUEUE[1][front] = next_y;
				front++;
			}
		}
	}
	return ret;
}
void label_bfs(int x, int y, int cnt)
{
	int i, here_x, here_y, next_x, next_y;
	int front = 0, rear = 0;

	curQUEUE[0][front] = x;
	curQUEUE[1][front] = y;
	front++;

	while (front > rear)
	{
		here_x = curQUEUE[0][rear];
		here_y = curQUEUE[1][rear];
		rear++;
		labelState[here_y][here_x] = cnt;
		visit[here_y][here_x] = 1;

		for (i = 0; i < 4; i++)
		{
			next_x = dx[i] + here_x;
			next_y = dy[i] + here_y;

			if ((next_x >= 0) && (next_y >= 0) && (next_x < N) && (next_y < N) && (visit[next_y][next_x] == -1))
			{
				if (curState[next_y][next_x] == 1)
				{
					curQUEUE[0][front] = next_x;
					curQUEUE[1][front] = next_y;
					front++;
				}
			}
		}
	}
}

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

문제

문제

출처

ICPC

틀린 이유가 무엇일까요??.

new_face 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말