글 읽기 - 예제 4번에서...

zhoang3 5년 전 1

예제 4번에서 56개로 나옵니다...

다른 예제는 다 통과했는데... 심지어 다른 분이 말하는 반례들도 통과했습니다...

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

BFS를 사용해서 먹이까지 초를 측정하고 먹이를 못먹으면 초를 측정하지 않았습니다.

#define MAX 20

#include<iostream>
#include<memory.h>
#include<queue>

using namespace std;

int N;
int res, eat;
int map[MAX][MAX];
bool visit[MAX][MAX];

int nr, nc;

int dx[4] = { -1, 0, 0, 1 }; //상 좌 우 하
int dy[4] = { 0, -1, 1, 0 };

struct shark {
	int r;
	int c;
	int size;
}baby;

void BFS(int r, int c) {

	int time = 0;

	queue<pair<int, int>> q;
	queue<pair<int, int>> q2;

	memset(visit, false, sizeof(visit)); //먹이까지 거리 계산을 위한 방문 체크
	visit[r][c] = true; //현재 상어의 위치 visit

	q.push({ r,c });

	while (1) {

		time++;
		
		while (!q.empty()) {
			auto current = q.front();
			q.pop();

			for (int i = 0; i < 4; i++) { //상좌우하 순으로
				nr = current.first + dx[i];
				nc = current.second + dy[i];

				if (visit[nr][nc] || nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
				// 이미 방문했거나 범위를 벗어난다면
				if (map[nr][nc] && map[nr][nc] < baby.size) { //물고기가 있고 상어보다 크기가 작으면
					map[nr][nc] = 0; eat--; //빈칸으로 채우고 횟수 차감

					if (eat == 0) { //횟수대로 먹었다면
						baby.size++; //크기 상승
						eat = baby.size; //크기만큼 횟수 수정
					}
					res += time; //먹이를 먹었으므로 시간 추가
					BFS(nr, nc); //재귀
					return;
				}
				else if (!map[nr][nc] || map[nr][nc] == baby.size) {
					visit[nr][nc] = true;
					q2.push({ nr,nc });
				}
			}
		}

		if (q2.empty()) break;

		time++;
		
		while (!q2.empty()) {
			auto current = q2.front();
			q2.pop();

			for (int i = 0; i < 4; i++) {
				nr = current.first + dx[i];
				nc = current.second + dy[i];

				if (visit[nr][nc] || nr < 0 || nc < 0 || nr >= N || nc >= N) continue;

				if (map[nr][nc] && map[nr][nc] < baby.size) {
					map[nr][nc] = 0; eat--;

					if (eat == 0) {
						baby.size++;
						eat = baby.size;
					}
					res += time;
					BFS(nr, nc);
					return;
				}
				else if (!map[nr][nc] || map[nr][nc] == baby.size) {
					visit[nr][nc] = true;
					q.push({ nr,nc });
				}
			}
		}
		if (q.empty()) break; 
	}

}

int main() {
	scanf("%d", &N);

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

			if (map[i][j] == 9) {
				baby = { i, j, 2 };
				map[i][j] = 0; //상어 자리를 빈칸으로
 			}
		}
	}

	eat = baby.size; //상어의 크기에 맞게 먹는 횟수 카운트
	BFS(baby.r, baby.c);

	printf("%d\n", res);
}

ljs921026 4년 전 5

저도 bfs써서 4번예제 56 나왔어서 보니까

상어가 (0,2)에서 다음번 (0,4)로 움직여야하는데

(1,1)로 움직이더라구요

그부분 한번 확인해보세요

저는 bfs안에 우선순위큐 좀 섞어서 해결했습니다.

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

문제

문제

출처

ICPC

예제 4번에서...

zhoang3 5년 전 1

ljs921026 4년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말