문제
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
시간 제한: 2초
메모리 제한: 512MB
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
입력
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
출력
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
예제 입출력
| 예제 번호 | 입력 | 출력 |
| 1 | 3 0 0 0 0 0 0 0 9 0 |
0 |
| 2 | 3 0 0 1 0 0 0 0 9 0 |
3 |
| 3 | 4 4 3 2 1 0 0 0 0 0 0 9 0 1 2 3 4 |
14 |
| 4 | 6 5 4 3 2 3 4 4 3 2 3 4 5 3 2 9 5 6 6 2 1 2 3 4 5 3 2 1 6 5 4 6 6 6 6 6 6 |
60 |
| 5 | 6 6 0 6 0 6 1 0 0 0 0 0 2 2 3 4 5 6 6 0 0 0 0 0 2 0 2 0 0 0 0 3 9 3 0 0 1 |
48 |
| 6 | 6 1 1 1 1 1 1 2 2 6 2 2 3 2 2 5 2 2 3 2 2 2 4 6 3 0 0 0 0 0 6 0 0 0 0 0 9 |
39 |
Ⅰ문제 분석하기
(본 문제 분석은 예시입출력 3번을 기준으로 작성되었습니다.)
아기 상어가 이동 가능한 경우: 자신보다 작거나 같은 경우
아기 상어가 먹기 가능한 경우: 자신보다 작은 경우
- 먹을 수 있는 물고기가 한마리보다 많다면 거리가 가장 가까운 물고기
- 같은 거리의 물고기라면 가장 위쪽 물고기
- 같은 거리, 같은 행이라면 가장 왼쪽 물고기
관리해야하는 변수
1. 아기 상어의 위치(Y, X)와 크기
2. 아기 상어가 잡아먹은 물고기 개수 CNT
3. 이동시간=이동거리=답 ANS
| 4 | 3 | 2 | 1 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 9 시작 위치 |
0 |
| 1 | 2 | 3 | 4 |
시작 크기가 2이기 때문에 1인 크기인 물고기만 먹기 가능하다.
따라서 가장 상단 우측과 가장 하단 좌측의 붉게 표시된 부분으로 이동이 가능하며
두 물고기 다 위치는 3이기 때문에, 위쪽 물고기인 우측상단 물고기로 가야한다.
| 4 | 3 | 2 | 상어 이동 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 |
아기 상어의 위치: (0,3)
아기 상어의 크기: 2
아기 상어가 잡아먹은 물고기 개수 CNT: 1
이동시간=거리: 3
| 4 | 3 | 2 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 상어 이동 | 2 | 3 | 4 |
아기 상어의 위치: (3,0)
아기 상어의 크기: 2
아기 상어가 잡아먹은 물고기 개수 CNT: 2
=> 아기 상어 크기 증가
아기 상어의 크기: 3
아기 상어가 잡아먹은 물고기 개수 CNT: 0
이동시간 = 거리: 3 + 6 = 9
| 4 | 3 | 2 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 상어 이동 | 2 | 3 | 4 |
전체 맵을 탐색하여 잡아먹을 수 있는 물고기를 탐색. 붉은색으로 표시된 두 곳으로 이동가능하나
가장 거리가 가까운 우측 물고기로 이동한다.
| 4 | 3 | 2 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 상어 이동 |
3 | 4 |
아기 상어 위치: (3,1)
아기 상어 크기: 3
아기 상어가 잡아먹은 물고개 개수: 1
이동 시간 = 거리: 9+1=10
| 4 | 3 | 2 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 상어 이동 |
3 | 4 |
전체 맵을 탐색하여 잡아먹을 수 있는 물고기를 탐색.
| 4 | 3 | 상어 이동 |
0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 3 | 4 |
아기 상어 위치: (0,2)
아기 상어 크기: 3
아기 상어가 잡아먹은 물고개 개수: 2
이동 시간 = 거리: 10+4 = 14
| 4 | 3 | 상어 위치 |
0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 3 | 4 |
현재 아기 상어의 크기가 3이기 때문에 더이상 먹을 수 있는 물고기가 없다.
따라서 로직을 종료하고 답을 출력한다.
이동 시간 = 이동 거리 = 답 : 14
Ⅱ 슈도코드 작성하기
/*
* 작성자, 1.0, 202Y.MM.YY 누Ring <dierdia@naver.com>
*
* BAEKJOON 골드3 16236 아기 상어
* 문제 링크: https://www.acmicpc.net/problem/16236
* 작성 언어: Pseudo-code
*/
class POINT 선언
{
int y, x, dis
Point(int y, int x, int dis)
{
this 로 사용할 수 있도록 구성
}
}
--------------------------------------
MAIN 문
{
[변수선언] 변수 n 입력
[변수선언] 배열 arr
[변수선언] 배열 아기상어 y좌표, x좌표, size, (현 사이즈에서의 먹은 수)cnt
for(i=0; i<n; i++)
{
for(i=0; i<n; i++)
{
[배열입력] arr[i][j]
if(arr[i][j]==9)
{
[배열입력] 아기상어
}
}
}
[변수선언] Point movept // 현재 아기상어의 위치
[변수선언] int ans=0
[배열선언] dy dx 상하좌우 움직이도록 배열
while(true)
{
[배열선언] boolean visited[n][n]
[큐 선언] Queue<Point>q
[큐 초기 삽입] q.offer(new Point(y, x, 0))
visited[y][x] 방문처리
movept.dis=Integer.MAX_VALUE // 이동할 거리 중 가장 짧은 거리를 구해야하기 때문
while(!q.ieEmpty)
{
① 코딩순서
[변수선언] Point tmp = q.offer();
③ 코딩순서
if(tmp.dis<movept.dis)
{
break;
}
if(물고기가 있고 물고기 사이즈가 작아 먹을 수 있으면)
{
if(tmp.dis<movept.dis)
{
movept=tmp //이번위치=옮길 위치(후보)
//현재위치가 거리가 가장 가까운 물고기가 있는 곳이긴 하지만
//같은거리의 다른 위치에 있을 수 있음으로
}
else if(tmp.dis==movept.dis)
{
if(tmp.y<movept.y) // 지금위치가 이전 같은거리 물고기가 있는 위치보다 위라면
{
movept=tmp // 이번위치=옮길 위치
}
else if(tmp.y==movept.y&&tmp.x<movept.x)//y위치가 같다면 왼쪽에 있는지 비교
{
movept=tmp;
}
}
continue;
}
② 코딩순서
for(int i=0;i<4)
{
int ny= tmp.y+dy[i]
int nx= tmp.x+dy[i]
if(arr범위 벗어나지 않는다면)
{
if(visited 방문하지않고 상어의 크기와 작거나 같아서 이동가능한 경우)
{
ny, nx 방문처리
q.offer(new Point(ny,nx,tmp.dis+1))
}
}
}
④ 코딩순서
if(movept.dis!=MAXVALUE)
{
ans+=movept.dis
아기상어가 먹은 물고기 개수 ++
if(아기상어가 이번 사이즈에 먹은 개수 == 아기상어 크기)
{
먹은 개수 = 0
크기 ++
}
arr[y좌표][x좌표] = 0
}
else // movept가 없기 때문에 더이상 먹을 수 있는 물고기가 없음
{
break;
}
[출력] ans 출력
}
}
}
Ⅲ 코드 구현 ( 구현 언어: JAVA )
/*
* 작성자, 1.0, 202Y.MM.YY 누Ring <dierdia@naver.com>
*
* BAEKJOON 골드3 16236 아기상어
* 문제 링크: https://www.acmicpc.net/problem/16236
* 작성 언어: JAVA
*/
import java.util.*;
import java.io.*;
public class Main{
public static int n;
public static int[][]arr;
public static int[]baby;
public static int[]dy= {-1,1,0,0}; //상하좌우 이동
public static int[]dx= {0,0,-1,1}; //상하좌우 이동
public static int[][]dist;
static class Point{
int y;
int x;
int dis;
Point(int y, int x, int dis)
{
this.y=y;
this.x=x;
this.dis=dis;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine()); // 배열 크기 입력
arr=new int [n][n]; // 배열 선언
baby=new int[4]; // 아기상어의 정보 저장용 배열, Y위치, X위치, 크기, 해당 크기에서 먹은 물고기 마리수
StringTokenizer st;
for(int i=0;i<n;i++)
{
st=new StringTokenizer(br.readLine());
for(int j=0;j<n;j++)
{
arr[i][j]=Integer.parseInt(st.nextToken());
if(arr[i][j]==9)
{
arr[i][j]=0;
baby[0]=i;//최초 상어 Y위치
baby[1]=j;//최초 상어 X위치
baby[2]=2;//최초 상어 크기
}
}
}
Point movept = new Point(baby[0], baby[1], 0);
//아기 상어가 이동할 장소
//최초 시작 시 현재 거리를 넣고 거리를 0으로 지정
int ans=0;
while(true) {
boolean visited[][]=new boolean[n][n];
Queue<Point> q = new LinkedList<>();
visited[movept.y][movept.x]=true;
q.offer(new Point(movept.y, movept.x,0));
movept.dis=Integer.MAX_VALUE;//초기화(최소값을 찾아야 하기 때문에)
while(!q.isEmpty())
{
Point tmp=q.poll();
if(tmp.dis>movept.dis)
{
break;
}// 나온 거리 값이 현재 저장된 최소 거리값보다 클 경우 중지(거리가 가까운 곳을 우선으로 탐색하기 떄문에)
if(arr[tmp.y][tmp.x]!=0&&arr[tmp.y][tmp.x]<baby[2]) // 먹을 수 있는 물고기
{
if(tmp.dis<movept.dis)
{
movept=tmp;
}
else if(tmp.dis==movept.dis) // 거리가 같다면
{
if(tmp.y<movept.y) //y값이 작은 값을 우선으로 두고
{
movept=tmp;
}
else if(tmp.y==movept.y&&tmp.x<movept.x) // y값이 같다면 x값이 작은 것을 우선으로 둠
{
movept=tmp;
}
}
continue;
}
for(int i=0;i<4;i++)
{
int ny=tmp.y+dy[i];
int nx=tmp.x+dx[i];
if(ny>=0&&nx>=0&&ny<n&&nx<n)
{
if(visited[ny][nx]==false&&arr[ny][nx]<=baby[2])
{
visited[ny][nx]=true;
q.offer(new Point(ny,nx,tmp.dis+1));
}
}
}
}
if(movept.dis!=Integer.MAX_VALUE)
{
ans+=movept.dis;
baby[3]++;
if(baby[3]==baby[2])
{
baby[2]++;
baby[3]=0;
}
arr[movept.y][movept.x]=0;
}
else
{
break;
}
}
System.out.println(ans);
}
}
[백준] 골드3 16236번 아기 상어
'작심3일 챌린지 > 코딩 테스트' 카테고리의 다른 글
| [백준] 골드5 7490번 0 만들기 (0) | 2024.03.18 |
|---|---|
| [백준] 골드5 1916 최소비용 구하기 (1) | 2024.02.02 |
| [백준] 골드4 1753번 최단경로 完 (0) | 2024.02.02 |
| [백준] 골드2 1135 뉴스 전하기 (작성중) (0) | 2024.02.01 |
| [백준] 실버4 2164 카드2 (1) | 2024.02.01 |
댓글