[BOJ] 23290. 마법사 상어와 복제 - JAVA

🔗 문제

23290번: 마법사 상어와 복제

 

👨🏻‍💻 풀이 및 코드

문제 유형 및 난이도 : 구현, 시뮬레이션 / G1

 

풀이

시뮬레이션 문제라서 차근차근 해결하면서 풀었다.

 

1. 입력

 

① 입력으로 들어오는 물고기들의 위치와 방향을 List 에 담는다.

class Fish {
    int x, y;	// 위치
    int dir;	// 방향
}

List<Fish> fishes = new ArrayList<>();
fishes.add(new Fish(x, y, dir);

 

② 상어의 위치를 받는다. 

Fish shark = new Fish(x, y, -1); 	// 상어의 방향은 없으므로 -1

 

 

2. 복제 및 물고기 이동

static void copyAndMoveFish() {
		// 이동 전의 물고기들을 저장해둘 리스트
        List<Fish> rootFishes = new ArrayList<>();	

        // 이동 후의 물고기들을 저장할 배열
        List[][] map = new List[N][N];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                map[i][j] = new ArrayList<>();
            }
        }

        // 물고기들 이동
        for(Fish fish : fishes) {
        	// 이동하기 전에 복사
            rootFishes.add(new Fish(fish.x, fish.y, fish.dir);		

            boolean isMoved = false;
            int oriDir = fish.dir;

            do {
                int nx = fish.x + dx[fish.dir];
                int ny = fish.y + dy[fish.dir];

                // 격자를 벗어나거나, 냄새가 있거나, 상어가 있는 위치라면 회전
                if(nx<0 || nx>=N || ny<0 || ny>=N || smell[nx][ny] > 0 || (nx==shark.x) && (ny==shark.y)) {
                    fish.dir = (fish.dir-1+8)%8;
                    continue;
                }

                map[nx][ny].add(fish.dir);
                isMoved = true;
                break;
            } while(oriDir != fish.dir);

            if(!isMoved) {
                map[fish.x][fish.y].add(fish.dir); 
            }
        }
}

 

3. 상어 이동

 

① 상어가 이동 가능한 방향([상,상,상], [상,상,하] ... ) 을 우선순위대로 정렬하기 위한 클래스 선언

static class Dir implements Comparable<Dir>{
    int cnt;				// 물고기의 총 횟수
    int[] direction;		// 이동 방향
    int num;				// 사전순

    Dir(int cnt, int[] direction, int num) {
        this.cnt = cnt;
        this.direction = direction;
        this.num = num;
    }

    @Override
    public int compareTo(Dir o) {
        if(cnt == o.cnt) {
            return this.num - o.num;		// 작은순서
        }
        return o.cnt - this.cnt;			// 큰 순서
    }
}

 

② 상어 이동

static void moveShark() {
    // 상어가 이동가능한 경로들을 담아 정렬할 배열
    List<Dir> directions = new ArrayList<>();	
    
    // 상어가 이동할 경우의 수는 0 ~ 4^3(64)
    outer: for(int i=0; i<(int)(Math.pow(4, 3)); i++) {
    	// 4진수로 변환 (ex) 0 → 000(4), 63 → 333(4) : [상, 상, 상], [우, 우, 우]
        int[] dir = getQuaternary(i);
        
        // 먹는 물고기의 수
        int cnt = 0;	
        int nx = shark.x, ny = shark.y;
        // 한번 지나쳐온 경로는 물고기가 없기 때문에 방문 표시
        boolean[][] visited = new boolean[N][N];
        
        for(int j=0; j<3; j++) {
            nx += ddx[dir[j]];
            ny += ddy[dir[j]];
			
            // 격자 밖을 벗어나면 이동 불가능한 경로
            if(nx<0 || nx>=N || ny<0 || ny>=N) continue outer;
            if(visited[nx][ny]) continue;
            visited[nx][ny] = true;
            cnt += map[nx][ny].size();
        }

        directions.add(new Dir(cnt, dir, i));
    }
    
    Collections.sort(directions);
    
    // 상어가 이동할 경로
    Dir dir = directions.get(0);
    int nx = shark.x, ny = shark.y;
    for(int i=0; i<3; i++) {
        nx += ddx[dir.direction[i]];
        ny += ddy[dir.direction[i]];

        if(!map[nx][ny].isEmpty()) {
            smell[nx][ny] = 3;		// 냄새 남김
            map[nx][ny].clear();	// 모두 제거
        }
    }

    shark.x = nx; shark.y = ny;
}

 

③ 4진수 변환

static int[] getQuaternary(int num) {
    int[] res = new int[3];
    int idx=2;
    while(num > 0) {
        res[idx--] = num%4;
        num/=4;
    }

    return res;
}

 

 

4. 냄새 제거

static void removeSmell() {
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(smell[i][j]!=0) {
                smell[i][j]--;
            }
        }
    }
}

 

 

5. 복제 완료

static void magicSum() {
		// 물고기들 초기화
        fishes.clear();

        //이동 전 물고기들 담기
        for(Fish fish : rootFishes) {
            fishes.add(fish);
        }

        // 이동 후 물고기들 담기
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j].isEmpty()) continue;
                for(int k=0; k<map[i][j].size(); k++) {
                    fishes.add(new Fish(i, j, (int)map[i][j].get(k)));
                }
            }
        }
}

 

느낀 점

틀린 부분

