백준) 16236번: 아기 상어 in C

Made with Stable Diffusion

Problem

16236번: 아기 상어

Solution

 

그래프의 BFS와 시뮬레이션을 약간 복잡하게 꼬아놓은 문제이다.

 

먼저 문제부터 차례대로 이해해본다면

 

아기 상어는

- 처음 크기가 2,

- 자신의 크기보다 작거나 같은 크기의 물고기 칸만 이동 가능,

- 자신의 크기보다 작은 물고기만 먹을 수 있다,

- 자신의 크기와 같은 수의 물고기를 먹는다면 크기가 +1 증가한다. (그리고 다시 먹은 물고기의 수는 0으로 리셋)

- 1초에 상하좌우 한 칸만 움직인다.

- 먹을 수 있는 물고기 중 가장 가까운 물고기를 향해 간다.

- 같은 거리의 가까운 물고기가 여러 마리 있다면 가장 위에 있는 물고기, 그마저도 같다면 가장 왼쪽에 있는 물고기를 향해 움직인다.

- 더 이상 먹을 물고기가 없다면 그만 움직인다.(엄마 상어에게 도움 요청)

 

BFS를 여러 번 진행하고, 상어의 이동 시간을 더해주며 답을 구했다.

먼저 상어가 있는 위치에서부터 BFS를 통해 상어가 이동할 수 있는 모든 경로와 거리를 구한다.(visited 이용)

그리고 그 경로 내에 있는, 상어가 먹을 수 있는 물고기들 중 위 조건에 잘 부합하는 가장 가까운 물고기 하나를 고른다.

마지막으로 그 물고기가 있는 곳으로 상어의 위치를 변경하고 상어의 크기, 먹은 물고기 수, 이동할 때 걸린 시간도 그에 맞게 업데이트 한다.

그리고 변경된 상어의 위치부터 이전 과정(BFS)을 반복한다.

 

위 아기 상어의 규칙 중 

- 같은 거리의 가까운 물고기가 여러 마리 있다면 가장 위에 있는 물고기, 그마저도 같다면 가장 왼쪽에 있는 물고기를 향해 움직인다.

이 규칙이 조금 까다로운데 이는 이중 for 문을 돌리면서 바깥 for문은 위에서 아래로, 안쪽 for문은 왼쪽부터 오른쪽으로 탐색을 하면서 가장 거리가 가까운 물고기를 찾았다면 그 위치를 상어가 다음에 이동할 위치로 기록하고 바로 이중 for문을 break 함으로써 해결했다.

 

추가로 C언어에서 큐 자료구조는 x, y 좌표를 저장하거나 큐 크기가 크지 않은 경우, Linked List를 따로 만들 필요 없이 아래 코드와 같이 그냥 2차원 배열로 만들어도 된다는 것을 구글링하다가 알게 되었다. 코딩테스트에서 유용하게 쓸 수 있겠다. :)

 

Code

#include <stdio.h>

//큐를 2차원 배열로 구현.
int q[401][2] = {0, };
int front, rear;
int map[20][20], mapsize;
int shark_x, shark_y, sharksize = 2, shark_eat = 0;

// 상어의 이동 방향과 변화 크기.
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// BFS를 통해 상어를 규칙에 맞게 움직이고 움직인 거리를 반환.
int moveSharkBFS(){
	int i, j;
	
	int visited[20][20] = {0, };
	
	front = 0;
	rear = 0;
	
	// 처음 상어의 위치 큐에 입력 
	q[front][0] = shark_x;
	q[front][1] = shark_y;
	rear++;
	visited[shark_y][shark_x] = 1; 
	
	while(front < rear){
		// 현재 고려중인 상어 좌표를 큐에서 가져옴. 
		int x = q[front][0];
		int y = q[front][1];
		front++;
		
		for(i = 0; i<4; i++){
			// nx, ny는 상어 근처의 상하좌우 위치 좌표. 
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			// map 범위 밖일 경우 스킵. 
			if(nx < 0 || ny < 0 || nx >= mapsize || ny >= mapsize)
				continue;
			
			// 상어 크기 보다 큰 물고기가 있을 경우 또는 이미 방문했을 경우  스킵. 
			if(map[ny][nx] > sharksize || visited[ny][nx])
				continue;
			
			visited[ny][nx] = visited[y][x] + 1;
			
			// 큐에 삽입. 
			q[rear][0] = nx;
			q[rear][1] = ny;
			rear++;
		}
	} 

	// 상어가 이동할 수 있고 먹을 수 있는 물고기의 위치에 거리 값이 저장된다. 
	int edible[20][20] = {0, };
	// 상어가 현재 먹을 수 있는 물고기가 존재하면 1, 그 외 0. 
	int edible_flag = 0;
	// 먹을 수 있는 물고기들 중 가장 가까운 거리 값이 저장. 
	int minimum_distance = 999;
	
	for(i=0;i<mapsize;i++){
		for(j=0;j<mapsize;j++){
			if(visited[i][j] && map[i][j] < sharksize && map[i][j] > 0){
				// 1. 닿을 수 있고 2.  먹을 수 있는 물고기가 존재. 
                // edible에 물고기까지의 거리 저장.
				edible[i][j] = visited[i][j] - 1;
				edible_flag = 1;
				// 먹을 수 있는 물고기들 중 가장 가까운 거리를 탐색, 거리 값 업데이트. 
				if(visited[i][j] - 1 <= minimum_distance)
					minimum_distance = visited[i][j] - 1;
			}
		}
	}
	
	if(!edible_flag){
		// 더 이상 물고기를 먹을 수 없음. 
		return 0;
	}
	
	// 이중 for 문 break 위한 flag 
	int esc_flag = 0;
	// 상어가 물고기를 먹으러 도착할 최종 목적지 좌표. 
	int final_x = shark_x, final_y = shark_y;
	
	for(i=0;i<mapsize && !esc_flag;i++){
		for(j=0;j<mapsize;j++){
			if(minimum_distance == edible[i][j]){
				// 가까운 물고기들 중 가장 위, 왼쪽에 위치한 물고기의 위치 찾음. 
				esc_flag = 1;
				final_x = j;
				final_y = i;
				break;
			}
		}
	}
	
	// 새로운 상어 정보 업데이트.
	map[final_y][final_x] = 0;
	shark_x = final_x;
	shark_y = final_y;
	shark_eat++; 
	if(shark_eat == sharksize){
		// 상어가 자신의 크기만큼 먹었을 경우, 크기 + 1, 먹은 물고기 수 0 리셋
		shark_eat = 0;
		sharksize++;
	}
	
	return minimum_distance;
}; 

int main(){
	int i, j;
	
	scanf("%d", &mapsize);
	
	for(i=0;i<mapsize;i++){
		for(j=0;j<mapsize;j++){
			scanf("%d", &map[i][j]);
			if(map[i][j] == 9){
				// 처음 상어의 위치 저장. 
				shark_y = i;
				shark_x = j;
				map[i][j] = 0;
			}
		}
	}
	
	int total_distance = 0;
	int moved_distance = 0;
	
	while(1){
		if(!(moved_distance = moveSharkBFS()))
			break;
		total_distance += moved_distance;
	}
	
	printf("%d", total_distance);
	
	return 0;
}