[백준] 23290. 마법사 상어와 복제 (자바 JAVA)

[ 문제 ]  [백준] 23290. 마법사 상어와 복제 (자바 JAVA)

 

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

23290번: 마법사 상어와 복제

---

# 접근 방법 및 풀이 

 

• 일단 내가 다른 사람들 풀이와 다른점은 물고기 리스트를 3차원 배열로 표현하지 않고 HashMap으로 관리했다.
• static HashMap<Point, List<Integer>> fish; 를 선언해서 key값에 Point 클래스로 물고기의 위치 Point.x, Point.y로 만들고, 해당 위치에 여러개의 물고기가 있을 수 있으므로 value는 List로 사용했다.
• fish 맵을 3차원 맵으로 관리할 수도 있지만, 물고기를 제거할때 key값이 물고기가 있는 위치이므로 한번에 remove로 제거할 수 있어서 사용했다. -> 근데 시간적인 부분에서 3차원으로 바꿔서 풀어볼 예정 
• 무튼 마법사 상어 연습 한번의 로직 순서는 다음과 같다.
• 1. 물고기 현재 위치 복사 - copyFish()
• 2. 물고기 이동 - moveFish()
• 3. 상어 이동 - moveShark()
• 4. 물고기 냄새 생기고, 상어위치 변경 - makeSmell()
• 5. 물고기 냄새 제거 - removeSmell()
• 6. 물고기 복제 - addFish()
• 그리고 각 로직의 구현 방식은 다음과 같다.
• 1. 물고기 현재 위치 복사
  • copy를 새롭게 만들어서 fish를 그대로 clone()
• 2. 물고기 이동
  • 범위를 넘어가지 않고, 상어가 있는 위치가 아니고, 물고기 냄새가 없는 곳으로 이동
  • 이때 중요한건, "이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. " 라는 부분인데, 해석이 애매하다.
  • 청소년 상어를 풀어봤다면 좀 더 쉽게 이해할 수 있는데 주의할건 이부분이다.
  • 총 8가지 방향이 있으므로 현재방향에서부터 45도 반시계 회전하면서 8가지 방향 다 봤는데도 이동할 곳이 없다? 그러면 이동을 하지않는데, 그때 물고기의 방향은 마지막에 살펴본 방향이어야하는가? 라는 점이다.
  • 물고기는 이동하지 않으므로 처음 물고기의 방향 그대로여야한다. 
  • 즉, 이동을 하지 않은 처음 물고기 방향이 ← 라면, 마지막에 본 방향은 ↖ 였을테지만, 이동을 하지 않았으므로 ← 여야한다.
  • 물고기 이동후 이차원 배열 map[][]을 생성해서 이동한 물고기의 수를 표시해주었다.
• 3. 상어 이동  
  • dfs, 백트래킹, 정렬로 풀었다. 가장 중요한 부분이다. 이것 때문에 디버깅 1시간했다.
  • 먼저 생각해볼 점은 상어가 연속 3칸을 이동할때 상어가 왔던 칸을 다시 방문할 수 있는가? 정답은 yes.
  • 상어가  "상하하" 이동한다면 왔던 칸을 방문할 수 있다. 이때 주의할 건 왔던 칸을 방문했을때 이동하면서 물고기를 카운팅했는데 또 카운팅 해서는 안된다. 여기에 대해서 visit처리를 해야하고, 상어가 이동할 칸이 한번도 방문을 하지 않은 곳인지, 방문을 이미 했던 곳인지에 따라서 if-else로 분기를 해주어야한다.
  • 근데 여기서 생겼던 의문은 상어가 왔던 칸을 다시 방문하면 이미 방문한 곳이라 물고기 또 카운팅도 안해주는데 물고기수가 최대값이 되지 않을 것 같은데 왜 굳이 다시 방문해? -> 내가 했던 가장 큰 실수..
  • 이유는 다음과 같은 상황을 떠올려보면 된다. 현재 map[][]에 물고기 수가 다음과 같다.

  • 	1
    	9
    	3

  • 이때 상어의 위치가 물고기 9마리가 있는 위치라고 했을때, "상하하 or 하상상"으로 이동했을 경우에 물고기를 13마리 먹을 수 있다. 
  • 여기서 왔던 곳을 다시 되돌아 가지 않고 인접한 4방향으로 뻗어나갈 경우만 생각하면 1마리 혹은 3마리만 먹는 경우밖에 생각하지 못한다.
  • 그다음 상어가 3번 이동할 수 있는 모든 경우의 수를 Node 클래스를 생성해 sharkList에 넣어주었다.
