boj, 백준) 19236. 청소년 상어 ( C / C++)

1. 문제 링크

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

19236번: 청소년 상어

2. 문제 개요

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

물고기는 자기가 갖고 있는 고유의 방향이 있는데, 그쪽 방향으로 이동할 수 있다. 이동할 수 있는 칸은 빈칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

 

상어는 한쪽 방향으로만 물고기를 먹을 수 있다. 그 물고기를 먹으면 그 물고기의 방향을 갖게 된다. 이동할 수 없는 칸을 만나게 되면 공간에서 벗어나 집으로 간다. 이 과정이 반복된다.

 

3. 문제 힌트

Backtracking으로 구현해보자.

큰 그림은 상어가 1칸 움직였을 경우, 2칸 움직였을 경우, 3칸 움직였을 경우에서,

1칸-1칸, 1칸-2칸, 1칸-3칸, 1칸-아웃(종료), 2칸-1칸... 이와 같은 식으로 따지고 보면 Brute force형태이지만, Out이라는, 즉 칸을 벗어나거나 더 이상 진행할 수 없는 경우에는 그냥 바로 종료한다는 점이 Brute force와는 조금 다르고 backtracking과 조금 가깝다고 생각한다.

 

4. 문제 풀이

 

물고기의 구조체는

y, x위치, 생사여부, 방향 이 4가지로 만들었다.

 

backtracking을 위해 각 상태마다 지역변수를 만들어서 복사해주어야 한다.

그리고 상어 -> 물고기 순서대로 문제에 나와있는 대로 구현을 하면 된다.

 

이 문제는 특별한 알고리즘이 필요한 것은 아니기 때문에 구현력에 따라 문제의 난이도가 결정된다고 생각한다.

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

struct FISH{
	int y, x, dir;
	bool isdead;
};


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

void cpmap(int dest[4][4], int src[4][4])
{
	for(int i = 0; i < 4; ++i)
		for (int j = 0; j < 4; ++j)
			dest[i][j] = src[i][j];
	return;
}
void cpfish(FISH dest[17], FISH src[17])
{
	for (int i = 0; i <= 16; ++i)
		dest[i] = src[i];
}
int dfs(int origin_map[][4], int y, int x, int dir, FISH origin_fish[17])
{
	
	int map[4][4];
	FISH fish[17];
	cpmap(map, origin_map);
	cpfish(fish, origin_fish);
	//상어 y,x에 놓을것
	int eat = map[y][x];
	//여기서 dir결정
	dir = fish[map[y][x]].dir;

	fish[map[y][x]].x = -1;
	fish[map[y][x]].y = -1;
	fish[map[y][x]].isdead = true;
	map[y][x] = 0;

	int ans = 0;
	
	
	//물고기 이동
	for (int i = 1; i <= 16; ++i) {
		if (fish[i].isdead == false){

			int nx = fish[i].x, ny = fish[i].y;
			for (int d = 0; d <= 7; ++d){
				int cx = fish[i].x + dx[fish[i].dir];
				int cy = fish[i].y + dy[fish[i].dir];

				//상어면 방향바꾸기 1 ~ 8이지
				if (cx == x && cy == y) {
					fish[i].dir = (fish[i].dir + 1) % 8;
					continue;
				}
				//경계밖이면 방향바꾸기
				if (cx < 0 || cy < 0 || cx >= 4 || cy >= 4) {
					fish[i].dir = (fish[i].dir + 1) % 8;
					continue;
				}

				nx = cx;
				ny = cy;
				break;
			}
			
			//next위치의 물고기와 자리 바꾸기
			if (map[ny][nx] == 0) {
				map[fish[i].y][fish[i].x] = 0;
				map[ny][nx] = i;
				fish[i].y = ny;
				fish[i].x = nx;
			}
			else
			{
				int tx, ty, temp;
				tx = fish[i].x;
				ty = fish[i].y;
				fish[i].x = nx;
				fish[i].y = ny;
				fish[map[ny][nx]].x = tx;
				fish[map[ny][nx]].y = ty;

				map[ty][tx] = map[ny][nx];
				map[ny][nx] = i;
			}
		}
	}


	//먹을 물고기가 없거나 밖으로 나가면
	int cy = y + dy[dir];
	int cx = x + dx[dir];

	while (!(cy < 0 || cx < 0 || cy >= 4 || cx >= 4 )) {
		if(map[cy][cx] != 0)
			ans = max(ans, dfs(map, cy, cx, dir,fish));
		cy += dy[dir];
		cx += dx[dir];
	}
	return ans + eat;
}

int main()
{
	int map[4][4] = { 0 };
	FISH fish[17];
	for(int i=0; i<4; ++i)
		for (int j = 0; j < 4; ++j){
			int l, d;
			scanf("%d %d", &l, &d);
			fish[l].y = i;
			fish[l].x = j;
			fish[l].isdead = false;
			fish[l].dir = d - 1;
			map[i][j] = l;
		}
	
	printf("%d", dfs(map, 0, 0, 0, fish));
	return 0;
}

6. 결과

지적 댓글 환영입니다!