문제
청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.
N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.
각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.
모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
<그림 1>
우선 순위상어 1상어 2상어 3상어 4↑↑↑↑↓↓↓↓←←←←→→→→
| ↓ ← ↑ → | ↓ → ← ↑ | → ← ↓ ↑ | ← → ↑ ↓ |
| → ↑ ↓ ← | ↓ ↑ ← → | ↑ → ← ↓ | ← ↓ → ↑ |
| ← → ↓ ↑ | ← → ↑ ↓ | ↑ ← ↓ → | ↑ → ↓ ← |
| → ← ↑ ↓ | → ↑ ↓ ← | ← ↓ ↑ → | ↑ → ↓ ← |
<표 1>
<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.
<그림 2>
<그림 3>
<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.
<그림 4>
<그림 5>
<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.
이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.
입력
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)
그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.
그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.
그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.
맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.
출력
1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
https://www.acmicpc.net/problem/19237
19237번: 어른 상어
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미
www.acmicpc.net
package Samsung;
import java.io.*;
import java.util.*;
public class 어른상어 {
static int n,m,k;//m상어개수, 냄새k번이동후 사라짐
static Info[][]arr;
static int[][][]wayorder;
static int[]dx = {0,-1,1,0,0};
static int[]dy = {0,0,0,-1,1};
static class Pos {
int x,y;
Pos(int x, int y){
this.x = x;
this.y = y;
}
}
static class Info{
int num;
int kcnt;
Info(int num, int kcnt){
this.num = num;
this.kcnt = kcnt;
}
}
public static void print() { //arr 덤프용
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr[i].length; j++) {
if(arr[i][j]!=null) {
System.out.print("("+arr[i][j].num+" "+arr[i][j].kcnt+")");
}
else {
System.out.print("("+0+" "+0+")");
}
}
System.out.println();
}
System.out.println();
}
public static boolean cango(int x, int y) {
return x>=0 && x<n && y>=0 && y<n;
}
public static boolean checkAll(Pos[] sharkpos) { //상어1을 제외한 나머지 상어들이 모두 없는지 확인
for(int i=2; i<sharkpos.length; i++) { //상어 위치 배열이 1빼고 모두 null인지를 통해 확인을 한다.
if(sharkpos[i]!=null) {
return false;
}
}
return true;
}
public static void move(Pos[] sharkpos) {
for(int i=0; i<arr.length; i++) { //나머지냄새나는곳의 냄새(kcnt)를 1줄여준다
for(int j=0; j<arr[i].length; j++) {
if(arr[i][j]!=null) { //만약 냄새나는 곳일 경우
arr[i][j].kcnt-=1;
if(arr[i][j].kcnt==0) {arr[i][j]=null;}
}
}
}
for(int i=1; i<=m; i++) {
Pos p = sharkpos[i];
if(p!=null) { //i번째상어가 아직 존재하는 경우
Info f = arr[p.x][p.y];
if(f!=null && f.num!=i) { //이미 배치하고자 하는 자리에 다른 상어가 있다면
sharkpos[i]=null; //i 번째 상어를 퇴출 ( 작은 번호가 차지해야하기 떄문)
continue;
}
arr[p.x][p.y]= new Info(i,k); //자리에 아무도 없으면 배치해줌
}
}
}
public static void simulate(int[] sharkway , Pos[] sharkpos ) {
/*어려웠던 부분2: 상어의 다음 방향과 위치를 찾는것*/
for(int i=1; i<=m; i++) {
if(sharkpos[i]!=null) {
Pos p = sharkpos[i];
int x = p.x;
int y = p.y;
int dir = sharkway[i];
int ndir =dir;
int nx =x;
int ny =y;
boolean tg = false;
for(int d=1; d<=4; d++) {
int ddir = wayorder[i][dir][d];
nx=x+dx[ddir];
ny=y+dy[ddir];
if(cango(nx,ny)&&arr[nx][ny]==null) { //4방향 중 null 인 것(냄새가 없는곳)을 찾는다
ndir =ddir;
tg = true;
break;
}
}
if(tg==false) { //냄새가 없는 곳을 찾지 못했을때
for(int d=1; d<=4; d++) {
int ddir = wayorder[i][dir][d];
nx=x+dx[ddir];
ny=y+dy[ddir];
if(cango(nx,ny)&&arr[nx][ny].num==i) { //4방향 중 현재와 냄새가 같은 곳 을 찾는다.
ndir =ddir;
tg = true;
break;
}
}
}
if(tg==false)continue; //냄새가 없는 곳 , 냄새가 같은 곳 둘다 못찾았을때
sharkway[i]=ndir;
sharkpos[i] = new Pos(nx,ny);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
//어려웠던부분3 : 자료구조를 어떻게 해야할지
arr = new Info[n][n];
int[] sharkway = new int[m+1]; //상어의 방향 저장
Pos[] sharkpos = new Pos[m+1]; //상어의 위치 저장
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
int nn = Integer.parseInt(st.nextToken());
if(nn!=0) { //만약 0이아닌 숫자가 있다면 Info저장을 해준다.
arr[i][j] = new Info(nn,k);
sharkpos[arr[i][j].num]= new Pos(i,j);
}
}
}
st = new StringTokenizer(br.readLine());
for(int i=1; i<=m; i++) {
sharkway[i] = Integer.parseInt(st.nextToken());
}
/*어려웠던 부분1: 방향순서 처리하는 것*/
wayorder = new int[m+1][5][5];
for(int i=1; i<=m; i++) {
for(int j=1; j<=4; j++) {
st = new StringTokenizer(br.readLine());
for(int k=1; k<=4; k++) {
wayorder[i][j][k] =Integer.parseInt(st.nextToken());
//i번째 상어가 현재 방향 j일때의 방향 순서 4가지(k)
}
}
}
int time =0;
while(!checkAll(sharkpos)) {
if(time>=1000) {time=-1; break;} //시간이 1000인데도 checkAll이 false라는 건 시간이 1000을 넘어가서도 상어가 남아있다는것
simulate(sharkway,sharkpos);
move(sharkpos);
time ++;
}
System.out.println(time);
}
}
- 어려웠던 부분1: 방향순서 처리하는 것
- 어려웠던 부분2: 상어의 다음 방향과 위치를 찾는것
- 어려웠던부분3 : 자료구조를 어떻게 해야할지
'백준 > 삼성기출' 카테고리의 다른 글
| 마법사상어와토네이도-20057번(Java) (0) | 2021.09.22 |
|---|---|
| 스타트택시 - 1923번(Java) (0) | 2021.09.18 |
| 마법사 상어와 파이어볼 / 시뮬레이션 (0) | 2021.04.23 |
| 큐빙 (0) | 2021.04.19 |
| 치킨 배달 (0) | 2021.04.19 |
