글 읽기 - 16236번 논리 틀린것 좀 봐주실 수 있을까요?

stronghsg 4년 전 0

값을 뽑아보면 따로 부정확하게 움직이는것 같지는 않은거 같은데..

논리적으로 이상한 흐름이나 부족한부분 지적해주실 수 있을까요?

부탁드립니다.

6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

정답: 60, 출력: 53

6
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
0 0 0 0 0 6
0 0 0 0 0 9

정답: 39, 출력: 41

#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 = INT_MAX;
int min_x = INT_MAX;
int min_y = INT_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 = INT_MAX;
	min_x = INT_MAX;
	min_y = INT_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];
							}
						}					
					}
				}
			}
		}



	}
}

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 != INT_MAX && min_y != INT_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;
}

stronghsg 4년 전 0

조건을 덜 살폈네요..

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

문제

문제

출처

ICPC

16236번 논리 틀린것 좀 봐주실 수 있을까요?

stronghsg 4년 전 0

stronghsg 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말