① 물고기들 이동하기 전에 rootFishes에 담아둘 때 fish 를 그대로 담아서 틀렸다. 이동을 시작하면 방향을 바꾸기 때문에 rootFishes 도 변경이 된다. 항상 객체때문에 틀리고 애를 먹는 것 같다. 

for(Fish fish : fishes) {
    // 복제 -> 여기서 rootFishes에 fish 를 그대로 담아서 틀렸다. 아래에서 fish.dir를 변경하기 때문
    rootFishes.add(new Fish(fish.x, fish.y, fish.dir));
}

---

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_23290_마법사상어와복제_sol2 {
	
	final static int N = 4;
	static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};	// ←, ↖, ↑, ↗, →, ↘, ↓, ↙
	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] ddx = {-1, 0, 1, 0};	// 상 좌 하 우
	static int[] ddy = {0, -1, 0, 1};
	static List[][] map;
	static Fish shark;
	static int[][] smell;
	static List<Fish> rootFishes;
	static List<Fish> fishes;
	
	static class Fish {
		int x, y, dir;
		
		Fish(int x, int y, int dir) {
			this.x = x; 
			this.y = y;
			this.dir = dir;
		}
	}
	
	static class Dir implements Comparable<Dir>{
		int cnt;
		int[] direction;
		int num;
		
		Dir(int cnt, int[] direction, int num) {
			this.cnt = cnt;
			this.direction = direction;
			this.num = num;
		}
		
		@Override
		public int compareTo(Dir o) {
			if(cnt == o.cnt) {
				return this.num - o.num;		// 작은순서
			}
			return o.cnt - this.cnt;			// 큰 순서
		}
	}
	
	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_23290.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int M = Integer.parseInt(st.nextToken());	// 물고기의 수
		int S = Integer.parseInt(st.nextToken()); 	// 연습한 횟수
		
		fishes = new ArrayList<>();		// 현재 있는 물고기
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			int d = Integer.parseInt(st.nextToken())-1;
			
			fishes.add(new Fish(x, y, d));
		}
		st = new StringTokenizer(br.readLine(), " ");
		shark = new Fish(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1, -1);
		
		rootFishes = new ArrayList<>();	// 복제되는 물고기
		smell = new int[N][N];	// 냄새
		for(int s=1; s<=S; s++) {
			// 복제, 물고기 이동
			copyAndMoveFish();
			
			// 상어 이동
			moveShark();
			
			// 냄새제거
			removeSmell();
 			
			// 복제 완료
			magicSum();
		}
		
		System.out.println(fishes.size());
		br.close();
	}
	
	static void copyAndMoveFish() {
		rootFishes.clear();
		// 물고기 이동
		map = new List[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = new ArrayList<>();
			}
		}
		for(Fish fish : fishes) {
			// 복제 -> 여기서 rootFishes에 fish 를 그대로 담아서 틀렸다. 아래에서 fish.dir를 변경하기 때문
			rootFishes.add(new Fish(fish.x, fish.y, fish.dir));
			
			boolean isMoved = false;
			int oriDir = fish.dir;
			
			do {
				int nx = fish.x + dx[fish.dir];
				int ny = fish.y + dy[fish.dir];
				
				if(nx<0 || nx>=N || ny<0 || ny>=N || smell[nx][ny] > 0 || (nx==shark.x) && (ny==shark.y)) {
					fish.dir = (fish.dir-1+8)%8;
					continue;
				}
				
				map[nx][ny].add(fish.dir);
				isMoved = true;
				break;
			} while(oriDir != fish.dir);
			
			if(!isMoved) {
				map[fish.x][fish.y].add(fish.dir); 
			}
		}
	}
	
	static void moveShark() {
		// 상어 이동
		List<Dir> directions = new ArrayList<>();
		outer: for(int i=0; i<(int)(Math.pow(4, 3)); i++) {
			int[] dir = getQuaternary(i);
			int cnt = 0;		// 먹는 물고기의 수
			int nx = shark.x, ny = shark.y;
			boolean[][] visited = new boolean[N][N];
			for(int j=0; j<3; j++) {
				nx += ddx[dir[j]];
				ny += ddy[dir[j]];
				
				if(nx<0 || nx>=N || ny<0 || ny>=N) continue outer;
				if(visited[nx][ny]) continue;
				visited[nx][ny] = true;
				cnt += map[nx][ny].size();
			}
			
			directions.add(new Dir(cnt, dir, i));
		}
		Collections.sort(directions);
		
		Dir dir = directions.get(0);
		int nx = shark.x, ny = shark.y;
		for(int i=0; i<3; i++) {
			nx += ddx[dir.direction[i]];
			ny += ddy[dir.direction[i]];
			
			if(!map[nx][ny].isEmpty()) {
				smell[nx][ny] = 3;		// 냄새 남김
				map[nx][ny].clear();	// 모두 제거
			}
		}
		
		shark.x = nx; shark.y = ny;
	}
	
	static void removeSmell() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(smell[i][j]!=0) {
					smell[i][j]--;
				}
			}
		}
	}
	
	static void magicSum() {
		fishes.clear();
		for(Fish fish : rootFishes) {
			fishes.add(fish);
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j].isEmpty()) continue;
				for(int k=0; k<map[i][j].size(); k++) {
					fishes.add(new Fish(i, j, (int)map[i][j].get(k)));
				}
			}
		}
	}

	
	static int[] getQuaternary(int num) {
		int[] res = new int[3];
		int idx=2;
		while(num > 0) {
			res[idx--] = num%4;
			num/=4;
		}
		
		return res;
	}
	

}

 

---

Reference

-