백준 19236 청소년 상어 - 삼성 SW 역량 테스트 기출

백준 19236 청소년 상어 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

19236번: 청소년 상어

 

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

1. 번호 순서대로 물고기가 이동해야 하기 때문에, fishList에 물고기 정보를 담아 번호를 기준으로 오름차순 sorting했다.

   . 이로 인해 index로 특정 no의 물고기 정보에 접근할 수 있다.

2. 죽은 물고기는 deadList에 "번호"만 넣었고, 죽은 물고기에 대한 정보는 fishList에서 "번호"로 접근했다.

3. 상어는 이동 가능한 칸 중 하나를 선택해서 이동하고 그 경우를 모두 따져야한다. 따라서 이에 대한 DFS를 구현해야 한다.

4. DFS 과정에서는 재귀를 돌았기 때문에, 상태 유지가 중요했다.

   . 재귀를 돌고 나서, 돌기 전의 상태로 복구해야하는 것은 총 4가지가 있다.

      . ArrayList<Fish> fishList(물고기 정보) / ArrayList<Integer> deadList(죽은 물고기 번호)

      . int[][] board(격자) / shark(상어)

   . Integer 리스트나 int 배열은 대입만으로 Deep Copy가 되지만 Custom Object(Fish)는 Deep Copy가 되지 않는다.

   . Collections.addAll(Collection ); 또한 DeepCopy되지 않는다.

   . 따라서, fishList를 copyFishList로 Deep Copy 할 때는 fishList의 값과 동일한 새로운 객체를 생성하여 add 했다.

   . 이를 간단하게 하기 위해, Fish 클래스에 복사 생성자를 구현했다. (코드에서 확인)

 

<DeepCopy 예제 코드>

import java.util.ArrayList;
import java.util.List;

public class CollectionTest {
	
	static class Pair{
		int y, x;

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

	static List<Integer> intList = new ArrayList<>();
	static List<Integer> copyIntList = new ArrayList<>();
	static List<Pair> pairs = new ArrayList<>();
	static List<Pair> copyPairs = new ArrayList<>();

	public static void main(String[] args) {
		intList.add(0);
		intList.add(0);
		intList.add(0);
		
		copyIntList.addAll(intList);
		intList.set(0, 1);
		intList.add(3);
		
		System.out.println("intList");
		intList.forEach(v -> System.out.print(v +" "));
		System.out.println("\ncopyIntList");
		copyIntList.forEach(v -> System.out.print(v +" "));
		System.out.println();
		
		pairs.add(new Pair(0, 0));
		pairs.add(new Pair(1, 0));
		pairs.add(new Pair(2, 0));
		copyPairs.addAll(pairs);
		
		pairs.get(0).y = 1;
		pairs.get(0).x = 1;
		pairs.add(new Pair(3, 0));
		
		System.out.println("pairs");
		pairs.forEach(v -> System.out.printf("(%d, %d) ", v.y, v.x));
		System.out.println();
		System.out.println("copyPairs");
		copyPairs.forEach(v -> System.out.printf("(%d, %d) ", v.y, v.x));
		System.out.println();
	}
}

<DeepCopy 예제 결과>

intList
1 0 0 3 
copyIntList
0 0 0 
pairs
(1, 1) (1, 0) (2, 0) (3, 0) 
copyPairs
(1, 1) (1, 0) (2, 0)

3. 코드

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

public class Main {

	static class Fish implements Comparable<Fish> {
		int y, x;
		int no, d;

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

		public Fish(Fish f) {
			super();
			this.y = f.y;
			this.x = f.x;
			this.no = f.no;
			this.d = f.d;
		}

		@Override
		public int compareTo(Fish o) {
			return this.no - o.no;
		}

	}

	static ArrayList<Fish> fishList = new ArrayList<>(); // 물고기 정보
	static ArrayList<Integer> deadList = new ArrayList<>(); // 죽은 물고기 번호
	static int[][] board = new int[4][4];
	static Fish shark = new Fish(0, 0, -1, -1); // 상어 번호는 -1
	static int[] dirY = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dirX = { 0, -1, -1, -1, 0, 1, 1, 1 };

