글 읽기 - 집배원 한상덕 질문입니다

skgud3481 7년 전 0

BFS + 다익스트라로 풀었습니다.

테스트 케이스는 잘 나오는데 혹시 다른 테스트 케이스가 있을까요?

check배열은 각 정점에 가는 가장 작은 피로도를 저장하는 배열입니다.

더이상 최소 값을 찾을 수 없을 때 while문을 빠져 나오게 했고

빠져나온 뒤에 모든 K에 대한 가장 작은 피로도 중에 가장 큰 값을 출력하도록 했습니다.

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

#include <stdio.h>

char board[50][51];
int check[50][50];
int tired[50][50];
int x_q[100000];
int y_q[100000];
int t_q[100000];
int min[100000];
int max[100000];
int N;
int front, rear;
const int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = { 0, -1, -1, -1, 0, 1, 1, 1};

int checking(int xx, int yy)
{
	if (tired[yy][xx] >= min[front] && tired[yy][xx] <= max[front])//사이에 있을 때
		return 0;
	if (tired[yy][xx] < min[front])//min보다 작을 때
		return min[front] - tired[yy][xx];
	if (tired[yy][xx] > max[front]) //max보다 클 때
		return tired[yy][xx] - max[front];
}

void push(int xx, int yy, int tt, int mx, int mn)
{
	x_q[rear] = xx;
	y_q[rear] = yy;
	t_q[rear] = tt;
	if (mx < tired[yy][xx]) //mx가 tired보다 작을 때.
		max[rear] = tired[yy][xx];
	else
		max[rear] = mx;
	if (mn > tired[yy][xx])
		min[rear] = tired[yy][xx];
	else
		min[rear] = mn;
	++rear;
}

int main()
{
	int i, j, k;
	int nx, ny;
	int MIN, MAX;

	scanf("%d", &N);
	MIN = 100000000;
	MAX = 0;
	for (i = 0; i < N; ++i)
		scanf("%s", board[i]);
	for (i = 0; i < N; ++i)
		for (j = 0; j < N; ++j)
		{
			scanf("%d", &tired[i][j]);
			check[i][j] = 1000001;
			if (board[i][j] == 'P')
			{
				x_q[0] = j;
				y_q[0] = i;
				check[i][j] = tired[i][j];
				if (MIN > tired[i][j])
					MIN = tired[i][j];
				if (MAX < tired[i][j])
					MAX = tired[i][j];
			}
			if (board[i][j] == 'K')
			{
				if (MIN > tired[i][j])
					MIN = tired[i][j];
				if (MAX < tired[i][j])
					MAX = tired[i][j];
			}
		}

	front = 0;
	rear = 1;
	t_q[front] = MAX - MIN;
	max[front] = MAX;
	min[front] = MIN;

	while (front < rear)
	{
		for (i = 0; i < 8; ++i)
		{
			nx = x_q[front] + dx[i];
			ny = y_q[front] + dy[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N && check[ny][nx] > t_q[front] + checking(nx, ny))
			{
				push(nx, ny, t_q[front] + checking(nx, ny), max[front], min[front]);
				check[ny][nx] = t_q[front] + checking(nx, ny);
			}
		}
		++front;
	}

	MAX = 0;

	for (i = 0; i < N; ++i)
		for (j = 0; j < N; ++j)
			if (board[i][j] == 'K')//K인곳 중에서 제일 큰 곳
				if (check[i][j] > MAX)
					MAX = check[i][j];
	
	printf("%d\n", MAX);
	return 0;
}

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

문제

문제

출처

ICPC

집배원 한상덕 질문입니다

skgud3481 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말