- 소요시간 : 2시간
- 문제 사이트 : 백준
- 문제 수준 : 골드 2
- 문제 유형 : 구현, 시뮬레이션
- 다른 사람의 풀이를 참고 했는가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/19237
- 푼 날짜 : 2023.05.03
1. 사용한 자료구조 & 알고리즘
- 구현 & 시뮬레이션
- 해시맵 :
1번 상어의 방향의 가지수가 16개
2번 상어의 가지수가 16개 ....로 서로 각각 다 다르므로
해당 상어의 16개의 가지수를 정해주기 위해서 해시맵 사용
2. 사고과정
문제를 보고 N , M , K를 봤는데 그냥 그대로를 구현해주면 시간초과는 나지 않을 것으로 예상.
M 개의 상어가 최대 k 번 이동할 것으로 , 400 * 1000 정도로 예상했음.
고민한 부분은
해당 상어에게 할당된 우선순위 방향을 어떻게 구현할 것인가 ?
-> 앞서 말했듯 해시맵을 이용해서, 다음 좌표를 구했다.
냄새가 없는 것을 먼저 이동, 그 외에는 내 냄새가 있는 좌표로 이동하는데, 둘 다 해당하지 않는 경우가 있나 ?
-> k 최솟값이 1이기 떄문에 내가 이전에 이동하기 전 좌표에는 내 번호의 냄새가 무조건 있기 때문에 그런 경우는 발생할 수 없다.
map의 냄새의 번호와 상어를 분리해서 (map은 그대로 두고, 상어는 queue 같은 걸로 따로 처리)할 것인가, 아니면 map에 상어를 그대로 둘 것인가 ?
-> 상어의 좌표를 queue로 따로 처리해 두면 시간은 덜 걸릴 것이나,
(2차원 map을 뒤지며 상어를 찾을 필요가 없음) 코드가 복잡해지고
N의 크기가 작으므로, map에 상어의 정보도 함께 담아서 함께 처리함.
이 정도까지 생각했을 때 40-50분 정도 지났고, 그 후에는 코딩했다.
3. 풀이과정
- 맵에 1번 상어 외의 다른 상어가 없는 경우에 while문 반복
- 맵에 상어가 있는 경우, 해당 좌표에 k개의 냄새를 뿌린다. 이 때, 어떤 상어의 냄새인지도 함께 저장.
- 상어를 이동시킨다. 해시맵에 저장해둔 해당 상어의 이동 우선순위에 따라 이동, 그리고 주변에 냄새가 없는 공간이 있다면 그 좌표로, 그 외에는 내 번호의 냄새가 있는 좌표로 간다. ( 상어 1마리 1마리 따로 처리하지 않고 queue에 담아두었다가 한번에 처리)
- 냄새가 존재하는 좌표가 있다면, 냄새를 1줄이고 냄새가 이떄 0이 된다면 어떤 상어의 냄새인지도 함께 제거한다.
- while문이 돌 때마다 count를 증가하는데, 1000 초과가 되면 -1을 출력한다.
4. 소스코드
import java.util.*;
import java.io.*;
public class Main{
static Shark shark[][];
static HashMap<Integer,Integer[]> sharkDir=new HashMap<>();
static int dy[] = {0,-1,1,0,0};
static int dx[] = {0,0,0,-1,1};
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb=new StringBuilder();
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int M=Integer.parseInt(st.nextToken());
int k=Integer.parseInt(st.nextToken());
shark=new Shark[N][N];
HashMap<Integer,Integer[]> tempMap = new HashMap<>();
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
shark[i][j] =new Shark(0,0,0,0);
shark[i][j].num = Integer.parseInt(st.nextToken());
if(shark[i][j].num>0)
tempMap.put(shark[i][j].num,new Integer[] {i,j});
}
}
st=new StringTokenizer(br.readLine());
//상어의 좌표와, 방향이 따로따로 주어지므로, 좌표를 기억해 두었다가 나중에 해당 좌표에 방향을 부여
for(int i=0;i<M;i++) {
int num = Integer.parseInt(st.nextToken());
Integer sharkPoint[] = tempMap.get(i+1);
int sharkY=sharkPoint[0];
int sharkX=sharkPoint[1];
shark[sharkY][sharkX].dir = num;
}
//해시맵으로 해당 상어의 이동방향 우선순위를 지정해줌
for(int i=0;i<M;i++) {
int num = 0;
Integer arr[]=new Integer[16];
for(int j=0;j<4;j++) {
st=new StringTokenizer(br.readLine());
arr[num++] = Integer.parseInt(st.nextToken());
arr[num++] = Integer.parseInt(st.nextToken());
arr[num++] = Integer.parseInt(st.nextToken());
arr[num++] = Integer.parseInt(st.nextToken());
}
sharkDir.put(i+1,arr);
}
int count =0;
//상어가 2마리 이상 있다면 반복.
while(checkShark()==false) {
//상어가 있는 좌표에 냄새를 뿌림
spreadSmell(k);
//상어가 이동함
moveShark();
//냄새가 있는 좌표의 냄새를 1 줄임
reduceSmell();
//count 가 while 문이 돌때마다 증가하는데, 1000 초과가 되면 -1을 출력하고 멈춤
count ++;
if(count>1000) {
System.out.println(-1);
System.exit(0);
}
}
System.out.println(count);
}
//해당 좌표에 상어가 있다면,
//그 좌표에 어떤 상어의 냄새인지와, k초 동안 지속되는 냄새를 남김
public static void spreadSmell(int k) {
for(int i=0;i<shark.length;i++) {
for(int j=0;j<shark.length;j++) {
if(shark[i][j].num>0) {
shark[i][j].smell = shark[i][j].num;
shark[i][j].k = k;
}
}
}
}
//1번 상어 이외에 다른 상어가 있는지 체크. true,false로 반환
public static boolean checkShark() {
for(int i=0;i<shark.length;i++) {
for(int j=0;j<shark.length;j++) {
if(shark[i][j].num>=2) return false;
}
}
return true;
}
//상어를 이동시키는 메소드
public static void moveShark() {
//상어의 이동은 한 번에 처리되므로 queue에 담아두었다가 처리
Queue<Integer[] > queue=new LinkedList<>();
for(int i=0;i<shark.length;i++) {
for(int j=0;j<shark.length;j++) {
//해당 좌표에 상어가 있다면
if(shark[i][j].num>0) {
//해시맵에 저장해 두었던 우선순위 배열을 가져옴
Integer dirRecipe[] = sharkDir.get(shark[i][j].num);
//내가 현재 바라보고 있는 방향에 따라, 다음 4개 좌표를 구함
int next = 4 * (shark[i][j].dir-1);
int yy [] = new int[5];
int xx [] = new int[5];
for(int k=1;k<5;k++) {
yy[k] = dy [ dirRecipe[next] ] ;
xx[k] = dx [ dirRecipe[next++] ] ;
}
boolean findNoSmellArea = false;
int nextY=0;
int nextX=0;
int saveDir = 0;
//4개 방향에서, 냄새가 없는 좌표를 찾았다면 그 방향으로 이동하기 위해 좌표 저장.
for(int k=1;k<5;k++) {
nextY = i+ yy[k];
nextX = j + xx [k];
if(nextY<0||nextX<0||nextY>=shark.length||nextX>=shark.length)
continue;
if(shark[nextY][nextX].smell == 0) {
findNoSmellArea = true;
saveDir = k;
break;
}
}
//냄새가 없는 좌표를 찾지 못했다면, 그 방향으로 이동하기 위해 좌표 저장
if(!findNoSmellArea) {
for(int k=1;k<5;k++) {
nextY = i+ yy[k];
nextX = j + xx [k];
if(nextY<0||nextX<0||nextY>=shark.length||nextX>=shark.length)
continue;
if(shark[nextY][nextX].smell == shark[i][j].smell) {
saveDir = k;
break;
}
}
}
// 내가 바라보는 방향을 정한다.
int nextDir = 0;
if(yy[saveDir]== -1 && xx[saveDir] == 0) nextDir = 1;
else if (yy[saveDir]== 1 && xx[saveDir] == 0) nextDir = 2;
else if (yy[saveDir]== 0 && xx[saveDir] == -1) nextDir = 3;
else nextDir = 4;
//다음 좌표, 상어 번호, 방향을 저장하고
//현재 좌표의 번호, 방향을 제거
queue.add(new Integer[] {nextY,nextX,shark[i][j].num,nextDir});
shark[i][j].num = 0;
shark[i][j].dir= 0;
}
}
}
//큐에 저장해 두었던 상어들을 꺼냄
while(!queue.isEmpty()) {
Integer temp[]=queue.poll();
int Y=temp[0];
int X=temp[1];
int num=temp[2];
int dir=temp[3];
//만약 해당 좌표에 상어가 없다면, 그냥 이동함
if(shark[Y][X].num==0) {
shark[Y][X].num = num;
shark[Y][X].dir = dir;
}
//해당 좌표에 상어가 있다면, 현재 상어 번호가 더 적은 경우에만 갱신
else {
if(shark[Y][X].num > num ) {
shark[Y][X].num = num;
shark[Y][X].dir = dir;
}
}
}
}
//맵 전체의 냄새를 1씩 줄여줌
//냄새가 0이 된다면, 몇번 상어의 냄새인지도 지움.
public static void reduceSmell () {
for(int i=0;i<shark.length;i++) {
for(int j=0;j<shark.length;j++) {
if(shark[i][j].k>0) {
shark[i][j].k --;
if(shark[i][j].k==0) {
shark[i][j].smell = 0;
}
}
}
}
}
}
class Shark {
int num;
int dir;
int smell;
int k;
Shark(int num,int dir,int smell,int k) {
this.num=num;
this.dir=dir;
this.smell=smell;
this.k=k;
}
}
5. 결과
6. 회고
이번 문제를 품으로써 아기 상어, 청소년 상어, 어른 상어를 모두 풀었다.
여기있는 삼성 sw 역량 테스트 기출 문제를 다 풀고 싶다..!!
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
아이스 카라멜 마끼아또보단 뜨거운 아메리카노를, 맨투맨보단 니트를, 웹툰보단 책을 좋아하고 싶은 사람