글 읽기 - [반례들 추가] 38%를 못 넘어가네요... 반례 다 해봤습니다 도와주세요ㅠㅠ!

hoedown 4년 전 1

현재 아기상어 위치로부터 최소 거리 이동해가면서

먹잇감이 발견되면 후보로 선정하는 로직으로 bfs 구현하였는데요.

예제와 게시판에 있는 반례들 다 잘 되는데 38%에서 막혀버립니다ㅠㅠ

같은 거리에서 먹잇감이 될 수 있는 후보들 우선순위도 잘 설정해놨어요...

고수님들 도움 부탁드려요..!

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

#define MAX_SIZE 21

using namespace std;

int N;
int map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int fish[MAX_SIZE*MAX_SIZE];

int baby_size = 2;
int by, bx;
int fish_size = 0;
int dx[] = { 0, 1, 0 , -1 };
int dy[] = { 1, 0, -1 , 0 };
int main() {
	cin >> N;
	int num_fish = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				map[i][j] = 0;
				by = i; bx = j;
			}
		}
	}

	int total_time = 0;
	bool eat = true;
	while (eat) {
		eat = false;
		memset(visit, false, sizeof(visit));
		queue <pair<int, int>> baby;
		queue <int> cnt;
		queue <pair<int, int>> eatfish;
		baby.push(make_pair(by, bx));
		cnt.push(0);
		visit[by][bx] = true;

		while (!baby.empty()) {

			int num_baby = baby.size();
			int ccnt = cnt.front();

			for (int bi = 0; bi < num_baby; bi++) {
				int cy = baby.front().first; int cx = baby.front().second;
				for (int i = 0; i < 4; i++) {
					int ny = cy + dy[i]; int nx = cx + dx[i];
					if (ny >= 0 && ny < N && nx >= 0 && nx < N && !visit[ny][nx] && map[ny][nx] <= baby_size) {
						if (map[ny][nx] < baby_size && map[ny][nx] >0) {
							visit[ny][nx] = true;
							eat = true;
							eatfish.push(make_pair(ny, nx));
						}
						else {
							visit[ny][nx] = true;
							baby.push(make_pair(ny, nx));
							cnt.push(ccnt + 1);
						}
					}
				}
				baby.pop();
				cnt.pop();
			}
			

			int miny = MAX_SIZE; int minx = MAX_SIZE; int targety = MAX_SIZE; int targetx = MAX_SIZE;
			int num_eatfish = eatfish.size();
			if (eat) {
				for (int i = 0; i < num_eatfish; i++) {
					int tempy = eatfish.front().first; int tempx = eatfish.front().second;
					if (tempy < miny) {
						miny = tempy;
						targety = tempy;
						targetx = tempx;
					}
					else if (tempy == miny) {
						if (tempx < minx) {
							minx = tempx;
							targety = tempy;
							targetx = tempx;
						}
					}
					eatfish.pop();
				}
				map[targety][targetx] = 0;
				fish_size++;
				if (fish_size == baby_size) {
					fish_size = 0;
					baby_size++;
				}
				//cout << "냠냠 : " << targety << targetx << " 거리 : " << ccnt + 1 << " 상어크기 : " <<  baby_size <<endl;

				total_time = total_time + ccnt + 1;
				by = targety; bx = targetx;
				break;
			}

			
			
		}
	}
	cout << total_time;


	return 0;
}

hoedown 4년 전 0

이 반례들 다 맞는데 틀렸습니다라고 나와요ㅠㅠ

input
3 
0 1 1 
5 5 5 
0 9 0
answer : 0
    
    
input
6
1 0 0 0 0 0
6 6 6 6 6 0
1 0 6 0 9 0
2 0 6 0 6 6
6 0 0 0 6 6
6 6 6 6 6 6
answer : 25
    
    
input
20
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
answer : 209
  
    
input
3
9 3 1
3 1 1
1 1 1
answer : 0
    
    
input
4
1 0 0 0
0 9 0 0
0 0 1 0
0 0 0 1
answer : 8
    

