[백준/19237] 어른 상어 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/19237

• 분류 : Simulation

• 풀이 시간 : 2시간 30분

  문제를 잘못 해석해서 완전 다른 순서대로 구현함..

  문제를 내 멋대로 해석하지 말고 있는 그대로 풀자! 제발!

문제 해설

1. NxN 칸에 M마리의 상어 존재, 각 상어는 번호 부여되어있음
2. 상어는 자신이 있는 칸에 본인의 냄새 뿌림
3. 냄새 뿌린 후 동, 서, 남, 북 방향으로 이동
   1. 이동 경로 탐색 순서는 각 상어가 바라보고 있는 방향에 따라 우선순위 존재 : 우선순위 방향대로 이동
      1. 우선순위는 상어마다 다름
      2. 우선순위가 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다름
   2. 빈칸이 있으면 빈칸으로 이동
   3. 빈칸이 없으면, 자신의 냄새가 있는 칸의 방향으로 이동
      1. 냄새가 있는 칸이 여러 개이면 : 특정한 우선순위를 따름
   4. 만약 같은 칸에 한마리 이상의 상어가 도착했을 때, 상어 번호가 더 작은 상어만이 살아남음
4. 1번 상어만 살아남게되는 시간 출력
5. 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력

Solution

풀이 접근 방법

1. 변수 선언
   • Shark Class : 상어 객채(상어 번호, 위치, 현재 바라보고 있는 방향, 생사 여부)
   • map[ 0 ][ x 좌표 ][ y 좌표 ] : 해당 위치에 냄새를 뿌리고 간 상어 번호
   • map[ 1 ][ x 좌표 ][ y 좌표 ] : 해당 위치에 뿌린 잔여 냄새
   • List\ sharks : 상어들 리스트
   • int[][][] dirPriority : 특정 상어가 현재 바라보고있는 방향에서 움직일 수 있는 방향의 우선순위
     • dirPriority [ 상어 번호 ][ 현재 바라보고 있는 방향 ][ 방향 ]
2. 상어 이동 -> 이동한 위치에 냄새 뿌림 + 이전 냄새들 감소 -> 상어 생사 여부 확인
3. "같은 칸에 여러마리 도착하면, 더 작은 상어 번호만 살아남음"
   • 상어 번호 오름차순대로 정렬 후 탐색
   • 무조건 작은 번호가 먼저 도착하도록, 이후 도착하는건 다 죽음
