백준 19237 어른 상어 - 삼성 SW 역량 테스트 기출

백준 19237 어른 상어 - 삼성 SW 역량 테스트 기출

1. 문제 링크

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

 

2. 문제 해결에 대한 아이디어

1. 상어의 방향 정보는 번호 순서대로 입력 받기 때문에 상어 리스트를 번호를 기준으로 sorting 해야한다.

2. 격자는 Tile(상어 번호, 냄새 번호, 냄새 잔여시간) 의 2차원 배열로 구성했다.

3. 이 문제는 고려해야할 것이 아주 많다. 냄새, 격자 밖으로 나간 상어, 이동 후에 격자 상태 등이다.

4. 상어가 겹치는 경우가 발생할 수 있어서, 상어 번호를 제외한 냄새 정보만 동일한 copyBoard 를 이동에 사용했다.

5. 격자 밖으로 나가는 상어는 따로 byeShark 리스트에 "번호"를 저장했다.

6. 다음과 같은 순서를 구성했다.

   1. 초기 상어 위치에 대한 냄새 생성

   2. 반복 (횟수가 1000이 넘어가거나, 1번 상어만 남은 경우)

      1. 상어 움직임

         1. 움직이기 전에, copyBoard를 만들어서 copyBoard에서 움직였다.

         2. 다 움직이고나서 copyBoard 정보를 board로 다시 저장했다.

      2. 밖으로 나간 상어를 상어 리스트에서 제거

      3. 기존에 있던 냄새 지속시간 감소

      4. 새로운 상어 위치에 냄새 생성

