19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
1. 풀이방법
- 사실 풀이방법은 딱히 없습니다...
- 문제에서 원하는 조건 그대로를 구현해내면되고, 사용되는 알고리즘 또한 별로 없는 것 같다.
- 조건을 한단계씩 맞춰나가면서 스텝 바이 스텝으로 짜면 되는데,,,,,,,, 코드가 매우 길어집니다.. 저만 그런건지.....
2. 주의사항
- *** 처음에 문제를 천천히 파악하고 문제의 조건들을 충분히 담을 수 있을만한 자료구조와 변수 선언에 신경써야합니다.짜다 보니 이 변수들로만 모든걸 체크하기 부족해서 추가적으로 임의로 선언할 경우 코드가 길어지면서 실수할 가능성이 높은 것 같습니다.
그래서 이 과정에 꽤 많은 시간을 소모해도 된다고 생각합니다.
- 단계,단계 차례대로 천천히 구현해 나갈 것
- 저 같은 경우 마지막에 다 짰는데도 틀렸습니다가 떠서 봤더니...
비슷한 변수이름을 두개 (sharkdir, sharkdir) 을 선언해서 썼더니 코드가 길어지면서 저도 모르게 이를 실수 했습니다.
왠만하면 변수이름은 잘 구별될 수 있도록 선언하는 것이 좋을 것 같습니다.
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
bool sharkdie[401];
vector<int> sharkdir;
pair<int, int> sharks[401]; //현재 상어들의 위치 (x,y)
vector<pair<int, int>> sea[21][21]; //first= 상어번호, second= 남은 k
int dirinfo[401][4][4];
int tmpint;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
//위.아래,왼쪽,오른쪽
void inputs() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> tmpint;
if (tmpint != 0) {
sharks[tmpint].first = i; sharks[tmpint].second = j;
}
}
}
sharkdir.push_back(-1); // 인덱스 맞추기 용
for (int i = 0; i < m; i++) {
cin >> tmpint; sharkdir.push_back(tmpint-1);
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
cin >> tmpint;
dirinfo[i][j][k]=tmpint-1;
}
}
}
}
bool boundcheck(int x, int y) {
return (x >= 0 && y >= 0 && x < n&& y < n);
}
bool checksharks() {
for (int i = 2; i <= m; i++) {
if (sharkdie[i] == false) return false;
}
return true; //1번 상어 빼고 다 쫓겨남
}
int main() {
inputs();
int resultsecond=0;
while (1) {
if (resultsecond > 1000) { cout << -1; break; }
if (checksharks()) { cout << resultsecond; break; }
//냄새 k 감소
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!sea[i][j].empty()) {
sea[i][j][0].second--;
if (sea[i][j][0].second == 0) {
sea[i][j].clear();
}
}
}
}
//냄새 뿌리기
for (int i = 1; i <= m; i++) {
if (sharkdie[i] == false) { //쫓겨나지 않았다면 냄새 뿌린다.
sea[sharks[i].first][sharks[i].second].clear();
sea[sharks[i].first][sharks[i].second].push_back({ i,k });
}
}
//이동하기
for (int i = 1; i <= m; i++) { //상어 한마리씩 본다.
if (sharkdie[i] == true) continue;
bool suc = false;
// 냄새가 없는 칸이 있는지 먼저본다.
for (int j = 0; j < 4; j++) {
int nextx = sharks[i].first + dx[dirinfo[i][sharkdir[i]][j]];
int nexty = sharks[i].second + dy[dirinfo[i][sharkdir[i]][j]];
if (boundcheck(nextx, nexty) && sea[nextx][nexty].empty()) { //냄새가 없는 칸
sharks[i].first = nextx;
sharks[i].second = nexty;
suc = true;
sharkdir[i] = dirinfo[i][sharkdir[i]][j]; //이동한 방향이 보고있는 방향이 된다.
break;
}
}
if (suc == false) {
for (int j = 0; j < 4; j++) {
int nextx = sharks[i].first + dx[dirinfo[i][sharkdir[i]][j]];
int nexty = sharks[i].second + dy[dirinfo[i][sharkdir[i]][j]];
if (boundcheck(nextx, nexty) && sea[nextx][nexty][0].first == i) { //자신의 냄새가 있는 칸
sharks[i].first = nextx;
sharks[i].second = nexty;
suc = true;
sharkdir[i] = dirinfo[i][sharkdir[i]][j]; //이동한 방향이 보고있는 방향이 된다.
break;
}
}
}
}
// 겹치는 상어 쫓아내기
for (int i = 1; i <= m; i++) {
if (sharkdie[i] == true) continue;
for (int j = i + 1; j <= m; j++) {
if (sharkdie[j] == true) continue;
if (sharks[i].first == sharks[j].first && sharks[i].second == sharks[j].second) { // 겹쳐진 상어가 생기면
sharkdie[j] = true; // 쫓겨난다 (번호가 늦는 놈이)
}
}
}
resultsecond++;
}
return 0;
}'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
| 백준 16235 [C++] (0) | 2021.03.06 |
|---|---|
| 백준 17779 [C++] (0) | 2021.03.05 |
| 백준 17140 [C++] (0) | 2021.01.24 |
| 백준 2726 [C++] (0) | 2021.01.16 |
| 백준 10993 [C++] (0) | 2021.01.16 |