4. "빈칸이 없으면, 자신의 냄새가 있는 칸의 방향으로 이동"
   • 빈칸이 없으면, 움직일 수 있는 우선순위 방향대로 돌면서 자신의 냄새가 있는 칸으로 이동
     • 이전 방향으로 돌아가는 것이 아닌 우선순위 방향대로 탐색해야 함!!!

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main_19237 {
  static class Shark {
    int id, x, y, dir;
    boolean isDie;

    public Shark() {
    }

    public Shark(int id, int x, int y) {
      this.id = id;
      this.x = x;
      this.y = y;
      this.isDie = false;
    }

    public void move(int nx, int ny, int dir) {
      this.x = nx;
      this.y = ny;
      this.dir = dir;
    }

  }

  static int N, M, k;
  static int[][][] map, dirPriority;
  static final int LOCATION = 0, SMELL = 1;
  static boolean isFin = false;
  static int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };
  static List<Shark> sharks;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st;

    st = new StringTokenizer(br.readLine());
    N = Integer.valueOf(st.nextToken());
    M = Integer.valueOf(st.nextToken());
    k = Integer.valueOf(st.nextToken());

    // map[0] = 상어 위치
    // map[1] = 잔여 냄새
    map = new int[2][N][N];
    // 0 : 위, 1 : 아래, 2 : 왼, 3 : 오
    dirPriority = new int[M + 1][4][4];
    sharks = new ArrayList<Shark>();

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());

      for (int j = 0; j < N; j++) {
        int id = Integer.valueOf(st.nextToken());
        map[LOCATION][i][j] = id;

        if (id != 0) {
          // 상어 초기 냄새 초기화
          map[SMELL][i][j] = k;
          // 상어 생성
          sharks.add(new Shark(id, i, j));
        } else {
          map[SMELL][i][j] = 0;
        }
      }

    }

    // 상어 번호 순서대로 오른차순 정렬
    Collections.sort(sharks, new Comparator<Shark>() {
      @Override
      public int compare(Shark s1, Shark s2) {
        return Integer.compare(s1.id, s2.id);
      }
    });

    // 상어 방향 초기화
    st = new StringTokenizer(br.readLine());
    for (Shark shark : sharks) {
      shark.dir = Integer.valueOf(st.nextToken()) - 1;
    }

    // 각 상어의 방향 우선순위 입력
    for (int sId = 1; sId <= M; sId++) {
      for (int i = 0; i < 4; i++) {
        st = new StringTokenizer(br.readLine());

        for (int j = 0; j < 4; j++) {
          dirPriority[sId][i][j] = Integer.valueOf(st.nextToken()) - 1;
        }
      }
    }

    bw.write(solution() + "\n");
    bw.flush();
    bw.close();
  }

  static int solution() {
    int time = 0;

    while (time <= 1000) {
      // 상어가 움직인 위치 배열
      int[][] exist = moveShark();

      decreaseSmell(exist);

      if (isFin)
        break;

      time++;
    }

    return time > 1000 ? -1 : time;
  }

  static int[][] moveShark() {
    int[][] exist = new int[N][N];
    int deadCnt = 0;

    for (Shark shark : sharks) {

      if (shark.isDie) {
        deadCnt++;
        continue;
      }

      // 현재 상어가 있는 방향에 대한 이동 우선순위
      int[] flagDir = dirPriority[shark.id][shark.dir];
      boolean canMove = false;

      // 이동할 수 있는 빈 칸 있나 확인
      for (int i = 0; i < 4; i++) {
        int nx = shark.x + dx[flagDir[i]];
        int ny = shark.y + dy[flagDir[i]];

        // 지도 범위 밖이거나 냄새가 존재하면 이동 불가능
        if (!isIn(nx, ny) || map[SMELL][nx][ny] != 0)
          continue;

        // 빈 칸이지만, 이미 나보다 작은 번호를 가진 상어가 도착했으면 죽어야 함
        if (shark.id != 1 && exist[nx][ny] >= 1 && exist[nx][ny] < shark.id) {
          shark.isDie = true;
        } else {
          // 아무도 도착하지 않은 빈칸으로 이동
          exist[nx][ny] = shark.id;
          shark.move(nx, ny, flagDir[i]);
        }

        canMove = true;
        break;
      }

      // 빈 칸으로 이동함
      if (canMove)
        continue;

      // 이동할 수 있는 칸 없으면 내가 있었던 곳으로 다시 이동
      // 바라보고있는 방향의 우선순위대로 탐색
      for (int i = 0; i < 4; i++) {
        int nx = shark.x + dx[flagDir[i]];
        int ny = shark.y + dy[flagDir[i]];

        // 지도 범위 밖이고, 내가 냄새뿌린 칸 아니면 이동 불가능
        if (!isIn(nx, ny) || map[LOCATION][nx][ny] != shark.id)
          continue;

        exist[nx][ny] = shark.id;
        shark.move(nx, ny, flagDir[i]);
        break;
      }
    }

    // 1번 상어 빼고 모두 죽었으면 끝
    if (deadCnt == M - 1)
      isFin = true;

    return exist;
  }

  static void decreaseSmell(int[][] exist) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        // 기존 냄새 감소
        if (map[SMELL][i][j] != 0) {
          int newSmell = map[SMELL][i][j] - 1;

          if (newSmell == 0) {
            map[LOCATION][i][j] = 0;
          }
          map[SMELL][i][j] = newSmell;
        }

        // 움직인 후 상어가 위치한 칸이면 새로운 냄새 뿌림
        if (exist[i][j] != 0) {
          map[LOCATION][i][j] = exist[i][j];
          map[SMELL][i][j] = k;
        }
      }
    }
  }

  static boolean isIn(int x, int y) {
    if (0 <= x && x < N && 0 <= y && y < N)
      return true;
    return false;
  }
}