글 읽기 - 어떤 부분이 틀린 걸까요...?

gkgkehdrms 2년 전 0

게시판에 있는 반례나 구글링해서 나온 반례 모두 넣었는데, 잘 나오고 있습니다.

어떤 부분이 틀렸길래... 답이 나오지 않는 걸까요..?

제가 푼 방식은

1. BFS로 그룹핑을 하면서 방문했던 정점을 모두 ax, ay 배열에 넣어둡니다.

2. 바닥에 닿을 경우 그냥 pass, 아닐 경우 ax, ay에 넣어둔 좌표를 가지고 클러스터를 떨어트리는 과정을 거치구요

3. 떨어트린 클러스터가 바닥에 닿을 경우 ax, ay에 저장해둔 좌표를 사용해서 기존 visit 배열의 값을 수정해줍니다.

어떤 부분이 문제가 될까요 ㅠㅠ

제가 직접 테케를 하나 만들었는데, 입력 조건에서 2개 이상의 클러스터가 동시에 떨어지는 경우가 없다고 하니...

아래 케이스는 애초에 입력 조건에 타당하지 않은 거 같고..

고수님들 조언 좀 부탁드립니다.

input

8 8
xxxxx...
...xxx..
x.xxx...
xxx.....
..xx...x
..x....x
..xxxxxx
.....x..
3
1
4
6

통과 코드 output

........
........
.xxxx...
x..xxx..
xxxxx...
..xx...x
..x....x
..xxxxxx

본인 코드 output

........
........
.xxxx...
...xxx..
..xxx...
..xx...x
x.x....x
xxxxxxxx

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int** visit;
int tri, n, m, ptr;

//BFS로 방문한 좌표를 저장하는 배열
int* ax, * ay;

int direc_x[4] = { 1, 0, -1, 0 };
int direc_y[4] = { 0, 1, 0, -1 };

//BFS를 위한 큐
typedef struct {
	int* y;
	int* x;
	int num;
	int rear;
	int front;
	int max;
} Queue;

//큐 초기화
void Ini(Queue* q)
{
	q->max = n * m;
	q->y = (int*)calloc(n * m, sizeof(int));
	q->x = (int*)calloc(n * m, sizeof(int));

	q->rear = q->front = q->num = 0;
}

void Enque(Queue* q, int x, int y)
{
	q->x[q->rear] = x;
	q->y[q->rear] = y;
	q->rear++;
	q->num++;
}

int De_x(Queue* q)
{
	int temp = q->x[q->front];
	return temp;
}

int De_y(Queue* q)
{
	int temp = q->y[q->front];
	return temp;
}

//좌표 디큐
void Deque(Queue* q, int* x, int* y)
{
	*x = De_x(q);
	*y = De_y(q);

	q->front++;
	q->num--;
}

int Empty(Queue* q)
{
	return (q->num != 0);
}

void Termi(Queue* q)
{
	free(q->x);
	free(q->y);
	q->num = q->max = q->front = q->rear = 0;
}

void BFS(int x, int y)
{
	int px, py;
	int start = ptr;
	px = x;
	py = y;

	//큐에 방문한 좌표를 넣으면서
	tri = 0;
	Queue q;
	Ini(&q);
	Enque(&q, px, py);
	visit[py][px] = 2;

	//ax, ay 배열에도 방문한 배열의 좌표를 추가
	ax[ptr] = x;
	ay[ptr++] = y;
	if (ay[ptr - 1] == n - 1) tri = 1;

	//방문한 좌표는 '2'로 수정, 바닥이 있을 경우 tri를 1로 변경해둠
	while (Empty(&q))
	{
		Deque(&q, &px, &py);
		for (int i = 0; i < 4; i++)
		{
			if (px + direc_x[i] >= 0 && px + direc_x[i] < m && py + direc_y[i] >= 0 && py + direc_y[i] < n)
			{
				if (visit[py + direc_y[i]][px + direc_x[i]] == 1)
				{
					visit[py + direc_y[i]][px + direc_x[i]] = 2;
					Enque(&q, px + direc_x[i], py + direc_y[i]);
					ax[ptr] = px + direc_x[i];
					ay[ptr++] = py + direc_y[i];
					if (ay[ptr - 1] == n - 1) tri = 1;
				}
			}
		}
	}


	//바닥에 닿지 않았을 경우 떨어져야 한다.
	//ax, ay에 저장해둔 좌표를 꺼내서 떨어지게 만들어줌
	//이 때 값은 3으로 변경
	//땅에 닿을 경우 tri를 1로 변경
	while (1)
	{
		if (tri == 1) break;
		else
		{
			int i;
			for (i = start; i < ptr; i++)
			{
				visit[ay[i]][ax[i]] = -1;
				visit[ay[i] + 1][ax[i]] = 3;
				ay[i]++;
				if (ay[i] + 1 == n) tri = 1;
				else if (visit[ay[i] + 1][ax[i]] == 1 || visit[ay[i] + 1][ax[i]] == 2) tri = 1;
			}
		}

	}

	for (int i = start; i < ptr; i++)
	{
		visit[ay[i]][ax[i]] = 2;
	}


	Termi(&q);
}

int main()
{
	int i, j, cnt, height;
	char temp;
	scanf("%d%d", &n, &m);
	getchar();
	visit = (int**)calloc(n, sizeof(int*));

	for (i = 0; i < n; i++)
	{
		visit[i] = (int*)calloc(m, sizeof(int));
	}

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			scanf("%c", &temp);
			if (temp == 'x') visit[i][j] = 1;
			else visit[i][j] = -1;
		}
		getchar();
	}

	scanf("%d", &cnt);
	ax = (int*)calloc(n * m * cnt, sizeof(int));
	ay = (int*)calloc(n * m * cnt, sizeof(int));

	for (i = 0; i < cnt; i++)
	{
		scanf("%d", &height);
		if (i % 2 == 0)
		{
			j = 0;
			while (1)
			{
				if (j == m) break;
				if (visit[n - height][j] == 1)
				{
					visit[n - height][j] = 0;
					break;
				}
				else j++;
			}
		}
		else if (i % 2 == 1)
		{
			j = m - 1;
			while (1)
			{
				if (j == -1) break;
				if (visit[n - height][j] == 1)
				{
					visit[n - height][j] = 0;
					break;
				}
				else j--;
			}
		}

		ptr = 0;



		for (int a = n - 1; a >= 0; a--)
		{
			for (int b = 0; b < m; b++)
			{
				if (visit[a][b] == 1)
				{
					BFS(b, a);
				}

			}
		}

		if (tri == 1)
		{
			int i;
			for (i = 0; i < ptr; i++)
			{
				visit[ay[i]][ax[i]] = 1;
			}
		}

	}

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (visit[i][j] == 1) printf("x");
			else printf(".");
		}
		if (i != n - 1) printf("\n");
	}

	return 0;
}

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

문제

문제

출처

ICPC

어떤 부분이 틀린 걸까요...?

gkgkehdrms 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말