백준 16236 - 아기 상어

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

16236번: 아기 상어

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

 

아기 상어는 위와 같은 규칙으로 움직입니다.

문제를 해결하기 위해서 구현해야 할 기능은 상, 하, 좌, 우로 움직이며 갈 수 있는 칸 찾기, 규칙에 따라서 갈 수 있는 칸 정렬, 아기 상어의 정보 변경하기를 구현해야 합니다.

 

1. 기본 설정

    아기 상어가 갈 수 있는 칸 중에서 자신이 먹을 수 있는 물고기가 있을 수 있습니다.

    그렇다면 그 좌표를 구조체 백터를 선언해 넣어줬습니다. 

    아기 상어의 정보는 항상 변할 수 있어야합니다. 따라서 구조체를 선언해 아기 상어의 정보를 저장했습니다.

    BFS 탐색을 끝낸 뒤, 1. 백터의 크기가 0이라면 시간 출력하고 끝

                              2. 백터의 크기가 1이라면 해당 좌표를 아기 상어에 입력하고 나머지 정보 갱신

                              3. 백터의 크기가 1 이상이라면 규칙에 따라 정렬 후에 맨 앞의 정보를 아기 상어에 입력, 갱신

  

 

2. 상하좌우로 움직이며 갈 수 있는 칸 찾기

   아기 상어는 자신보다 크기가 작다면 먹고, 크기가 같다면 움직이기만 하고, 크기가 크다면 그 칸으로 가지 못합니다.

   그렇다면 BFS를 구현할 때 1. check[x][y] == 0 이면서 해당 좌표의 크기가 0이면 움직이기만 합니다.

                                     2. check[x][y] == 0 이면서 아기 상어보다 작다면 움직인 후에 백터에 넣어줍니다.

                                     3. check[x][y] == 0 이면서 아기 상어와 크기가 같다면 움직이기만 합니다.

 

 

3. 규칙에 따라서 칸 정렬하기

   문제 조건을 봤을 때 정렬 조건은 1. 거리, 2. X좌표, 3. Y좌표입니다.

   위에 있다는 의미는 X좌표가 작다는 의미이고 왼쪽에 있다는 의미는 Y좌표가 작다는 의미입니다.

   다음은 규칙에 따라 정렬하는 코드입니다.

bool cmp(fi a, fi b) {
	if (a.route < b.route) {
		return true;
	}
	else if (a.route == b.route) {
		if (a.x < b.x) {
			return true;
		}
		else if (a.x == b.x) {
			if (a.y < b.y) {
				return true;
			}
			return false;
		}
		return false;
	}
	return false;
}

    

1, 2, 3번을 모두 이해하셨다면 문제를 쉽게 풀 수 있습니다.

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

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int num;
int arr[4] = { 1,-1,0,0 };
int arr2[4] = { 0,0,1,-1 };
typedef struct fi {
	int x;
	int y;
	int route;
}fi;
typedef struct qu {
	int x;
	int y;
	int size_shark;
	int time;
	int eat;
}qu;
vector<fi> fish;
qu S;
int shark[21][21];
int check[21][21];

bool cmp(fi a, fi b) {
	if (a.route < b.route) {
		return true;
	}
	else if (a.route == b.route) {
		if (a.x < b.x) {
			return true;
		}
		else if (a.x == b.x) {
			if (a.y < b.y) {
				return true;
			}
			return false;
		}
		return false;
	}
	return false;
}

void find_can_eat(int a, int b);

void solution() {
	while (1) {
		fish.clear();
		memset(check, 0, sizeof(check));

		find_can_eat(S.x, S.y);
		if (fish.size() == 0) {
			cout << S.time;
			break;
		}
		else if (fish.size() == 1) {
			//cout << fish[0].route << "\n";
			shark[fish[0].x][fish[0].y] = 9;
			shark[S.x][S.y] = 0;
			S.x = fish[0].x;
			S.y = fish[0].y;
			S.eat++;
			S.time += fish[0].route;
			if (S.eat == S.size_shark) {
				S.eat = 0;
				S.size_shark++;
			}
		}
		else {
			sort(fish.begin(), fish.end(), cmp);
			//cout << fish[0].route << "\n";
			shark[fish[0].x][fish[0].y] = 9;
			shark[S.x][S.y] = 0;
			S.x = fish[0].x;
			S.y = fish[0].y;
			S.time += fish[0].route;
			S.eat++;
			if (S.eat == S.size_shark) {
				S.eat = 0;
				S.size_shark++;
			}
		}
	}
}

void find_can_eat(int a, int b) {
	queue<pair<pair<int, int>, int>> q;
	check[a][b] = 1;
	q.push(make_pair(make_pair(a,b),0 ));

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int dis = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + arr[i];
			int yy = y + arr2[i];
			if (xx >= 1 && yy >= 1 && xx <= num && yy <= num) {
				if (check[xx][yy] == 0) {
					if (shark[xx][yy] == 0) {
						check[xx][yy] = 1;
						q.push(make_pair(make_pair(xx, yy), dis + 1));
					}
					else if (shark[xx][yy] < S.size_shark) {
						check[xx][yy] = 1;
						fish.push_back({ xx,yy,dis + 1 });
						q.push(make_pair(make_pair(xx, yy), dis + 1));
					}
					else if (shark[xx][yy] == S.size_shark) {
						check[xx][yy] = 1;
						q.push(make_pair(make_pair(xx, yy), dis + 1));
					}
				}
			}
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> num;
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= num; j++) {
			cin >> shark[i][j];
			if (shark[i][j] == 9) {
				S.x = i;
				S.y = j;
				S.size_shark = 2;
				S.time = 0;
				S.eat = 0;
			}
		}
	}
	solution();
	return 0;
}

 

 

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