글 읽기 - 아기상어 이자식...

kwakinmo 5년 전 0

아기상어 이자식... 힘드네요...

예외상황들을 최대한 넓게 생각해서 반례를 많이 만들어봤는데 틀린부분을 못찾았습니다ㅠㅠ

조언부탁드려요..!

#include <typeinfo>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector> 
using namespace std;

int N;
int map[21][21];
bool check[21][21];
int time;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

struct Fish {
	int x;
	int y;
	int size;
	int dist; // 상어와의 거리
};

Fish shark;
vector<Fish> smallfishes; // 상어가 먹을 수 있는 후보군을 저장.

bool cmp(Fish &a, Fish &b) { // 가장 가까운, 가장 위에, 가장 왼쪽에 있는 물고기.
	if (a.dist < b.dist) {
		return true;
	}
	else if (a.dist == b.dist) {
		if (a.x < b.x) {
			return true;
		}
		else if (a.x == b.x) {
			if (a.y < b.y) return true;
		}
	}
	return false;
}

int bfs(Fish candidate) { // 각 후보 물고기들과 아기상어와의 거리를 구해준다.


	queue<Fish> q;
	q.push(candidate);
	int smallfishDist = 0;

	check[candidate.x][candidate.y] = true; 

	while (!q.empty()) {
		Fish front = q.front();
		q.pop();
		check[front.x][front.y] = true; 
		

		// 후보고기 입장 + 아기상어 입장 에서 생각하자.
		for (int i = 0; i < 4; i++) { // 상하좌우로 탐색하면서 거리를 찾음.
			int nx = front.x + dx[i];
			int ny = front.y + dy[i];

			if (check[nx][ny]) continue; 
			check[nx][ny] = true; 
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) {
				continue; // 범위 넘어가면 버림.
			}
			if ((nx != shark.x || ny != shark.y) && map[nx][ny] > shark.size) continue; // 아기상어 위치가 아니면서 해당 위치의 물고기의 사이즈가 샤크의 사이즈보다 크면 못지나감
			


			if (nx == shark.x && ny == shark.y) { // 아기상어 찾으면 거리 리턴해주기.
				return front.dist + 1;
			}
			else {
				q.push({ nx,ny, front.size, front.dist + 1 }); // bfs 진행.
			}
		}
	}
	
	return 987654321; // 혹시 아기상어에 못 도달할수도.
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	// 초기화

	// 입력
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				shark = { i,j,2,0 };
			}
		}
	}

	int time = 0;
	int eatCnt = 0;

	// 알고리즘
	while (1) {  // 상어가 물고기 하나 잡아먹으면 다시 while문 돌아야 함.
		memset(check, 0, sizeof(check));
		smallfishes.clear();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0 || map[i][j] == 9) continue;
				if (map[i][j] < shark.size) smallfishes.push_back({ i,j,map[i][j],0 }); // 이 큐에는 아기상어가 잡아먹을 수 있는 후보군이 들어가 있다. 
			}
		} 

		if (smallfishes.size() == 0) { break; } // 1. 상어보다 작은 물고기가 없으면, 게임을 끝낸다.
		else if (smallfishes.size() == 1) { // 2. 상어보다 작은 물고기가 한마리면 가서 먹는다..
			for (int i = 0; i < (int)smallfishes.size(); i++) { // 각 후보군 마다 상어와의 거리 구해줌.
				smallfishes[i].dist = bfs(smallfishes[i]);
				memset(check, 0, sizeof(check));
			}

			// 가장 가까운 애를 골라서 잡아먹는다.
			if (smallfishes[0].dist != 987654321) { 
				int sharknx = smallfishes[0].x;
				int sharkny = smallfishes[0].y;
				map[shark.x][shark.y] = 0;
				map[sharknx][sharkny] = 9; // 상어 이동.
				shark = { sharknx,sharkny,shark.size,0 };
				time += smallfishes[0].dist; // 거리만큼 시간 ++
				eatCnt++; // 잡아먹은 카운트 ++
			}
			else { break; }
		}
		else { // 가장 가까이 있는 애들을 찾아서 그 중에 하나(가장위,가장왼쪽에 있는거)를 먹는다.
			for (int i = 0; i < (int)smallfishes.size(); i++) {
				smallfishes[i].dist = bfs(smallfishes[i]); // 각 후보군 마다 거리를 구해줌.
				memset(check, 0, sizeof(check));
			}

			// 가장 가까운 애를 찾아서, 먹자!!
			sort(smallfishes.begin(), smallfishes.end(), cmp);

			if (smallfishes[0].dist != 987654321) {
				int sharknx = smallfishes[0].x;
				int sharkny = smallfishes[0].y;
				map[shark.x][shark.y] = 0;
				map[sharknx][sharkny] = 9;
				shark = { sharknx,sharkny,shark.size,0 };
				time += smallfishes[0].dist;
				eatCnt++;
			}
			else { break; }
		}

		if (eatCnt == shark.size) { 	// 아기상어 사이즈 만큼 먹었으면 상어사이즈 ++
			eatCnt = 0;
			shark.size++;
		}
	}
	// 출력
	cout << time << '\n';
}

kwakinmo 5년 전 0

check[nx][ny] = true;
if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) {
continue;
}

이 두줄의 코드를 순서를 바꾸니 해결되었습니다.

nx가 -1 or N이거나

ny가 -1 or N일 때

범위 외 index 접근 때문에 틀린것 같은데, 이게 런타임에러가 발생한게 아니라 틀렸습니다로 나오는 이유를 알 수 있을까요???

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

문제

문제

출처

ICPC

아기상어 이자식...

kwakinmo 5년 전 0

kwakinmo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말