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

문제 링크입니다. https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

삼성 SW 역량테스트 기출 문제입니다.

까다로운 기출문제 였습니다.

문제 조건

출력 예시

문제에서 구현할 것은 물고기의 움직임 + 상어의 움직임 입니다.

 

물고기가 움직일 때는 조건이 있습니다.

먹힌 물고기가 아니며, 이동한 칸이 상어가 있는 곳이 아닐 경우에만 이동할 수 있습니다.

int map[5][5];  // 상어가 위치한 칸은 -1이다.
info info_fish[17];
int live_fish[17];
int dx[9] = { 0,-1,-1,0,1,1,1,0,-1 };  // 1 ~ 8은 각각의 방향
int dy[9] = { 0,0,-1,-1,-1,0,1,1,1 };  // 0칸은 안쓰는 칸

먼저 map 배열을 통해서 현재 물고기, 상어가 있는 위치를 저장했습니다.

info 구조체를 사용해, X번 물고기의 정보(크기, 이동 방향, 현재 위치)를 저장했습니다.

live_fish 배열을 통해서 X번 물고기가 살아있는지의 여부를 저장했습니다.

dx, dy 배열을 통해서 위쪽 이동부터 45도씩 반시계 방향까지 움직임을 만들었습니다.

 

위의 배열이 담고 있는 정보를 통해서 물고기의 움직임을 구현하겠습니다.

먼저 X번째 물고기가 살아있는지를 확인합니다.

X번 물고기가 살아있다면 해당 이동 방향으로 한번 움직여봅니다.

움직인 곳이 map 안이고 상어가 없는 곳일 경우가 있으며, map 바깥이거나 상어가 있는 곳일수도 있습니다.

 

먼저 map 안이며 상어가 없을 때에는 2가지가 있습니다. 

1. 빈칸일 경우 -> 해당 칸으로 이동을 한 뒤에 이동한 물고기의 위치를 바꾸어 줍니다.

2. 다른 물고기가 있을 경우 -> X번 물고기와 Y번 물고기의 위치를 바꾸어줍니다.

 

map 바깥이거나 상어가 있는 곳일 경우, 현재 이동 방향에서 45도씩 반시계 방향으로 움직여봅니다.

움직임이 끝나는 조건은 움직인 방향이 움직이는 곳의 방향과 같아질 때입니다. 

먼저 다른 방향으로 움직였을때 움직일 수 있는 곳을 만났다면 해당 방향으로 움직인 후에 물고기 위치를 바꾸어주면 됩니다.

움직였을 곳을 만나지 못했다면 움직이지 않으면 됩니다.

(코드는 move_fish() 함수를 확인해주세요)

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

이번에는 상어의 움직임을 구현하겠습니다.

상어 크기의 최댓값을 구해야 하기에 상어가 이동할 수 있는 모든 경우를 확인해야 합니다.

따라서 DFS를 통해 상어를 이동하면서 상어 크기를 계속 비교해주면 됩니다.

 

배열을 하나만 만들어서 상어를 움직였을 경우 DFS를 할 때마다 바뀌기 때문에 정확한 값을 구하지 못합니다.

따라서 현재 상태를 저장할 배열을 만들어서 DFS가 끝날때마다 해당 배열로 다시 만들어주면 됩니다.

 

상어는 이동 방향으로 어디든 갈 수 있기에 map의 범위를 벗어나지 않는 경우에서 전부 확인해봅니다.

빈칸은 이동할 수 없기에 물고기가 있는 곳만 이동합니다.

해당 방향으로 이동한 뒤 똑같이 DFS를 통해 끝까지 이동합니다.

(코드는 dfs() 코드를 확인해주세요)

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

문제 접근 방법

1. 현재 물고기의 정보와 살아있는지의 여부를 저장한다.

2. 상어가 (1,1)에서 시작하니 해당 칸에 물고기는 죽은 걸로 저장한다.

3. 위의 정보를 시작으로 물고기를 움직인다.

4. 상어를 움직인다.

5. 3번과 4번의 경우를 계속 반복하며 확인한다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

