[백준] 16236번: 아기 상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

문제 이해

다른 상어가 물고기를 먹는 문제들보다 훨씬 간단하다.

일단 물고기 배열을 따로 만들지 않아도 된다는 점! 그냥 입력받은 맵으로만 처리가 가능한다. 

 

1. 상어가 먹을 수 있는 물고기의 좌표를 찾는다 -> BFS

2. 만약 먹을 수 있는 물고기가 없다면 종료한다.

3. 찾은 좌표에 물고기 없애고 상어 넣고, 시간(t)에 상어 위치에서 그 물고기까지의 거리를 더한다.

4. 상어의 사이즈 업은 본인 사이즈만큼의 물고기를 먹었을 때 일어난다.

 

처음에 마지막 4번을 제대로 안읽었다가 왜지..? 이러고 있었다.

 

그나마 설명할 부분이 먹을 수 있는 물고기 좌표를 찾는 BFS 부분이다. 

Find_Target()

그냥 BFS랑 거의 비슷한데 만약 방문하려는 위치 (ny, nx) 가 

• 그냥 빈칸이면 enq해주면 된다
• 상어 사이즈(shark.s) 보다 크면 못가므로 visit도 enq도 일어나지 않는다
• 상어 사이즈랑 같으면 갈 수는 있지만 먹지는 못한다. visit과 enq를 하지만, target으로 해줄 지를 처리하는 부분을 건너 뛴다
• 상어 사이즈보다 작으면 먹을 수 있다. 
  • 만약 기존 후보 물고기보다 거리가 가까우면 이 물고기를 target으로 해준다. 
  • 만약 거리가 같으면, y좌표가 더 작은지를 확인한다. 작으면 이 물고기를 target으로 해준다. 
  • 만약 y좌표도 같으면 x좌표가 더 작은지 확인한다. 작으면 이 물고기를 target으로 해준다.

void Find_Target(void) {
	// BFS 해야 함
	memset(visited, 0, sizeof(visited));
	wp = rp = 0;
	min_dis = 0x7fffffff;

	enq(shark.y, shark.x, 0);
	visited[shark.y][shark.x] = -1;
	
	while (!empty()) {
		ELE cur = deq();
		//if (cur.dis > min_dis) continue;
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (map[ny][nx] > shark.s) continue; // 본인보다 큼 --> 지나가지도 못함
			if (visited[ny][nx] != 0) continue;
			visited[ny][nx] = cur.dis + 1;
			enq(ny, nx, cur.dis + 1);
			if(map[ny][nx] > 0 && map[ny][nx] != 9){// 물고기다 --> 먹기를 시도
				if (map[ny][nx] == shark.s) continue; // 같은 사이즈 -> 못 먹음
				if (cur.dis + 1 < min_dis) { // 1. 거리
					tar_y = ny;
					tar_x = nx;
					min_dis = cur.dis + 1;
				}
				else if (cur.dis + 1 == min_dis) { // 2. 위쪽 우선
					if (ny < tar_y) {
						tar_y = ny, tar_x = nx;
						continue;
					}
					else if (ny == tar_y) {
						if (nx < tar_x) { // 3. 왼쪽 우선
							tar_y = ny, tar_x = nx;
							continue;
						}
					}
				}
			}
		}
	}
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 20

int N;
int map[MAXN + 1][MAXN + 1];
int visited[MAXN + 1][MAXN + 1];
typedef struct st {
	int y, x, s; // 좌표, 사이즈
}FISH;
FISH shark;
//FISH f[MAXN * MAXN + 5];
//int fcnt;

int min_dis = 0x7fffffff;
int tar_y, tar_x;

// 큐
typedef struct st2{
	int y, x, dis;
}ELE;
ELE q[MAXN * MAXN * 10];
int wp, rp;

void enq(int y, int x, int dis) {
	q[wp].y = y, q[wp].x = x, q[wp++].dis = dis;
}
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }

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

void Get_Input(void) {
	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) shark.y = i, shark.x = j, shark.s = 2;
			else if (map[i][j] != 0) {
				// 물고기
				//f[fcnt].y = i, f[fcnt].x = j, f[fcnt++].s = map[i][j];
			}
		}
	}
}

void Find_Target(void) {
	// BFS 해야 함
	memset(visited, 0, sizeof(visited));
	wp = rp = 0;
	min_dis = 0x7fffffff;

	enq(shark.y, shark.x, 0);
	visited[shark.y][shark.x] = -1;
	
	while (!empty()) {
		ELE cur = deq();
		//if (cur.dis > min_dis) continue;
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (map[ny][nx] > shark.s) continue; // 본인보다 큼 --> 지나가지도 못함
			if (visited[ny][nx] != 0) continue;
			visited[ny][nx] = cur.dis + 1;
			enq(ny, nx, cur.dis + 1);
			if(map[ny][nx] > 0 && map[ny][nx] != 9){// 물고기다 --> 먹기를 시도
				if (map[ny][nx] == shark.s) continue; // 같은 사이즈 -> 못 먹음
				if (cur.dis + 1 < min_dis) { // 1. 거리
					tar_y = ny;
					tar_x = nx;
					min_dis = cur.dis + 1;
				}
				else if (cur.dis + 1 == min_dis) { // 2. 위쪽 우선
					if (ny < tar_y) {
						tar_y = ny, tar_x = nx;
						continue;
					}
					else if (ny == tar_y) {
						if (nx < tar_x) { // 3. 왼쪽 우선
							tar_y = ny, tar_x = nx;
							continue;
						}
					}
				}
			}
		}
	}
}

int main(void) {
	Get_Input();
	int t = 0;
	int cnt = 0;
	while (1) {
		// 더 이상 먹을 수 없다 -> 종료
		Find_Target();
		if (min_dis == 0x7fffffff) break;
		
		// tar_y, tar_x 에 있는 물고기 먹으면 됨
		map[shark.y][shark.x] = 0;
		shark.y = tar_y, shark.x = tar_x;
		map[tar_y][tar_x] = 9;
		t += min_dis;
		cnt++;
		if (cnt == shark.s) {
			shark.s += 1;
			cnt = 0;
		}
	}
	printf("%d", t);
	return 0;
}