백준 19237 - 어른 상어(C++)

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

19237번: 어른 상어

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

꽤 복잡한 구현 문제였습니다.

문제 조건

출력 예시

저는 상어 움직이기 -> 겹치는 상어 없애기 -> 냄새 없애기 -> 냄새 퍼트리기 순서로 만들었습니다.

 

 

0. 선언된 배열, vector 설명

int change_way[401][4][4];   // X번 상어의 상하좌우 이동 우선순위
/// //////////////////////////////////////////////////////
int can_move_shark[401];      // 상어의 추방 여부
sh shark[401];                // X번 상어의 정보
vector<int> now_shark[21][21];  // X번 상어가 (x , y)에 존재한다
pair<int,int> check[21][21];    // X번 상어의 냄새를 저장
int move_time;

change_way 배열의 경우 3차원 배열입니다. 

해당 배열이 하는 일은 X번 상어가 i 방향으로 움직일때, 우선순위는 (a,b,c,d) 순이다 입니다. = change_way[X][i][]

now_shark vector가 하는 값은 임의의 좌표에서 몇번 상어가 존재하는지를 저장하는 것입니다.

check 배열이 하는 값은 임의의 좌표에서 X번 상어의 냄새가 Y번 남았다는 것을 저장합니다.

 

 

1. 상어 움직이기

void move_shark(int x) {
	vector<smell> can_go;
	int x1 = shark[x].x;
	int y1 = shark[x].y;
	for (int i = 0; i < 4; i++) {
		int xx = x1 + dx[i];
		int yy = y1 + dy[i];
		if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
			if (check[xx][yy].second == 0) {
				for (int j = 0; j < 4; j++) {
					if (i == change_way[x][shark[x].way][j]) {
						can_go.push_back({ i,1,0,j });
					}	
				}
			}
			else if (check[xx][yy].second != 0) {
				if (check[xx][yy].first == x) {
					for (int j = 0; j < 4; j++) {
						if (i == change_way[x][shark[x].way][j]) {
							can_go.push_back({ i,0,1,j });
						}
					}
				}
			}
		}
	}
	sort(can_go.begin(), can_go.end(), cmp);
	int xx = x1 + dx[can_go[0].way];
	int yy = y1 + dy[can_go[0].way];
	shark[x] = { xx,yy,can_go[0].way };
	now_shark[xx][yy].push_back(x);
}

먼저 움직일 수 있는 상어일 때, 해당 함수를 실행했습니다.(can_move_shark[X]의 값이 0)

현재 좌표에서 상하좌우로 움직여봅니다. 이때 나올 수 있는 경우는 다음과 같습니다.

1. 해당 방향으로 움직였을때, 상어의 냄새가 없는 경우

2. 해당 방향으로 움직였을때, 상어의 냄새가 나는 경우, 그 상어가 자신일 경우

-> 2가지 경우가 움직일 수 있는 경우입니다.

우선 순위는 1번 경우 > 2번 경우 입니다. 

 

이 값을 vector에 저장한 뒤, 우선순위에 따라 sort를 합니다.

vector의 처음 값을 통해 다음 상어의 좌표와 방향을 저장합니다.

 

 

2. 중복된 상어 제거하기

void get_rid_of_shark() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (now_shark[i][j].size() > 1) {
				sort(now_shark[i][j].begin(), now_shark[i][j].end());
				for (int k = 1; k < now_shark[i][j].size(); k++) {
					can_move_shark[now_shark[i][j][k]] = 1;
				}
			}
			now_shark[i][j].clear();
		}
	}
}

now_shark vector는 (X , Y)에 존재하는 상어의 번호를 저장하고 있습니다.

임의의 좌표에서 size가 2이상일 경우, 2마리 이상의 상어가 존재한다는 의미이니 가장 작은 번호의 상어만 살리고 나머지를 전부 없앱니다.(can_move_shark 배열의 값을 1로 만듭니다.)

 

 

3. 1번 상어만 남았는지 확인하기

bool check_shark() {
	bool flag = true;
	for (int i = 2; i <= M; i++) {
		if (can_move_shark[i] == 0) flag = false;
	}
	return flag;
}

can_move_shark 배열에서 1번 상어만 값이 0이라면, 1번 상어만 남았다는 의미가 됩니다. 

 

 

문제 접근 방법

1. 움직일 수 있는 상어를 움직인다.

2.. (X , Y)에서 2마리 이상이 있을 경우, 정리한다.

