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
[문제]
청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.
N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.
각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.
모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
| 우선 순위 | |||||||
| 상어 1 | 상어 2 | 상어 3 | 상어 4 | ||||
| ↑ | ↓←↑→ | ↑ | ↓→←↑ | ↑ | →←↓↑ | ↑ | ←→↑↓ |
| ↓ | →↑↓← | ↓ | ↓↑←→ | ↓ | ↑→←↓ | ↓ | ←↓→↑ |
| ← | ←→↓↑ | ← | ←→↑↓ | ← | ↑←↓→ | ← | ↑→↓← |
| → | →←↑↓ | → | →↑↓← | → | ←↓↑→ | → | ↑→↓← |
<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.
<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.
<그림 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라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.
- 맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.
[코드]
import java.util.*;
class Shark {
int x, y, dir;
public Shark(int x, int y, int dir) {
this.x=x;
this.y=y;
this.dir=dir;
}
}
public class BaekJoon_19237 {
static int n,m,k;
static Shark[] shark; // 1~m번째까지 각 상어의 위치와 방향 저장
static int[][] resttime; // 각 냄새의 남은 시간 -> 냄새를 뿌리면 k로 초기화
static int[][] smellowner; // 각 냄새를 뿌린 상어의 번호
static int[][][] priority; // 각 상어의 방향에 따른 우선순위
static int[] dx= {0,-1,1,0,0};
static int[] dy= {0,0,0,-1,1};
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
n=sc.nextInt(); // 배열 크기
m=sc.nextInt(); // 상어의 수
k=sc.nextInt(); // k번 이동하면 냄새 소멸
resttime=new int[n+1][n+1];
smellowner=new int[n+1][n+1];
shark=new Shark[m+1];
priority=new int[m+1][5][4];
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
int n=sc.nextInt();
// 상어가 있는 위치라면
if(n>0) {
shark[n]=new Shark(i,j,0); // 해당 번호의 상어 위치 저장
smellowner[i][j]=n; // 냄새의 주인 번호 저장
resttime[i][j]=k; // 냄새 생존 시간인 k로 초기화
}
}
}
// 각 상어의 방향 입력 받기 1:위, 2:아래, 3:왼쪽, 4:오른쪽
for(int i=1;i<=m;i++)
shark[i].dir=sc.nextInt();
// 각 상어마다 4방향에서의 우선 순위 입력받기
for(int i=1;i<=m;i++)
for(int j=1;j<=4;j++)
for(int k=0;k<4;k++)
priority[i][j][k]=sc.nextInt();
System.out.println(solve());
}
static int solve() {
int time=0;
while(true) {
// 1번 상어만 살아남았는지 확인하는 과정 -> 종료 조건
int count=0;
for(int i=1;i<=m;i++)
if(shark[i]!=null)
count++;
// 1번 상어만 살아남았다면 소요시간 return 후 종료
if(count==1&&shark[1]!=null)
return time;
// 1번 상어만 남지 못하고 1000초가 지났다면 실패
if(time>=1000)
return -1;
int[][] temp=new int[n+1][n+1];
for(int i=1;i<=m;i++)
// 격자 안에 있는 상어 이동시키기
if(shark[i]!=null)
moveShark(temp,i);
// 냄새의 유효시간 1씩 감소
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(resttime[i][j]>0)
resttime[i][j]--;
// 냄새 유효시간이 끝났다면 냄새의 주인도 없애주기
if(resttime[i][j]==0)
smellowner[i][j]=0;
}
}
/*
* 1초마다 상어가 이동한 결과는 temp 배열에 저장되어 있으므로
* temp 배열을 탐색해 상어가 새롭게 이동한 칸의 냄새 유효시간 k로 저장
* 해당 칸의 냄새의 상어 번호 저장
*/
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(temp[i][j]>0) {
resttime[i][j]=k;
smellowner[i][j]=temp[i][j];
}
}
}
time++;
}
}
/*
* 상어를 이동시키는 함수, m은 이동시킬 상어의 번호
* temp 배열에는 1번부터 m번까지의 상어가 순서대로 우선순위에 따라 이동한 결과가 저장되어 있다.
* 상어가 이동했을 때 실제 map을 바로 변경하지 않고 임시 배열에 저장했다가 한꺼번에 바꾸는 것이 오류 예방에 좋다.
*/
static void moveShark(int[][] temp, int m) {
int nx=0;
int ny=0;
int d=0;
/*
* 상어가 이동할 곳의 우선순위 첫번째는 아무 냄새로 없는 칸이다.
* 이 조건을 만족하는 곳으로 이동했는지 확인하기 위한 변수
*/
boolean flag=false;
for(int i=0;i<4;i++) {
// m번 상어의 현재 방향에서의 우선순위에 따라 순서대로 탐색
d=priority[m][shark[m].dir][i];
nx=shark[m].x+dx[d];
ny=shark[m].y+dy[d];
// 이동한 곳이 배열 범위 내에 있으며 다른 상어의 냄새가 없는 곳이라면 탐색 종료
if(nx>=1&&ny>=1&&nx<=n&&ny<=n&&smellowner[nx][ny]==0) {
flag=true;
break;
}
}
// 냄새가 없는 곳이 없는 경우
if(!flag) {
for(int i=0;i<4;i++) {
// m번 상어의 현재 방향에서의 우선순위에 따라 순서대로 탐색
d=priority[m][shark[m].dir][i];
nx=shark[m].x+dx[d];
ny=shark[m].y+dy[d];
// 인접한 칸 중에서 자신의 냄새가 있는 칸의 위치를 찾는다.
if(nx>=1&&ny>=1&&nx<=n&&ny<=n&&smellowner[nx][ny]==m)
break;
}
}
/*
* m번째 상어가 이동할 위치에 자신보다 이전에 이동한 상어가 없다면(자신보다 우선순위가 높은 상어)
* 이동한 위치로 상어 정보 수정(좌표, 바라보고 있는 방향)
*/
if(temp[nx][ny]==0) {
temp[nx][ny]=m;
shark[m].dir=d;
shark[m].x=nx;
shark[m].y=ny;
}
// 이동하려는 위치에 이미 자신보다 우선순위가 높은 상어가 있다면 m번째 상어는 격자 밖으로 쫒겨난다.
else
shark[m]=null;
}
}
[고찰]
이번 문제는 전형적인 삼성 SW 문제로 주어진 조건을 모두 구현하면 되는 시뮬레이션 문제였다. 스스로의 힘으로 풀어보려 노력했지만 쉽지 않아 다른 사람의 코드를 참고하면서 해결하였다.
*** 0) 필요한 자료구조
0-1) 상어의 현재 위치와 현재 바라보고 있는 방향을 저장할 클래스 선언 (class Shark)
0-2) 1~m번째 각 상어의 위치와 방향을 저장할 배열 선언 (Shark[] shark=new Shark[m+1])
0-3) 각 냄새의 유효시간을 저장하는 배열 (int[][] resttime=new int[n+1][n+1])
0-4) 각 냄새를 뿌린 상어의 번호를 저장하는 배열 (int[][] smellowner=new int[n+1][n+1])
0-5) 각 산어의 방향에 따른 우선순위를 저장하는 배열 (int[][][] priority=new int[m+1][5][4])
*** 1) 상어 이동 (moveShark 함수)
1-1) 상어는 1번부터 우선순위를 갖기 때문에 1번부터 m번까지의 상어가 격자 내에 있다면 이동을 시작한다.
1-2) 이동하려는 m번째 상어가 현재 바라보고 있는 방향에서의 우선순위에 따라 상, 하, 좌, 우를 탐색한다.
1-3) 상, 하, 좌, 우에 다른 상어의 냄새가 없는 곳이라면 상어가 우선적으로 이동해야 하는 칸이므로 탐색을 종료한다.
1-4) 인상, 하, 좌, 우에 비어있는 칸이 없다면 자신의 냄새가 있는 칸의 위치를 찾는다.
1-5) m번째 상어가 이동할 위치에 자신보다 이전에 이동한 상어(m번째 상어보다 우선순위가 높은 상어)가 없다면 해당 칸으로 이동한다. or 상어가 있다면 m번째 상어는 격자 밖으로 쫒겨난다.
*** 2) 냄새 유효시간 감소 (solve 함수)
2-1) m마리의 상어가 모두 이동을 끝냈다면 모든 냄새의 유효시간을 1 감소한다.
2-2) 유효시간을 감소시켜 0이 됐다면 해당 냄새의 주인인 상어 번호를 저장한 배열 값도 초기화 시킨다.
*** 3) 이동한 상어 위치에 냄새 생성 (solve 함수)
3-1) 1번 과정을 통해 모든 상어가 새롭게 이동한 칸에 냄새를 뿌린다.(= 냄새의 유효시간을 저장하는 함수의 값을 k로 초기화 한다.)
3-2) 냄새를 뿌린 칸에 냄새의 주인인 상어의 번호를 저장한다.
시뮬레이션 문제는 우선 문제를 정확하게 이해하고 문제를 구조화 하여 필요한 부분을 흐름대로 구현하는 과정이 중요한 것 같다. 좀 더 노력해서 이러한 능력을 길러야겠다.
'백준' 카테고리의 다른 글
| [백준_1937번] 욕심쟁이 판다 (0) | 2021.10.22 |
|---|---|
| [백준_1062번] 가르침 (0) | 2021.10.20 |
| [백준_17142번] 연구소 3_삼성 SW 역량테스트 (0) | 2021.10.19 |
| [백준_20058번] 마법사 상어와 파이어스톰_삼성 SW 역량테스트 (0) | 2021.10.12 |
| [백준_10711번] 모래성 (0) | 2021.10.12 |