Problem
매 초마다 움직이며 냄새를 뿌리는 상어들이 여러 마리 존재합니다.
각 상어들은 자신들이 바라보는 방향과 기준에 따라서 다음으로 움직일 방향을 선정합니다.
상어들이 같은 격자에 동시에 들어가게 되면 숫자가 작은 상어만 남고 나머지는 전부 내보냅니다.
가장 강한 1 번 상어가 남는 시간은 몇 초 뒤인지 구하는 문제입니다.
Solution
1 번 상어가 남거나 1000 초가 지날 때까지 다음 순서대로 반복하면 됩니다.
moveShark(): 상어 이동- 다음 방향 계산
- 이동
- 경쟁을 통해 작은 번호의 상어 생존
decreaseSmellTime(): 모든 냄새들 1 씩 감소createSmell(): 상어가 이동한 자리에 새로운 냄새 생성
주의할점
- 상어가 이동한 후에는 상어의 방향을 이동한 방향으로 바꿔주어야 합니다.
- 위 순서에서 2번과 3번을 바꾸게 되면 상어가 새로운 냄새를 생성하자마자 1 씩 깎이기 때문에 순서를 지켜야 합니다.
- 상어 리스트를 for 문으로 돌면서 경쟁에서 패배한 상어를 바로 제거하니 런타임 에러가 발생했습니다. for 문 도중에는 요소를 삭제하지 말고 기록해두었다가 나중에 삭제합니다.
Shark Class
- 상어의 넘버, 좌표, 현재 방향과 우선 순위를 갖고 있습니다.
- 우선 순위는
priority[현재 방향][우선 순위]형태입니다. findNextDir함수는 상어가 다음으로 이동할 방향을 구합니다.- 현재 상어의 방향을 기준으로 우선순위가 높은 방향부터
candiates셋에 존재하는지 확인합니다. candidates셋은 상어가 이동할 수 있는 방향들을 갖고 있습니다.
arr, smellOwner, leftTime
- 각각 상어의 위치, 냄새의 주인, 냄새들의 남은 시간을 기록한 2 차원 배열입니다.
noSmellSet, mySmellSet
- 상어가 이동할 수 있는 공간을 미리 구하기 위해 사용합니다.
- 상어는 먼저 냄새가 없는 곳을 찾고 만약 4방향 전부 냄새가 존재한다면 자기 냄새가 있는 방향으로 이동합니다.
- 이동할 수 있는 곳은 여러 개가 될 수 있기 때문에 Set 자료구조에 저장하고 상어의 현재 방향에 따른 우선순위를 통해 비교합니다.
willRemove
- 경쟁에서 뒤쳐진 상어는 제거해야 합니다.
- 한번에 여러 마리가 겹칠 수 있기 때문에 Queue 에 담아둡니다.
Java Code
import java.util.*; import java.io.*; class Main { // 1, 2, 3, 4 는 각각 위, 아래, 왼쪽, 오른쪽 static class Shark { int id, x, y, dir; int[][] priority = new int[5][5]; Shark() { } int findNextDir(Set<Integer> candidates) { for (int i = 1; i < 5; i++) { if (candidates.contains(priority[dir][i])) { return priority[dir][i]; } } return 0; } } static int N, M, k; static int[][] arr = new int[21][21]; static int[][] smellOwner = new int[21][21]; static int[][] leftTime = new int[21][21]; static Map<Integer, Shark> sharks = new HashMap<>(); static int time = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; // input st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken()); 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] > 0) { Shark s = new Shark(); s.id = arr[i][j]; s.x = i; s.y = j; sharks.put(s.id, s); smellOwner[i][j] = s.id; leftTime[i][j] = k; } } } // direction of sharks st = new StringTokenizer(br.readLine()); for (int i = 0; i < M; i++) { Shark s = sharks.get(i + 1); s.dir = Integer.parseInt(st.nextToken()); } // priority of sharks for (int i = 0; i < M; i++) { Shark s = sharks.get(i + 1); for (int j = 0; j < 4; j++) { st = new StringTokenizer(br.readLine()); for (int z = 0; z < 4; z++) { s.priority[j + 1][z + 1] = Integer.parseInt(st.nextToken()); } } } // solution solution(); } static void solution() { while (time++ < 1000) { moveShark(); decreaseSmellTime(); createSmell(); if (sharks.size() == 1) { System.out.println(time); return; } } System.out.println(-1); } // 상어 이동 후 겹친 애 쫓아내기 static void moveShark() { // dx dy 는 위, 아래, 왼쪽, 오른쪽 순서 int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; Queue<Integer> willRemove = new LinkedList<Integer>(); for (Integer id : sharks.keySet()) { Set<Integer> noSmellSet = new HashSet<>(); Set<Integer> mySmellSet = new HashSet<>(); Shark s = sharks.get(id); for (int i = 0; i < 4; i++) { int nx = s.x + dx[i]; int ny = s.y + dy[i]; if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; if (smellOwner[nx][ny] == 0) { noSmellSet.add(i + 1); } else if (smellOwner[nx][ny] == s.id) { mySmellSet.add(i + 1); } } // 냄새 없는 곳부터 스캔하고 자기 냄새 있는 곳을 스캔해서 이동할 방향 구하기 int nextDir = s.findNextDir(noSmellSet); if (nextDir == 0) { nextDir = s.findNextDir(mySmellSet); } // 상어 이동 arr[s.x][s.y] = 0; if (nextDir == 1) { s.x -= 1; } else if (nextDir == 2) { s.x += 1; } else if (nextDir == 3) { s.y -= 1; } else if (nextDir == 4) { s.y += 1; } // 이동할 위치에 상어 있으면 경쟁 후 작은 번호가 승리 if (arr[s.x][s.y] == 0 || s.id < arr[s.x][s.y]) { arr[s.x][s.y] = s.id; s.dir = nextDir; } else { willRemove.add(s.id); } } while (!willRemove.isEmpty()) { sharks.remove(willRemove.poll()); } } // 맵 전체의 냄새 시간을 하나씩 감소 시키고 0 이 되면 냄새 주인 정보도 지움 static void decreaseSmellTime() { for(int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (leftTime[i][j] == 0) continue; leftTime[i][j]--; if (leftTime[i][j] == 0) { smellOwner[i][j] = 0; } } } } // 상어가 이동한 곳에 새로운 냄새 생성 static void createSmell() { for (Integer id : sharks.keySet()) { Shark s = sharks.get(id); smellOwner[s.x][s.y] = s.id; leftTime[s.x][s.y] = k; } } }
'알고리즘 문제 > Samsung' 카테고리의 다른 글
| 백준 19236번. 청소년 상어 (Java) (0) | 2020.10.15 |
|---|---|
| 백준 17143번. 낚시왕 (Java) (3) | 2020.10.14 |
| 백준 17144번. 미세먼지 안녕! (Java) (0) | 2020.10.12 |
| 백준 19238번. 스타트 택시 (Java) (0) | 2020.10.12 |
| 백준 14891번. 톱니바퀴 (Java, Python) (0) | 2019.01.01 |