3. 이전에 움직인 곳의 냄새를 없앤다.

4. 새롭게 냄새를 퍼트린다.

5. 1000번 이상 움직여도 답이 없는 경우 or 1번 상어만 남은 경우일때 탐색을 종료한다.

 

 

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

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

using namespace std;
//  0 - 위, 1 - 아래, 2 - 왼쪽, 3 - 오른쪽
// 우선순위 순서 = 위, 아래, 왼쪽, 오른쪽
int N, M, K;
int map[21][21];
int dx[4] = { -1,1,0,0 }; // 상하좌우
int dy[4] = { 0,0,-1,1 }; // 상하좌우
typedef struct sh {
	int x;
	int y;
	int way;
}sh;
typedef struct smell {
	int way;
	int no_other;
	int mine;
	int way_priority;      //낮을수록 우선순위가 높다
};
int change_way[401][4][4];   // X번 상어의 상하좌우 이동 우선순위
/// //////////////////////////////////////////////////////
int can_move_shark[401];      // 상어의 추방 여부
sh shark[401];                // X번 상어의 정보
vector<int> now_shark[21][21];  // X번 상어가 (x , y)에 존재한다
pair<int,int> check[21][21];    // X번 상어의 냄새를 저장
int move_time;

bool check_shark() {
	bool flag = true;
	for (int i = 2; i <= M; i++) {
		if (can_move_shark[i] == 0) flag = false;
	}
	return flag;
}

bool cmp(smell a, smell b) {
	if (a.no_other > b.no_other) return true;
	else if (a.no_other == b.no_other) {
		if (a.mine > b.mine) return true;
		else if (a.mine == b.mine) {
			if (a.way_priority < b.way_priority) return true;
			else return false;
		}
		else return false;
	}
	else return false;
}

void move_shark(int x) {
	vector<smell> can_go;
	int x1 = shark[x].x;
	int y1 = shark[x].y;
	for (int i = 0; i < 4; i++) {
		int xx = x1 + dx[i];
		int yy = y1 + dy[i];
		if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
			if (check[xx][yy].second == 0) {
				for (int j = 0; j < 4; j++) {
					if (i == change_way[x][shark[x].way][j]) {
						can_go.push_back({ i,1,0,j });
					}	
				}
			}
			else if (check[xx][yy].second != 0) {
				if (check[xx][yy].first == x) {
					for (int j = 0; j < 4; j++) {
						if (i == change_way[x][shark[x].way][j]) {
							can_go.push_back({ i,0,1,j });
						}
					}
				}
			}
		}
	}
	sort(can_go.begin(), can_go.end(), cmp);
	int xx = x1 + dx[can_go[0].way];
	int yy = y1 + dy[can_go[0].way];
	shark[x] = { xx,yy,can_go[0].way };
	now_shark[xx][yy].push_back(x);
}

void get_rid_of_shark() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (now_shark[i][j].size() > 1) {
				sort(now_shark[i][j].begin(), now_shark[i][j].end());
				for (int k = 1; k < now_shark[i][j].size(); k++) {
					can_move_shark[now_shark[i][j][k]] = 1;
				}
			}
			now_shark[i][j].clear();
		}
	}
}

void get_rid_of_smell() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (check[i][j].second > 0) {
				check[i][j].second -= 1;
				if (check[i][j].second == 0) {
					check[i][j] = { 0,0 };
				}
			}
		}
	}
}

void spread_smell() {
	for (int i = 1; i <= M; i++) {
		if (can_move_shark[i] == 0) {
			check[shark[i].x][shark[i].y] = { i,K };
		}
	}
}

void solve() {
	int ans = 0;
	while (1) {
		if (move_time > 1000) {
			ans = -1;
			break;
		}
		if (check_shark()) {
			ans = move_time;
			break;
		}
		for (int i = 1; i <= M; i++) {
			if(can_move_shark[i] == 0) move_shark(i);
		}
		get_rid_of_shark();
		get_rid_of_smell();
		spread_smell();		
		move_time++;
	}
	cout << ans;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0) {
				shark[map[i][j]] = { i,j,0 };
				check[i][j] = { map[i][j],K };
				now_shark[i][j].push_back(map[i][j]);
			}
		}
	}
	for (int i = 1; i <= M; i++) {
		cin >> shark[i].way;
		shark[i].way -= 1;
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> change_way[i][j][k];
				change_way[i][j][k] -= 1;
			}
		}
	}
	solve();
	return 0;
}

 

 

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