	static int score = 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\\삼성기출\\청소년상어_19236\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		fishList.add(new Fish(-1, -1, -2, 0)); // 허수값 삽입
		for (int i = 0; i < 4; i++) {
			String[] lines = br.readLine().split(" ");
			int k = 0;
			for (int j = 0; j < 4; j++) {
				int no = Integer.parseInt(lines[k++]);
				int dir = Integer.parseInt(lines[k++]) - 1; // 방향 보정
				board[i][j] = no;
				fishList.add(new Fish(i, j, no, dir));
			}
		}
		Collections.sort(fishList);

		Fish dead = fishList.get(board[shark.y][shark.x]);
		deadList.add(dead.no);
		board[shark.y][shark.x] = -1;
		shark.d = dead.d;
		selectDead();

		System.out.println(score);
		br.close();
	}

	static void selectDead() {
		fishMove();

		int iy = shark.y;
		int ix = shark.x;
		int id = shark.d;

		while (true) {
			int yy = shark.y + dirY[id];
			int xx = shark.x + dirX[id];

			if (yy >= 4 || xx >= 4 || yy < 0 || xx < 0) { // 더 이상 이동할 곳이 없다.
				int temp = 0;
				for (int i = 0; i < deadList.size(); i++) {
					temp += deadList.get(i);
				}

				score = Math.max(score, temp);

				return;
			}

			shark.y = yy;
			shark.x = xx;
			if (board[yy][xx] == 0) { // 상어는 빈칸으로 이동 못함
				continue;
			}

			// 상어가 이동할 것이다.
			Fish save = new Fish(shark);
			int[][] copyBoard = new int[4][4];
			ArrayList<Fish> copyFishList = new ArrayList<>();
			// deep copy
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					copyBoard[i][j] = board[i][j];
				}
			}
			fishList.forEach(f -> copyFishList.add(new Fish(f)));
			// select dead
			Fish dead = fishList.get(board[yy][xx]);
			deadList.add(dead.no);

			board[iy][ix] = 0; // 상어가 있던 곳을 빈칸으로
			shark = new Fish(yy, xx, -1, dead.d);
			board[shark.y][shark.x] = -1; // 상어가 위치한 곳을

			selectDead();

			deadList.remove(deadList.size() - 1);
			shark = new Fish(save);
			// deep copy
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					board[i][j] = copyBoard[i][j];
				}
			}
			fishList.clear();
			copyFishList.forEach(f -> fishList.add(new Fish(f)));

		}
	}

	static void fishMove() {
		for (int i = 1; i < fishList.size(); i++) {
			Fish now = fishList.get(i);
			if (deadList.contains(now.no))
				continue;
			int y = now.y;
			int x = now.x;
			int d = now.d; // 초기 방향
			while (true) {
				int yy = y + dirY[now.d];
				int xx = x + dirX[now.d];

				if (yy >= 4 || xx >= 4 || yy < 0 || xx < 0 || board[yy][xx] == -1) {
					now.d += 1;
					now.d %= 8;
					if (now.d == d) { // 한바퀴 돌았음
						break;
					}
					continue;
				}

				if (board[yy][xx] == 0) { // 빈 칸
					board[now.y][now.x] = 0;
					now.y = yy;
					now.x = xx;
					board[now.y][now.x] = now.no;
				} else { // 물고기가 있다
					int ty = now.y;
					int tx = now.x;
					Fish target = fishList.get(board[yy][xx]);
					now.y = target.y;
					now.x = target.x;
					board[now.y][now.x] = now.no;
					target.y = ty;
					target.x = tx;
					board[target.y][target.x] = target.no;
				}
				break;
			}
		}
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 이번 기회에 객체를 Deep Copy 하는 것에 대해 경각심을 갖게 되었다.

   . 생성한 객체를 Deep Copy 할 때는 무조건 새로운 객체를 만들어 동일한 값을 채워준다.

2. Deep Copy가 안 되는 것을 인지하지 못 하여 푸는데 시간이 너무 오래 걸렸다.