typedef struct info {
	int num;
	int way;
	int x;
	int y;
}info;
int ans;
int map[5][5];  // 상어가 위치한 칸은 -1이다.
info info_fish[17];
int live_fish[17];
int dx[9] = { 0,-1,-1,0,1,1,1,0,-1 };  // 1 ~ 8은 각각의 방향
int dy[9] = { 0,0,-1,-1,-1,0,1,1,1 };  // 0칸은 안쓰는 칸

void change_fish(int x, int y) {
	swap(map[info_fish[x].x][info_fish[x].y], map[info_fish[y].x][info_fish[y].y]);
	pair<int, int> place = { info_fish[x].x, info_fish[x].y };
	info_fish[x].x = info_fish[y].x;
	info_fish[x].y = info_fish[y].y;
	info_fish[y].x = place.first;
	info_fish[y].y = place.second;
}

void move_fish() {
	for (int i = 1; i <= 16; i++) {
		info fish = info_fish[i];
		if (live_fish[fish.num] == -1) continue;
		int x = fish.x + dx[fish.way];
		int y = fish.y + dy[fish.way];
		bool can_move = false;
		if (x >= 1 && x <= 4 && y >= 1 && y <= 4) {
			if (map[x][y] == 0) {
				can_move = true;
				info_fish[i].x = x;
				info_fish[i].y = y;
				map[x][y] = i;
				map[fish.x][fish.y] = 0;
			}
			else if (map[x][y] != -1) {
				can_move = true;
				change_fish(map[x][y], i);
			}
		}
		if (!can_move) {
			int next_way = fish.way + 1;
			if (next_way == 9) next_way = 1;
			while (next_way != fish.way) {
				int xx = fish.x + dx[next_way];
				int yy = fish.y + dy[next_way];
				if (xx >= 1 && xx <= 4 && yy >= 1 && yy <= 4) {
					if (map[xx][yy] == 0) {
						info_fish[i].x = xx;
						info_fish[i].y = yy;
						info_fish[i].way = next_way;
						map[xx][yy] = i;
						map[fish.x][fish.y] = 0;
						break;
					}
					else if (map[xx][yy] != -1) {
						info_fish[i].way = next_way;
						change_fish(map[xx][yy], i);
						break;
					}
				}
				next_way++;
				if (next_way == 9) next_way = 1;
			}
		}
	}
}

void change_state(int x, int y, int xx, int yy, int fish_num, bool state) {
	if (state) {
		map[x][y] = 0;
		live_fish[fish_num] = -1;
		map[xx][yy] = -1;
	}
	else {
		map[x][y] = -1;
		map[xx][yy] = fish_num;
		live_fish[fish_num] = 0;
	}
}

void dfs(int Size, int way, int x, int y) {
	ans = max(ans, Size);
	int copy_map[5][5];
	int copy_live_fish[17];
	info copy_fish[17];
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			copy_map[i][j] = map[i][j];
		}
	}
	for (int i = 1; i <= 16; i++) {
		copy_fish[i] = info_fish[i];
		copy_live_fish[i] = live_fish[i];
	}
	move_fish();
	for (int i = 1; i <= 3; i++) {
		int xx = x + dx[way] * i;
		int yy = y + dy[way] * i;
		if (xx >= 1 && xx <= 4 && yy >= 1 && yy <= 4) {
			if (map[xx][yy] != 0) {
				int fish = map[xx][yy];
				int new_way = info_fish[fish].way;
				change_state(x, y, xx, yy, fish, true);
				dfs(fish + Size, new_way, xx, yy);
				change_state(x, y, xx, yy, fish, false);
			}
		}
		else break;
	}
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			map[i][j] = copy_map[i][j];
		}
	}
	for (int i = 1; i <= 16; i++) {
		info_fish[i] = copy_fish[i];
		live_fish[i] = copy_live_fish[i];
	}
}

void solve() {
	int X = map[1][1];
	map[1][1] = -1;
	live_fish[X] = -1;
	dfs(X, info_fish[X].way, 1, 1);
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			int x, y;
			cin >> x >> y;
			map[i][j] = x;
			info_fish[x] = { x, y, i, j };
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요