Posts [백준] 19237번 - 어른 상어(삼성 공채)
Post
Cancel

[백준] 19237번 - 어른 상어(삼성 공채)


[백준] 19237번 - 어른 상어(삼성 공채)

[링크] https://www.acmicpc.net/problem/19237


💎 문제 조건과 설명

문제 조건과 설명은 위의 링크를 참조 부탁드립니다.


🚀 생각한 아이디어

일단 문제에서 관리해 주어야 할 변수들이 많았습니다.

1초가 흐를 때마다 상어의 위치도 옮겨야 하고, 각 칸에 냄새를 남긴 상어의 번호와 냄새값도 관리해야 합니다.

그래서 이들을 각각 다른 배열에 두고 관리하면 조금이나마 편할 것 같다고 생각하게 되었습니다.

사용한 변수

  • 상어 구조체(shark) : 상어의 y, x 좌표값, 상어가 보는 방향, 상어의 죽음 여부, 상어마다 다른 방향 우선순위 를 모두 담고 있습니다.
  • 격자판(board, 2차원 배열) : 상어가 현재 위치하고 있는 곳에 상어 번호를 적은 2차원 배열
  • 각 칸마다의 {냄새를 남긴 상어 번호, 냄새값}을 관리하는 2차원 pair 배열

구현한 함수

  • valid : 경계를 넘는지 확인하는 함수
  • remove_smell : 일괄적으로 모든 칸의 냄새를 1 감소시키는 함수. 단, 격자판에 상어가 없는 칸에 대해서만 감소를 시켰습니다.
  • moving : 죽지 않은 모든 상어들을 조건에 맞게 이동시켜 보는 함수
  • simulation : 위 함수들을 종합하여 시뮬레이션 해 보는 함수

실행 과정

  • 우선순위 이해

상어는 이동하는 방향에 따라, 우선순위가 달라집니다. 이 우선순위를 잘 이해해야 할 것 같은데, 상어가 보는 방향에 해당하는 우선순위의 방향대로 이동을 시도해야 합니다. 예를 들어 상어 1번이 다음과 같은 우선순위를 가지고 있다고 가정해 보겠습니다.

보는 방향우선 순위
↓ ← ↑ →
→ ↑ ↓ ←
← → ↓ ↑
→ ← ↑ ↓

상어 1번이 보고 있는 방향은 초기에 → 입니다.

여기에서는 보고 있는 방향이 → 일 때 우선순위가 가장 높은 방향은 → 입니다. 그러므로 →(오른쪽 칸)을 살펴봅니다.

그런데 만약 오른쪽 칸도 갈 수 없었을 경우, 그 다음 우선순위인 ← 로 보는 방향을 바꾼 뒤 왼쪽으로 가봅니다. 왼쪽으로 갈 수 있었을 경우, 상어 1번의 보는 방향은 ← (3) 으로 바뀌고 그 칸으로 위치를 바꿔줍니다.

이런 식으로 갈 수 있을 때까지 우선순위를 바꾸어 가면서 이동시켜 봅니다. 주의할 점은, 이동을 시도할 때마다 상어의 보는 방향을 계속 갱신해야 합니다.

방향의 값은 ↑, ↓, ←, → 순으로 1,2,3,4 입니다. 그래서 int dy[5] = {0, -1, 1, 0, 0}, int dx[5] = {0, 0, 0, -1, 1} 로 선언한 다음 예를 들어 방향값이 1일 경우 dy[1], dx[1] 을 참조하도록 하였습니다.

  • 상어를 쫒아내고 냄새를 남기기

각 상어들은 보는 방향에 따라 빈 칸을 찾아서 이동할 것입니다. 이 때 이동하려는 칸이 1. 냄새는 없었는데 2. 상어가 있었을 경우, 그 칸에 있던 상어의 번호와 현재 이동 중인 상어의 번호를 비교한 다음, 번호가 더 큰 상어를 죽음 상태로 만듭니다. (isDead = true)

즉, 먼저 1번부터 M번까지의 모든 죽지 않은 상어를 차례대로 이동시켜 보면서 그 과정에 다른 상어가 있었으면 위처럼 비교하고 처리하면 됩니다. 그리고 상어의 이동이 모두 끝난 다음에, 상어가 위치한 칸의 냄새값을 갱신시킵니다.

  • 마지막으로 냄새값을 일괄 감소

이동과 냄새 남기기가 모두 끝난 뒤에, 상어가 없는 칸의 냄새를 일괄적으로 1 감소시킵니다.

여기까지 하면 1초가 흐릅니다. 이를 계속 반복하면 됩니다. 반복할 때마다 격자판에 1번 상어만 있는지 확인해 주어야 하며, 1000초가 지나면 -1을 반환합니다.


  • 소스코드 : 주석으로 최대한 자세히 써 놓았으니 참고해 주세요!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

int board[21][21]; // 격자판
pair<int, int> smell[21][21]; // 각 칸의 {상어번호, 냄새} 관리

typedef struct shark {
	int isDead;
	int dir;
	int y;
	int x;
	int rank[5][4];
}Shark;

Shark shark[401];
int N, M, k; // N은 격자 크기, M은 상어 수, k는 상어가 k번 이동하고 나면 사라지는 수

bool valid(int y, int x) {
	if (y < 0 || x < 0 || y >= N || x >= N) 
		return false;	
	return true;
}

// 일괄적으로 모든 칸의 냄새를 1 감소시키는 함수
void remove_smell() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 0 && smell[i][j].second > 0) {
				smell[i][j].second -= 1;

				if (smell[i][j].second == 0) {
					smell[i][j].first = 0;
				}
			}
		}
	}
}

