[BOJ-JS] 5991번 - Papaya Jungle

5991번: Papaya Jungle (acmicpc.net)

 

문제를 이해해보자면,

• n by m 격자 칸에 파파야 열매가 있다. 좌측 상단이 (1,1), 우측 하단이 (n, m).
• (1,1)에 사람이 있다. 사람은 칸에 있는 파파야를 전부 먹어치운 다음 상, 하, 좌, 우로 움직일 수 있으며, 처음 주어진 격자 칸을 벗어날 수는 없다.
• 움직일 수 있는 칸들 중 가장 많은 파파야가 있는 곳으로 이동하면서 (n, m)에 도착하면 멈춘다.

이때 중요한 조건이 두 가지가 있는데,

• 어느 순간에도 파파야가 가장 많은 칸은 유일하게 존재한다.
• 어떤 테스트 케이스에서도 (n, m)에 도달할 수 있는 것이 보장된다.

뒤의 두 조건이 더해지면서 매우 간단한 시뮬레이션 문제가 되었다!

[c,...b]=(0+require('fs').readFileSync(0)).split`
`;
[m,n]=c.split` `
a=Array(+m+2).fill(0).map(i=>Array(+n+2).fill(0))
b=b.map(i=>i.split` `)
for(i=0;i<m;i++){for(j=0;j<n;j++)a[i+1][j+1]=+b[i][j]}
r=a[1][1]
p=[1,1]
while(p[0]!=m||p[1]!=n){
  [i,j]=p;
  a[i][j]=0;
  [x,y,v]=[1,0,a[i+1][j]]
  if((w=a[i-1][j])>v)[x,y,v]=[-1,0,w]
  if((w=a[i][j+1])>v)[x,y,v]=[0,1,w]
  if((w=a[i][j-1])>v)[x,y,v]=[0,-1,w]
  r+=v;p[0]+=x;p[1]+=y
}
console.log(r)