[백준] 19236 청소년상어
업데이트:
20년도 상반기 삼성 오전 기출 청소년상어 문제풀이입니다.
처음에 이 문제를 접했을 때 아 그냥 단순한 dfs를 활용한 구현이구나 라고 생각했습니다. 하지만 중간에 예상치 못한 실수로 인해 풀리지가 않았고… 3시간이 넘는 상황이 발생했습니다… 실수를 안했음 더 좋았지 않았을까 하는 아쉬움이 남았습니다.
제가 접근한 로직은 다음과 같습니다.
- 상어는 0,0 물고기를 먹고 그 물고기가 가지는 방향을 가진다.
- 번호가 작은 물고기 순으로 가지고 있는 방향으로 한칸 이동한다.
2-1. 상어가 있는 칸이나 벽에 부딪히면 45도 반시계방향으로 바꾼다.
2-2. 이동이 가능하다면 그 위치로 이동한다. 아니라면 2-1로 다시 돌아간 뒤 모든 방향으로 이동이 불가능하다면 움직이지 않는다.
2-3. 이동하는 위치에 물고기가 있다면 위치를 변경한다.- 상어가 가지는 방향으로 갈 수 있는 모든 위치를 구한다.
3-1. 먹을 수 있는 물고기가 있다면 그 위치로 이동한 뒤 그 물고기가 가지는 방향성을 가지고 번호를 습득한다.
3-2. 먹을 수 있는 물고기가 없다면 종료한다.- 상어가 성공적으로 움직였다면 2로 돌아가 반복한다.
말이 좀 이상하지만 얼추 순서는 이렇습니다.
제가 실수한 부분은 종료부분이였습니다. 우선 Solve함수로 들어왔다면 Result값을 갱신해줬어야 했는데 갱신전에 상어가 먹을 수 있는 물고기가 있는지 체크를 하였고 없으면 갱신하고 종료였고 있다면 갱신을 안해버려서 계속해서 오류가 생겼는데 그걸 잡는데 2시간은 걸린 것 같습니다…
소스코드는 다음과 같습니다.
Source Code :
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
typedef pair<int, int> p;
int dx[9] = {0,-1,-1,0,1,1,1,0,-1};
int dy[9] = {0,0,-1,-1,-1,0,1,1,1};
struct info {
int number;
int dir;
};
int Result = 0;
info See[4][4];
p Fish[17];
void Fish_Print() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << See[i][j].number << ' ' << See[i][j].dir << " ";
}
cout << endl;
}
cout << endl;
}
void Fish_Move() {
for (int i = 1; i < 17; i++) { // i번째 물고기 이동
if (Fish[i].first == -1) continue;
int x = Fish[i].first;
int y = Fish[i].second;
int dir = See[x][y].dir;
int nx;
int ny;
int cnt = 0;
bool chk = true;
while (1) {
if (cnt == 8) {
chk = false;
break;
}
nx = x + dx[dir];
ny = y + dy[dir];
if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4 || See[nx][ny].number == -1) {// 경계 벗어날때 또는 상어
if (dir == 8) dir = 1;
else dir++;
}
else
break;
cnt++;
}
if (!chk) continue;
int number = See[nx][ny].number;
info tmp = See[nx][ny];
See[nx][ny] = See[x][y];
See[x][y] = tmp;
See[nx][ny].dir = dir; // 45도 방향 움직여주기
if (number == 0) { // 빈 공간이라면
Fish[i] = { nx,ny };
}
else {
p ttmp = Fish[number]; // 물고기 정보 변경
Fish[number] = Fish[i];
Fish[i] = ttmp;
}
}
}
void Solve(p Shark,int Sum) {
info See_Temp[4][4];
p Fish_Temp[17];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
See_Temp[i][j] = See[i][j];
}
}
for (int i = 1; i < 17; i++) {
Fish_Temp[i] = Fish[i];
}
Fish_Move();
Result = max(Result, Sum);
p idx = Shark;
int x = idx.first;
int y = idx.second;
int dir = See[x][y].dir;
for(int i=0;i<3;i++) { // 상어가 이동할 수 있는 가능성이 있는지 확인
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) break;
if (See[nx][ny].number > 0) {// 물고기가 있을 경우만
int number = See[nx][ny].number;
int ddir = See[nx][ny].dir;
See[nx][ny].number = -1;
See[idx.first][idx.second] = { 0,0 };
Fish[number] = { -1,-1 };
p shark_idx = { nx,ny };
Solve(shark_idx, Sum + number);
See[nx][ny] = { number,ddir };
Fish[number] = { nx,ny };
}
x = nx;
y = ny;
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
See[i][j] = See_Temp[i][j];
}
}
for (int i = 1; i < 17; i++) {
Fish[i] = Fish_Temp[i];
}
}
int main() {
p Shark = { 0,0 };
for (int i = 0; i < 4; i++) {
vector<info> tmp;
for (int j = 0; j < 4; j++) {
int a, b;
cin >> a >> b;
See[i][j] = { a,b };
Fish[a] = { i,j }; // 물고기가 가지는 좌표 만약 없어졌다면 -1,-1로 이동시키기
}
}
Result += See[0][0].number;
int Dir = See[0][0].dir;
See[0][0] = { -1,Dir };
Fish[Result] = { -1,-1 };
Solve(Shark,Result);
cout << Result;
return 0;
}
Summary
- 처음 설계를 잘 하자
- 코드는 깔끔하게
- 안풀리더라도 당황하지 않고 천천히…
소스코드
이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이
댓글남기기