// 모든 상어를 움직이는 함수
void moving() {
	// 1. 기본적으로 상어는 상,하,좌,우 중 인접한 칸으로 이동한다. 
	// 단, 보는 방향을 기준으로 아무 냄새가 없는 칸으로 이동한다.
	// 2. 상,하,좌,우 다 우선순위대로 둘러보면서 냄새가 없는 칸이 없었으면
	// 상,하,좌,우 중 자기 냄새가 있던 칸으로 이동한다.

	// 모든 상어에 대해서 이동시키기
	// 이 모든 과정을 진행하는 데 1초 소요된다고 가정
	for (int i = 1; i <= M; i++) {
		int dir = shark[i].dir; // i번 상어의 방향
		int y = shark[i].y;
		int x = shark[i].x;

		bool isFind = false;

		// 죽지 않은 상어들에 대해서만 진행
		if (shark[i].isDead == false) {
			// 보는 방향 기준 4가지 우선순위로 인접한 칸을 살펴본다.
			for (int j = 0; j < 4; j++) {
				int f_dir = shark[i].rank[dir][j]; // 보는 방향인 dir 기준 우선순위
				int ty = y + dy[f_dir];
				int tx = x + dx[f_dir];

				// 경계를 벗어나지 않았을 경우 && 냄새가 없었을 경우
				if (valid(ty, tx) && smell[ty][tx].second == 0) {
					// 아직 그 칸에 냄새는 새기지 말고, 그 자리에 상어를 이동시켜 본다.
					// 그 이유는 이 자리에 또다른 상어가 이동해서 올 수 있으므로

					// 다른 상어가 이동해 있을 경우, 상어 번호를 비교한다.
					if (board[ty][tx] != 0) {

						// 가고자 했던 자리의 상어보다 내 번호가 작을 경우
						// 내가 그 자리를 치고 들어간다.
						// 그리고 원래 그 자리에 있던 상어는 없애버린다.
						if (board[ty][tx] > i) {
							board[y][x] = 0; // 이동 전은 빈 칸으로 바꿈

							board[ty][tx] = i;
							shark[i].y = ty;
							shark[i].x = tx;
							shark[board[ty][tx]].isDead = true;
							isFind = true;

							// 이동한 상어의 보는 방향을 바꾼다.
							shark[i].dir = f_dir;
						}

						// 가고자 했던 자리의 상어보다 내 번호가 클 경우
						// 상어 나 자신을 죽게 한다.
						else if (board[ty][tx] < i) {
							board[y][x] = 0;
							shark[i].isDead = true;
							isFind = true;
							break;
						}
					}

					// 가려고 하는 칸에 아무 상어도 없었을 경우
					else {
						board[y][x] = 0; // 이동 전은 빈 칸으로 바꿈
						board[ty][tx] = i;
						shark[i].y = ty;
						shark[i].x = tx;
						isFind = true;

						// 이동한 상어의 보는 방향을 바꾼다.
						shark[i].dir = f_dir;
					}

					break; // 이동을 했으므로 다음 상어로 넘어간다.
				}
			}


			// 상,하,좌,우 모두 빈 칸은 없었을 경우, i번 상어 자신의 냄새가 있는 곳으로 이동
			if (!isFind) {
				// 자신의 냄새가 있는 곳을 다시 찾는다.
				for (int j = 0; j < 4; j++) {
					int f_dir = shark[i].rank[dir][j]; // 보는 방향 기준 우선순위
					int ty = y + dy[f_dir];
					int tx = x + dx[f_dir];

					// 자신의 번호와 같을 경우
					if (valid(ty, tx) && smell[ty][tx].first == i) {
						board[y][x] = 0; // 이동 전은 빈 칸으로 바꿈
						board[ty][tx] = i;
						shark[i].y = ty;
						shark[i].x = tx;

						// 이동한 상어의 보는 방향을 바꾼다.
						shark[i].dir = f_dir;
						break;
					}
				}
			}
		}
	}

	// 이동이 모두 끝났으면, 새로 이동한 상어가 있는 지점에 냄새를 남긴다.
	for (int i = 1; i <= M; i++) {
		// 죽지 않은 상어들에 대해서만 시행한다.
		if (shark[i].isDead == false) {
			int y = shark[i].y;
			int x = shark[i].x;

			smell[y][x].first = i;
			smell[y][x].second = k;
		}
	}
}

int simulation() {

	int time = 0; // 0초에 시작

	while (time <= 1000) {
		// 격자에 1번 상어만 있는지 확인
		bool flag = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] != 0 && board[i][j] != 1) {
					flag = true; // 다른게 있다
					break;
				}
			}
		}
		if (!flag) break;

		// 상어를 이동시키고, 냄새를 남긴다.
		moving();

		// 상어가 없는 곳의 모든 냄새 1씩 제거	
		remove_smell();

		// 여기까지가 1초 경과
		time += 1;	
	}

	if (time > 1000)
		return -1;
    
	return time;
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> k;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] != 0) {
				shark[board[i][j]].y = i;
				shark[board[i][j]].x = j;
			}
		}
	}

	// 각 상어의 초기 방향	
	for (int i = 1; i <= M; i++) {
		int input;
		cin >> input;
		shark[i].dir = input;
	}

	// 상어의 번호는 1번부터
	for (int i = 1; i <= M; i++) {
		for (int k = 1; k <= 4; k++) {
			for (int j = 0; j < 4; j++) {
				cin >> shark[i].rank[k][j];
			}
		}
	}

	// 초기에 상어가 주어졌을 때 냄새가 있다고 가정
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] != 0) {
				smell[i][j] = make_pair(board[i][j], k);
			}
		}
	}

	int res = simulation();
	cout << res;

	return 0;
}