• 4. 물고기 냄새 생기고, 상어위치 변경
  • 문제에 주어진 조건대로 sharkList를 정렬한다.
  • 상어가 움직인 경로대로 fish에서 물고기를 제거하고 smell[][] 2차원 배열에 냄새가 사라질 시간을 표시해주었다.
  • 이때 냄새가 생긴 현재 시간 t +  2로 했다. 
  • 따라서 1초에 생긴 냄새라면 smell[][] = 3으로 표시했다. 이유는 3초에 사라지기 때문이다.
  • 그리고 해당 냄새가 생긴 자리에 또 새로운 냄새가 생기면 그대로 값을 갱신해주면 된다.
• 5. 물고기 냄새 제거
  • 현재 시간 기준에 사라질 냄새는 0으로 초기화해주었다.
  • smell[][] == t 인것을 0으로 바꿔줌.
• 6. 물고기 복제
  • 기존 fish에 추가
• 자세한건 코드참조

 

 

# 주의할 점 

 

• 상어 이동시 백트래킹 잘하기. 상어가 3칸 연속 이동할 때 자신이 왔던 칸으로 이동할 수 있음. 그때 이미 상어가 한번 방문한 칸에 물고기를 또 카운트 해주면 안되므로 방문체크하기.
• 물고기 이동안 할 경우 방향은 처음 가지고 있던 방향 그대로다.

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class bj23290_마법사상어와복제{
	
	static int M, S, shark_r, shark_c;
	static int ddr[] = {-1, 0, 1, 0};//상좌하우
	static int ddc[] = {0, -1, 0, 1};
	static int dr[] = {0, -1, -1, -1, 0, 1, 1, 1 };
	static int dc[] = {-1, -1, 0, 1, 1, 1, 0, -1};
	static class Node implements Comparable<Node>{
		int fishCnt, r, c;
		String move;
		
		public Node(int r, int c, int fishCnt, String move) {
			this.r = r;
			this.c = c;
			this.fishCnt = fishCnt;
			this.move = move;
		}

		@Override
		public String toString() {
			return "Node [fishCnt=" + fishCnt + ", r=" + r + ", c=" + c + ", move=" + move + "]";
		}
		
		@Override
		public int compareTo(Node o) {
			if(o.fishCnt == this.fishCnt) {
				return this.move.compareTo(o.move);
			}
			return o.fishCnt - this.fishCnt;
		}
		
		
	}
	static List<Node> sharkList;
	static int smell[][];
	static HashMap<Point, List<Integer>> fish;
	static HashMap<Point, List<Integer>> copy;
	static int map[][];
	static boolean visit[][];
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		M = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		fish = new HashMap<>();
		smell = new int[4][4];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int r = Integer.parseInt(st.nextToken()) -1;
			int c = Integer.parseInt(st.nextToken()) -1;
			int d = Integer.parseInt(st.nextToken()) -1;
			fish.computeIfAbsent(new Point(r,c), k -> new ArrayList<>()).add(d);
		}
		st = new StringTokenizer(in.readLine());
		shark_r = Integer.parseInt(st.nextToken())-1;
		shark_c = Integer.parseInt(st.nextToken())-1;
		//입력
		
		//S번 연습
		for (int t = 1; t <= S; t++) {
			copyFish(); //물고기 현재 위치 복사
			moveFish();//물고기 이동
			//상어 이동
			visit = new boolean[4][4];
			sharkList = new ArrayList<Node>();
			moveShark(shark_r, shark_c, 0, 0, "");
			makeSmell(t); //물고기 냄새 만들고 상어 이동
			removeSmell(t);//물고기 냄새 사라져		
			addFish(); //물고기 복제
		}
		
		//물고기 수
		int ans = 0;
		for(Point key : fish.keySet()) {
			ans += fish.get(key).size();
		}
		System.out.println(ans);
	}

	private static void addFish() {
		for (Point key : copy.keySet()) {
			if(fish.containsKey(key)) {
				fish.get(key).addAll(copy.get(key));
			}else {
				fish.put(key, copy.get(key));
			}
		}
	}

	private static void copyFish() {
		copy = new HashMap<Point, List<Integer>>();
		copy = (HashMap<Point, List<Integer>>) fish.clone();
	}
	
	
	private static void moveFish() {
		HashMap<Point, List<Integer>> newfish = new HashMap<Point, List<Integer>>();
		map = new int[4][4];
		for ( Point key : fish.keySet()) {
			List<Integer> list = fish.get(key);
			out: for (int i = 0; i < list.size(); i++) {
				int dir = list.get(i);
				for (int d = 0; d < 8; d++) {
					int nr = key.x + dr[dir];
					int nc = key.y + dc[dir];
					if(nr < 0 || nc < 0|| nr >= 4 || nc >= 4 || smell[nr][nc] != 0 || (nr == shark_r && nc == shark_c)) {
						dir = (dir-1 < 0) ? 7 : dir-1; //45도 방향 바꿈
						continue;
					}
					newfish.computeIfAbsent(new Point(nr, nc), k -> new ArrayList<>()).add(dir);
					map[nr][nc]++;
					continue out;
				}
				newfish.computeIfAbsent(new Point(key.x, key.y), k -> new ArrayList<>()).add(dir);
				map[key.x][key.y]++;
			}
		}
		fish = newfish;
	}
	

	private static void moveShark(int r, int c, int cnt, int fishCnt, String s) {
		if(cnt == 3) {
			List<Point> list = new ArrayList<>();
			Node node = new Node(r, c, fishCnt, s);
			sharkList.add(node);
			return;
		}
		
		for (int d = 0; d < 4; d++) {
			int nr = r + ddr[d];
			int nc = c + ddc[d];
			if(nr < 0 || nc < 0 || nr >= 4 || nc >= 4 )
				continue;
			if(!visit[nr][nc]) {
				visit[nr][nc] = true;
				moveShark(nr, nc, cnt+1, fishCnt+map[nr][nc], s + Integer.toString(d));
				visit[nr][nc] = false;
			}else {
				moveShark(nr, nc, cnt+1, fishCnt, s + Integer.toString(d));
			}
			
		}
	}
	

	private static void makeSmell(int t) {
		Collections.sort(sharkList);
		Node node = sharkList.get(0);
		int nr = shark_r;
		int nc = shark_c;
		for (int i = 0; i < 3; i++) {
			int d = node.move.charAt(i) - '0';
			nr += ddr[d];
			nc += ddc[d];
			if(fish.containsKey(new Point(nr, nc))) {
				
				smell[nr][nc] = t + 2;
				fish.remove(new Point(nr, nc));
			}	
		}
		shark_r = node.r;
		shark_c = node.c;
	}
	

	private static void removeSmell(int t) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if(smell[i][j] == t )
					smell[i][j] = 0;
			}
		}
		
	}
}

 

 

 

REVIEW

어렵다. 어렵고 골드 1 오랜만에 푸니까 정신 확 차려지고.. 3시간만에 풀었는데 정신차려야한다.

물고기 리스트를 HashMap 으로 관리하지말고, 3차원 배열로[][][] 하면 시간 더 줄일 수 있을 것 같다.

왜 자꾸 한 칸에 여러개 값이 들어갈 수 있으면 2차원 배열로만 생각한다거나.. 안되면 HashMap 쓰려고 하는 것 같은데, 물고기가 같은 칸에 오더라도 8가지 방향으로 올 수 있으니까 3차원으로 하면 되는 것을..

2회독으로 풀 때 그땐 3차원으로 풀어봐야지.