백준 문제 19236번 청소년 상어 문제풀이 c++
https://www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
문제해석
예전에 이 문제를 처음 봤을때 생각 났었던 아이디어는 백트래킹이 떠오르긴했는데 막상 직접 구현을 하기에 빡세게 느껴졌어서 언젠가 풀어야지하고 미루다가 얼마 전에 풀게 되었다.
실제로 백트래킹을 이용한 깡구현 문제인데 아이디어는 이렇다.
먼저 4x4 공간이기 때문에 상어의 현재 위치와 방향에 따라서 물고기를 최소 0개에서 최대 3개를 먹게 되는경우가 생긴다는걸 알 수있다.
그렇기 때문에 먹을 수 있는 모든 물고기에 대해서 전부 먹어보아야 답을 알수 있기 때문에 현재 공간을 백업 해두고 종료가 되면 뒤로 back하여 저장되었던 공간을 recover함이 필요하다고 생각했다.
예를 들어 <그림2>를 보자
현재 상어의 위치가 0,0이고 방향이 오른쪽 아래를 향하고 있는데 이 때 상어가 먹을 수 있는 물고기는 1번 4번 12번이 된다.
그렇다면 1번을 먹고 진행하다가 종료 시점이 나오면 back을 한다.
그러다 보면 어느 시점에 다시 <그림2>상태를 recover 하는 시점이 온다.
그럼 이때는 1번을 먹은 경우는 모두 해보았으므로 4번 물고기를 먹고 진행하다가 종료 시점이 나오면 back을 한다.
그러다 보면 어느 시점에 다시 <그림2>상태를 recover 하는 시점이 온다.
1번과 4번 물고기를 먹는 경우는 모두 해보았으므로 이번엔 12번을 먹어서 위와 같은 방식으로 작동하게 된다.
그렇다면 현재 상태를 저장하는 4x4배열이 있고 물고기는 시작할때 16마리가 존재하므로 깊이는 최대 16이 될 것이기 때문에 4x4배열 16개가 필요하다.
혹시 몰라 넉넉하게 4x4 배열 20개를 선언했다.(before 배열)
밑의 코드에 보면 함수가 총 7개중 back_up 함수와 recover 함수가 있는데
위에서 설명했듯이 필요한 시점에 before 배열에 백업 before배열로부터 recover를 받는 함수이다.
그렇다면 필요한 시점이 어딘지를 알아야하는데 이 문제는 백트래킹 문제이다.
따라서 백트래킹 함수역시 작성 하였는데 이름이 dfs 함수이고 인자로 상어가 향하는 방향 상어의 위치 깊이가 인자로 주어진다.
먼저 문제에서 하란대로 순서를
1. 상어가 물고기를 잡아먹는다.
2. 물고기들이 서로 움직이면서 위치를 바꾼다
3. 상어가 다음에 먹을 수 있는 물고기가 하나 이상 존재하면 4번스텝으로 가고 그렇지 않으면 종료한다.
4. 이 부분에 백트래킹을 구현한다.
기본적인 순서는 1->2->3->4로 가는데
먼저 back_up 함수는 백트래킹 하기전 3번과 4번사이에 호출을 해야하고
recover 함수는 4번에 백트래킹 구현의 끝 부분에 호출 해야한다.
그렇다면 이제 남은 eat,move,inside,check 함수에 대해 설명해보자면
eat함수는 1번과정에서 상어가 물고기를 잡아먹는 함수이다.
move함수는 2번과정에서 물고기들이 서로 위치를 바꾸어 움직이는 함수이다.
inside함수는 공간의 범위를 벗어나는지 확인하는 bool 타입함수이고
check함수는 상어가 먹을 수 있는 물고기가 존재 하는가?를 확인하는 bool 타입함수이다.
eat함수는 int 타입함수인데 상어가 먹을 물고기를 정하면 그 물고기의 위치가 인자로 들어와서 그 물고기를 먹고 먹은 물고기가 가진 방향을 리턴하는 함수로 작성했다.
맨처음 상어는 0,0을 먹어야하니까 최초엔 eat(0,0)을 하면된다.
move 함수에서 상어의 위치가 인자로 들어오고 물고기는 숫자가 작은 게 먼저 움직이는데 애초에 입력으로 받을때 물고기의 위치를 받아놓아서 1번부터 16번까지 반복문을 돌려주었다.
이러면 당연히 작은 물고기 부터 움직이게 된다.
만약 물고기가 상어에게 먹혀서 존재 하지않는다면 continue하면된다.
그리고 문제의 조건에 맞게 물고기가 향하는 방향이 공간을 벗어나거나 상어가 존재하면 방향을 45도 바꾸고 그렇지 않으면 두 물고기의 위치를 서로 바꾸게 작성한다.
int dy[8]={-1,-1,0,1,1,1,0,-1};
int dx[8]={0,-1,-1,-1,0,1,1,1};
반시계 45도씩 돌려주어야 하기 때문에 dy dx 전역 배열을 이렇게 작성하였다.
주의 할 것이 있는데 만약에 8바퀴를 돌아 원래 상태로 돌았다면 그 물고기는 어떤 방향으로도 이동 불가 이므로 break 포인트를 걸어주어야한다.
만약 break문을 작성안하면 아마 물고기는 영원히 방향을 바꾸게 될 것이다.
개인적으로 move함수가 가장 중요한 함수 같아서 이 부분을 좀 더 유심히 작성한거 같다.
만약 이 부분에 실수가있어서 틀렸다면 어디가 틀린지 확인해야 하는데 이 문제 move수행을 시각적으로 추척하기가 매우 힘든 문제다 즉 디버그가 너무 빡셀거 같다는것을 직감적으로 느꼈다.
inside 함수는 생략
check 함수는 상어의 위치와 방향이 주어지면 다음에 물고기를 하나라도 먹을 수있는가를 판단해야하는데
현재 상어의 위치에서 상어가 가진 방향으로 1칸부터 최대 3칸까지만 확인하여 물고기가 존재하는지만 보면된다.
왜냐면 4x4의 공간이기 때문이다.
아 그리고 물고기의 번호와 방향이 같이 존재하기때문에 일반 int 배열이 아니라 int , int를 쌍으로 묶은 pair 배열을 사용하였다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void back_up(int depth);
void recover(int depth);
int eat(int ny,int nx);
void move(int shark_i,int shark_j);
void dfs(int cd,int cy,int cx,int depth);
bool check(int cd,int cy,int cx);
bool inside(int ny,int nx);
int dy[8]={-1,-1,0,1,1,1,0,-1};
int dx[8]={0,-1,-1,-1,0,1,1,1};
pair <int,int> location[17];
pair <int,int> p[4][4];
pair <int,int> before[20][4][4];
int sum=0; int ans=0;
int main(){
cout.tie(NULL);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
for(int i=0; i<4; i++)
{
for(int j=0; j<4; j++)
{
cin>>p[i][j].first>>p[i][j].second;
p[i][j].second=p[i][j].second-1;
location[p[i][j].first].first=i;
location[p[i][j].first].second=j;
}
}
sum=sum+p[0][0].first;
dfs(eat(0,0),0,0,0);
cout<<ans;
}
void back_up(int depth){
for(int i=0; i<4; i++)
{
for(int j=0; j<4; j++)
{
before[depth][i][j]=p[i][j];
}
}
}
void recover(int depth){
for(int i=0; i<4; i++)
{
for(int j=0; j<4; j++)
{
p[i][j]=before[depth][i][j];
}
}
for(int i=0; i<4; i++)
{
for(int j=0; j<4; j++)
{
location[p[i][j].first].first=i;
location[p[i][j].first].second=j;
}
}
}
int eat(int ny,int nx){
location[p[ny][nx].first].first=-1;
location[p[ny][nx].first].second=-1;
p[ny][nx].first=0;
return p[ny][nx].second;
}
void move(int shark_i,int shark_j){
for(int i=1; i<=16; i++)
{
int cnt=0;
if(location[i].first==-1&&location[i].second==-1)
{
continue;
}
else
{
int cy=location[i].first;
int cx=location[i].second;
for(int j=0; j<8; j++)
{
if(cnt==8)
{
p[cy][cx].second=(p[cy][cx].second+1)%8;
break;
}
int ny=cy+dy[j];
int nx=cx+dx[j];
int direction=p[cy][cx].second;
if(direction==j)
{
if(inside(ny,nx))
{
if(ny==shark_i&&nx==shark_j)
{
p[cy][cx].second=(p[cy][cx].second+1)%8;
cnt++;
j=-1;
}
else
{
pair <int,int> tmp=p[cy][cx];
pair <int,int> tmp_l=location[i];
int x=p[ny][nx].first;
p[cy][cx]=p[ny][nx];
location[i].first=ny; location[i].second=nx;
p[ny][nx]=tmp;
location[x]=tmp_l;
break;
}
}
else
{
p[cy][cx].second=(p[cy][cx].second+1)%8;
cnt++;
j=-1;
}
}
}
}
}
}
void dfs(int cd,int cy,int cx,int depth){
move(cy,cx);
if(check(cd,cy,cx)==false)
{
ans=max(ans,sum);
return;
}
back_up(depth);
for(int i=1; i<=3; i++)
{
int ny=cy+i*dy[cd];
int nx=cx+i*dx[cd];
if(inside(ny,nx)&&p[ny][nx].first>0)
{
int x=p[ny][nx].first;
sum=sum+x;
dfs(eat(ny,nx),ny,nx,depth+1);
sum=sum-x;
recover(depth);
}
}
}
bool check(int cd,int cy,int cx){
for(int i=1; i<=3; i++)
{
int ny=cy+i*dy[cd];
int nx=cx+i*dx[cd];
if(inside(ny,nx)&&p[ny][nx].first)
{
return true;
}
}
return false;
}
bool inside(int ny,int nx){
if(0<=ny&&ny<4&&0<=nx&&nx<4)
{
return true;
}
else
{
return false;
}
}
대충 작성하는데만 1시간 30분걸렸고 예제 출력이 이상해서 그것 찾는데에 1시간 30분이 걸린 문제였다.
찾고 보니까 단순오타였음에 화가났지만 그래도 다행이 한번에 맞았다.
그런데 집에서 풀어서 이렇게 오래걸리면 실제로는 풀 수있을지가 고민이다.