[19236번 청소년 상어] - C++
[19236번 청소년 상어]
https://www.acmicpc.net/problem/19236
[19237번 어른 상어]
https://www.acmicpc.net/problem/19237
https://velog.io/@statco19/boj-19237
[16236번 아기 상어]
https://www.acmicpc.net/problem/16236
https://velog.io/@statco19/boj-16236
아기 - 청소년 - 어른 상어로 이어지는 시리즈 중 중간에 있는 문제이다. 체감 난이도는 청소년 상어가 가장 까다로웠다.
일단 상어가 먹을 수 있는 물고기 크기의 최대값을 구해야 하기 때문에 가능한 모든 경우를 백트래킹으로 살펴봐야 한다. 그 점에서 DFS 알고리즘을 사용해야 함을 알 수 있었다. 그리고 2차원 배열의 크기가 4*4인 점을 보면 DFS를 사용해도 시간초과가 나지 않을 만큼 연산이 많지 않을 것을 알 수 있었다.
풀이
물고기의 크기를 2차원 배열 size_
에 넣어주었고, 물고기의 방향을 2차원 배열 dir
에 넣어주었다.
void dfs(int r, int c, int score) {
// 상어를 (0,0)에 넣어주고 (0,0)에 있던 물고기 먹고 score에 크기 더해줌
// 물고기 이동
// 상어가 바라보는 방향에 물고기가 더 이상 없으면,
// 갈 곳이 없으므로 종료
if(sharkGoesHome(r,c,d)) {
ans = max(ans, score);
return;
}
// 상어가 바라보는 방향에 물고기가 있다면, 잡아먹으러 이동
// 잡아먹으러 가는 물고기의 위치를 (R,C)라고 하면
dfs(R,C,score);
return;
}
핵심이 되는 수도코드 부분을 이렇게 짜고 중간중간에 추가적인 메서드를 구현했다. 주의할 점은 상어가 물고기가 없는 칸을 발견하자마자 집으로 가는 것이 아닌 자기가 바라보는 방향에서 끝까지 한 마리도 물고기가 존재하지 않아야 집으로 돌아가도록 구현해야 한다.
C++ 코드
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility> // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;
int ans = 0;
int size_[4][4];
int dir[4][4];
int dr[] = {0,-1,-1,0,1,1,1,0,-1};
int dc[] = {0,0,-1,-1,-1,0,1,1,1};
int sharkR;
int sharkC;
int sharkGoesHome(int r, int c, int d) {
int nr,nc;
nr = r+dr[d];
nc = c+dc[d];
while(0<=nr&&nr<4 && 0<=nc&&nc<4) {
if(size_[nr][nc] > 0) { // fish exist
return 0;
}
nr += dr[d];
nc += dc[d];
}
return 1;
}
void move(int r, int c, int d) {
int nd,nr,nc;
for(int i=0;i<8;++i) {
nd = (d-1+i)%8 + 1;
nr = r+dr[nd];
nc = c+dc[nd];
if(0<=nr&&nr<4 && 0<=nc&&nc<4) {
if(nr==sharkR && nc==sharkC) { // shark
continue;
} else {
if(size_[nr][nc] > 0) { // fish
dir[r][c] = nd;
int tempSize = size_[nr][nc];
int tempDir = dir[nr][nc];
size_[nr][nc] = size_[r][c];
dir[nr][nc] = dir[r][c];
size_[r][c] = tempSize;
dir[r][c] = tempDir;
return;
} else if(size_[nr][nc]==0) { // empty
dir[r][c] = nd;
size_[nr][nc] = size_[r][c];
dir[nr][nc] = dir[r][c];
size_[r][c] = 0;
dir[r][c] = 0;
return;
}
}
}
}
return;
}
void moveFish() {
int num = 1;
while(num<=16) {
int found = 0;
for(int i=0;i<4;++i) {
for(int j=0;j<4;++j) {
if(size_[i][j] == num) {
int d = dir[i][j];
move(i,j,d);
found = 1;
break;
}
}
if(found) break;
}
num++;
}
return;
}
void dfs(int r, int c,int score) {
sharkR = r; sharkC = c;
score += size_[r][c];
size_[r][c] = 0;
int d = dir[r][c];
dir[r][c] = 0;
moveFish();
if(sharkGoesHome(r,c,d)) {
ans = max(ans, score);
return;
}
int size__cpy[4][4];
int dir_cpy[4][4];
copy(&size_[0][0], &size_[0][0]+16, &size__cpy[0][0]);
copy(&dir[0][0], &dir[0][0]+16, &dir_cpy[0][0]);
int nr,nc;
nr = r+dr[d];
nc = c+dc[d];
while(0<=nr&&nr<4 && 0<=nc&&nc<4) {
if(size_[nr][nc] > 0) { // fish exist
size_[r][c] = 0; // shark leaves
dfs(nr,nc,score);
sharkR = r; sharkC = c;
copy(&size__cpy[0][0], &size__cpy[0][0]+16, &size_[0][0]);
copy(&dir_cpy[0][0], &dir_cpy[0][0]+16, &dir[0][0]);
}
nr += dr[d];
nc += dc[d];
}
return;
}
int main(void) {
// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
for(int i=0;i<4;++i) {
for(int j=0;j<4;++j) {
scanf("%d%d", &size_[i][j], &dir[i][j]);
}
}
dfs(0,0,0);
printf("%d\n", ans);
return 0;
}
실행 결과
Author And Source
이 문제에 관하여([19236번 청소년 상어] - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@statco19/boj-19236저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)