7. 인접한 빈 칸이 없을 때, 자기 냄새가 있는 방향으로 가야한다. 

   1. 이 말 뜻을 이해하기 힘들었다. 자기 냄새가 있는 칸이 꼭 인접하지 않아도 되는 건지 헷갈렸다.

   2. 인접한 칸만 조사하는 로직을 짰는데, 통과했다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class Main {

	static class Shark implements Comparable<Shark> {
		int y, x, no;
		int d;
		HashMap<Integer, ArrayList<Integer>> hm = new HashMap<>();

		public Shark(int y, int x, int no) {
			super();
			this.y = y;
			this.x = x;
			this.no = no;
		}

		@Override
		public int compareTo(Shark o) {
			// TODO Auto-generated method stub
			return this.no - o.no;
		}

	}

	static class Tile {
		int sharkNo;
		int smellNo;
		int timer;

		public Tile(int sharkNo, int smellNo, int timer) {
			super();
			this.sharkNo = sharkNo;
			this.smellNo = smellNo;
			this.timer = timer;
		}

		public Tile(Tile t) {
			super();
			this.sharkNo = t.sharkNo;
			this.smellNo = t.smellNo;
			this.timer = t.timer;
		}
	}

	static Tile[][] board;
	static Tile[][] copyBoard;
	static ArrayList<Integer> byeShark = new ArrayList<>();
	static ArrayList<Shark> sharkList = new ArrayList<>();
	static int[] dirY = { -1, 1, 0, 0 };
	static int[] dirX = { 0, 0, -1, 1 };
	static int N, M, K; // K번 이동하면 사라짐
	static int time = 0;

	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\어른상어_19237\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] nmk = br.readLine().split(" ");
		N = Integer.parseInt(nmk[0]);
		M = Integer.parseInt(nmk[1]);
		K = Integer.parseInt(nmk[2]);

		board = new Tile[N][N];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				int sharkNo = Integer.parseInt(line[j]);

				board[i][j] = new Tile(sharkNo, 0, 0);
				if (sharkNo != 0) {
					sharkList.add(new Shark(i, j, sharkNo));
				}
			}
		}
		Collections.sort(sharkList);
		String[] line = br.readLine().split(" ");
		for (int i = 0; i < M; i++) {
			sharkList.get(i).d = Integer.parseInt(line[i]) - 1; // 방향 보정
		}

		for (int i = 0; i < M; i++) {
			Shark s = sharkList.get(i);
			for (int j = 0; j < 4; j++) {
				line = br.readLine().split(" ");
				ArrayList<Integer> temp = new ArrayList<>();
				for (int k = 0; k < 4; k++) {
					temp.add(Integer.parseInt(line[k]) - 1); // 방향 보정
				}
				s.hm.put(j, temp);
			}
		}

		smellMake();

		while (time <= 1000) {

			++time;
			sharkMove();
			sharkBye();
			smellDecrease();
			smellMake();

			if (sharkList.size() == 1)
				break;
		}
		if (time > 1000)
			time = -1;
		System.out.println(time);
	}

	public static void sharkBye() {
		for (int i = 0; i < byeShark.size(); i++) {
			int no = byeShark.get(i);
			for (int j = 0; j < sharkList.size(); j++) {
				if (no == sharkList.get(j).no) {
					sharkList.remove(j);
					break;
				}
			}
		}
		byeShark.clear();
	}

	public static void smellMake() {
		for (int i = 0; i < sharkList.size(); i++) {
			Shark s = sharkList.get(i);
			int no = s.no;
			int y = s.y;
			int x = s.x;
			Tile t = board[y][x];
			t.sharkNo = no;
			t.smellNo = no;
			t.timer = K;
		}
	}

	public static void smellDecrease() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				Tile t = board[i][j];
				if (t.timer != 0) {
					--t.timer;
				}
				if (t.timer == 0) {
					t.smellNo = 0;
				}
			}
		}
	}

	public static void makeCopyBoard() {
		copyBoard = new Tile[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				copyBoard[i][j] = new Tile(0, board[i][j].smellNo, board[i][j].timer);
			}
		}
	}

	public static void backToBoard() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = new Tile(copyBoard[i][j]);
			}
		}
	}

	public static void sharkMove() {
		makeCopyBoard();
		// 카피보드에서 해야함
		for (int i = 0; i < sharkList.size(); i++) {
			Shark s = sharkList.get(i);
			ArrayList<Integer> dirPrior = s.hm.get(s.d);

			boolean canMove = true;
			int yy = 0;
			int xx = 0;
			int dd = -1;
			for (int j = 0; j < 4; j++) {
				yy = s.y + dirY[dirPrior.get(j)];
				xx = s.x + dirX[dirPrior.get(j)];

				if (yy >= N || xx >= N || yy < 0 || xx < 0 || copyBoard[yy][xx].smellNo != 0) {
					canMove = false;
					continue;
				}

				canMove = true;
				dd = dirPrior.get(j);
				break;
			}

			if (canMove) { // 빈칸을 찾아서 이동할 수 있음
				// 그런데 거기에 상어가 있을 수도 있음
				if (copyBoard[yy][xx].sharkNo != 0) {
					if (copyBoard[yy][xx].sharkNo < s.no) {
						// s가 쫓겨남
						byeShark.add(s.no);
					} else {
						byeShark.add(copyBoard[yy][xx].sharkNo);
						copyBoard[yy][xx].sharkNo = s.no;
						s.y = yy;
						s.x = xx;
						s.d = dd;
					}
				} else { // 완벽한 빈칸이면
					copyBoard[yy][xx].sharkNo = s.no;
					s.y = yy;
					s.x = xx;
					s.d = dd;
				}
			} else { // 주변에 갈 곳이 없어서 자신의 냄새가 있는 칸으로 가야함

				int d;
				for (int j = 0; j < dirPrior.size(); j++) {
					d = dirPrior.get(j);
					yy = s.y + dirY[d];
					xx = s.x + dirX[d];

					if (yy >= N || xx >= N || yy < 0 || xx < 0 || copyBoard[yy][xx].smellNo != s.no) {
						continue;
					}

					s.y = yy;
					s.x = xx;
					s.d = d;
					copyBoard[yy][xx].sharkNo = s.no;

					break;
				}

			}
		}
		backToBoard();
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 문제에서 제시하는 조건들이 꽤나 많아 꼼꼼하게 구현해야했다.

2. 자신의 냄새가 있는 방향으로 이동한다는 조건에 대해 "인접한 칸"을 붙여줬으면 안 헷갈렸을 것 같다.