백준 19236 청소년 상어 - C++

간단한 시뮬레이션 문제이다.

 

보통 상어가 나오는 문제 (마법사 상어, 아빠 상어...)

는 삼성 공채 SW검정 기출문제인 경우이다.

삼성이 목표라면 꼭 풀어봐야할 문제이므로 한 번 보자.

 

요즘 트렌드는 복잡한 알고리즘을 요구하지 않지만

문제 자체가 길고 꼼꼼하게 읽어야 엣지 케이스를 맞출 수 있으므로

천천히 하나하나 읽으면 된다.

 

 

 

문제를 잘 읽었으면 구현시 어려울 것 같은 부분이 보인다.

1. 상어는 물고기의 이동이 모두 끝난 후 이동한다.

2. 다른 물고기가 있는 칸으로 이동할 때 서로의 위치를 바꾸는 방식으로 이동한다.

3. 상어는 여러 칸을 이동할 수 있으나 이동하면서 지나가는 칸에 있는 물고기는 먹지 않는다.

4. 최대로 먹을 수 있는 물고기를 구해야한다.

 

다행히도 같은 칸에 여러 물고기가 존재하지 않는 문제이다.

물고기 또한 고정된 순서로 움직이므로 항상 상황은

상어의 움직임에 달려있기 때문에 

우리는 항상 최댓값을 구할 수 있다.

 

이 문제는 점수가 중간에 작다고 해서 최적화 할 수 없기도 하고

가지치기 할 만한 건이 없어보이므로 DFS로 

착실하게 시뮬레이션을 하면 되겠다.

#include <stdio.h>
#include <string.h>
int dy[] = {0, -1 , -1 , 0, 1 , 1 , 1 , 0 , -1};
int dx[] = {0, 0 , -1 , -1 , -1 , 0 , 1 , 1 , 1 };

int map[4][4][2];//번호, 방향
int moved[18];//17은 상어
int max;

void dfs(int num) {
	for (int nextnum = 1; nextnum <= 17; nextnum++) {
		//위치찾기
		int cy=-1, cx=-1;
		for (int i = 0; i < 4; i++) {
			for (int j= 0; j < 4; j++) {
				if (map[i][j][0] == nextnum) {
					cy = i;
					cx = j;
					break;
				}

			}
		}
		if (cy == -1 && cx == -1) continue;
		if (nextnum != 17) {
			//갈 방향 찾기
			int ny, nx;
			for (int i = 0; i < 8; i++) {
				int newdir = (i + map[cy][cx][1]);
				if (newdir > 8) newdir -=8;
				ny = cy + dy[newdir];
				nx = cx + dx[newdir];
				if (ny >= 4 || ny < 0 || nx >= 4 || nx < 0) continue;
				//상어피함
				if (map[ny][nx][0] == 17)continue;
				int tmp1 = map[ny][nx][0], tmp2 = map[ny][nx][1];
				map[ny][nx][0] = map[cy][cx][0];
				map[ny][nx][1] = newdir;
				map[cy][cx][0] = tmp1;
				map[cy][cx][1] = tmp2;
				break;

			}
		//없으면 안움직임
		}
		else {
			//상어 움직이기
			int tmpmap[4][4][2];
			memcpy(tmpmap, map, sizeof(map));
			for (int i = 1; i < 4; i++) {
				int ny = cy + i*dy[map[cy][cx][1]];
				int nx = cx + i*dx[map[cy][cx][1]];
				if (ny >= 4 || ny < 0 || nx >= 4 || nx < 0) continue;
				if (map[ny][nx][0] == 0) continue;
				int addnum = map[ny][nx][0];
				map[ny][nx][0] = 17;
				map[cy][cx][0] = 0;
				map[cy][cx][1] = 0;
				dfs(num+addnum);
				memcpy(map, tmpmap, sizeof(map));
			}
		}

	}

	if (num > max) max = num;
	return;
}

int solve() {
	int ret = map[0][0][0];
	map[0][0][0] = 17;
	dfs(ret);
	return max;
}

int main() {
	int a, b;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			scanf("%d %d", &a, &b);
			map[i][j][0] = a;
			map[i][j][1] = b;
		}
	}
	int ans = solve();
	printf("%d\n", ans);
}