input
3
9 3 1
2 2 2
3 3 3  
answer : 4  
    
    
input  
3
9 2 2
2 2 3
1 3 1
answer : 2  
    

input  
2
9 3
3 1
answer : 0
    
    
input  
6
1 2 1 1 1 1 
1 3 6 2 2 3 
1 2 5 2 2 3 
3 3 2 4 6 3 
0 0 0 0 0 6 
0 0 0 1 1 9
answer : 39

stronghsg 4년 전 0

저도 위 반례 다 맞게 나오는데 틀렸다고 채점됩니다..ㅠㅠ

고수님들 도와주세요..!

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>
#include <cmath>

using namespace std;

int check[20][20];
int nodes[20][20];

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

int shark_size = 2;
int eat_cnt = 0;
int min_dist = INT32_MAX;
int min_x = INT32_MAX;
int min_y = INT32_MAX;

void init(int W, int H)
{
	for (int j = 0; j < H; j++)
	{
		for (int i = 0; i < W; i++)
		{
			check[j][i] = 0;
		}
	}
	min_dist = INT32_MAX;
	min_x = INT32_MAX;
	min_y = INT32_MAX;

}

void bfs(int x, int y, int W, int H)
{

	queue<pair<int, int>> before;
	check[y][x] = 1;

	before.push(make_pair(x, y));

	while (!before.empty())
	{
		int cur_x = before.front().first;
		int cur_y = before.front().second;
		before.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + dx[i];
			int next_y = cur_y + dy[i];
			if (0 <= next_x && next_x < W && 0 <= next_y && next_y < H)
			{//지도 안인 경우
				if (check[next_y][next_x] == 0)
				{//방문한 적 없는 경우
					if (nodes[next_y][next_x] <= shark_size)
					{//방문 가능한 경우
					 //방문하고 check
						check[next_y][next_x] = check[cur_y][cur_x] + 1;
						before.push(make_pair(next_x, next_y));

						if (nodes[next_y][next_x] != 0 && nodes[next_y][next_x] < shark_size)
						{// 물고기 먹는 경우
							if (min_dist > check[next_y][next_x])
							{//만약 현재 check 물고기까지 거리가 더 짧다면
								min_x = next_x; // 최단거리 갱신
								min_y = next_y;
								min_dist = check[next_y][next_x];
							}
							else if (min_dist == check[next_y][next_x])
							{//같은 거리라면 가장 위, 왼쪽 물고기 먹는다.
								if (next_y < min_y)
								{
									min_y = next_y;
									min_x = next_x;
									if (next_x < min_x)
									{
										min_y = next_y;
										min_x = next_x;
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

int main()
{
	int N, sx, sy;
	scanf("%d", &N);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &nodes[j][i]);
			if (nodes[j][i] == 9)
			{
				sx = i;
				sy = j;
				nodes[j][i] = 0;
			}
		}
	}

	int result = 0;
	while (true)
	{
		init(N, N);//check 등 파라미터 초기화

		bfs(sx, sy, N, N);

		if (min_x != INT32_MAX && min_y != INT32_MAX)
		{//물고기 먹은적 있으면
			result += check[min_y][min_x] - 1; // 먹은 시간 더하기
			eat_cnt++; // 먹은 수 더하기
			if (eat_cnt == shark_size)
			{// 상어 성장
				eat_cnt = 0;
				shark_size++;
			}
			nodes[min_y][min_x] = 0; //물고기 먹었으니까

			sx = min_x;
			sy = min_y;

			/*printf("size: %d sx: %d sy: %d\n", shark_size, sx, sy);
			printf("result: %d\n", result);
			for (int j = 0; j < N; j++)
			{
			for (int i = 0; i < N; i++)
			{
			printf("%3d", nodes[j][i]);
			}
			printf("\n");
			}
			printf("\n");*/
		}
		else break; //먹을 물고기 없으면 끝냄
	}

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

	system("pause");
	return 0;
}

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

문제

문제

출처

ICPC

[반례들 추가] 38%를 못 넘어가네요... 반례 다 해봤습니다 도와주세요ㅠㅠ!

hoedown 4년 전 1

hoedown 4년 전 0

stronghsg 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말