[BJ] 16236. 아기상어

[BJ] 16236: 아기상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

 

한달만에 다시 풀어봤는데 다시 푼 방법이 더 편하고 시간도 훨씬 단축된다.

 

✔ 문제 조건

1. N * N 크기, 물고기 M마리, 상어 1마리
   • map[][]
     0 : 빈칸
     1 ~ 6: 물고기 크기
     9 : 아기 상어
2. 상어
   • 최초 크기: 2
   • 상 하 좌 우 중 한칸 이동
   • 1초에 한 칸 이동
     • 상어 > 물고기 : 지나갈 수 있음 / 먹을 수 있음
     • 상어 = 물고기 : 지나갈 수 있음 / 먹을 수 x
     • 상어 < 물고기 : 지나갈 수 x / 먹을 수
   • 먹을 수 있는 물고기 1마리 : 그 위치로 먹으러 간다
   • 먹을 수 있는 물고기 2마리 이상 :
     가장 가까운 -> 가장 위 -> 가장 왼쪽 물고기 택
   • 물고기를 먹고나면 :
     상어 : 먹은 횟수 +1 ,
     먹은 횟수 == 상어 크기면 -> 상어 크기+1, 먹은 횟수 = 0
     물고기 칸 : 9
3. 물고기
   • 최초 크기 : 주어짐
4. 아기 상어가 몇 초 동안 물고기를 잡아먹을 수 있는지 출력

 

✔ 접근 과정

1. 물고기 class: 상어와의 거리, r, c 순의 정렬 기준
2. findFish() 
   1. map을 탐색하며 살아있고 & 현재 상어보다 작은 물고기를 list를 넣는다.
      • list에 넣을 때 현재 상어 위치와의 거리도 계산하여 넣는다.
      • 거리 계산 시 중간에 지나갈 수 없는 크기의 물고기를 피해가며 계산한다. (bfs 이용)
      • list가 비었다면 종료
   2. list 정렬
   3. 가장 앞에 있는 물고기 택
      • 상어가 이동: 상어의 r, c 변경
        map[상어r][상어c] = 0
      • 해당 물고기 칸 : map[물고기r][물고기c] = 9
      • 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가
3. 몇 초 지났는지 출력

 

✔ 주의할 점

1. 1초에 한 칸씩 움직이기 때문에, 결국 상어와 먹으러 가는 물고기들간의 거리의 합을 구한다.이때 거리를 bfs로 구할 때, 상어 위치에서 상어 위치까지는 0초 걸리기 때문에 방문 배열 값들을 전부 -1로 초기화 해준 후 상어 위치만 0으로 바꾸어야 한다.
   또한 이미 방문한 곳인지 확인할 때는 v[nr][nc]!=0인지를 확인하는게 아니라 -1인지를 확인하여야 한다.
2. 상어가 방문할 수 없는 곳이면 최대값을 반환하여 list에 넣지 않는다.
3. 상어에게 먹힌 물고기 위치를 0으로 바꾸면 안된다. 그 자리는 빈 칸이 아니라 상어가 이동한 칸이기 때문에 9로 바꾸어야 한다. 상어가 떠난 위치를 0으로 만들어야 한다.
4. 한달 전에 풀었던 방법인
   물고기 list를 만들어서, 죽었는지 여부를 boolean 변수로 확인하며 사용하는 것 보다 map에서 그때 그때 살아있는 물고기만 확인하는게 더 편하다.

import java.io.*;
import java.util.*;
// 210420

public class Main_BJ_16236_아기상어 {
	static int N, sharkR, sharkC, sharkSize, eatCnt, res; // 1초에 1칸 이동
	static int[][] map;
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, -1, 0, 1};
	
	static class Fish implements Comparable<Fish>{
		int r, c, dist;

		public Fish(int r, int c, int dist) {
			this.r = r;
			this.c = c;
			this.dist = dist;
		}
		
		@Override
		public int compareTo(Fish o) {
			if(this.dist == o.dist) {
				if(this.r == o.r) {
					return Integer.compare(this.c, o.c);
				}
				return Integer.compare(this.r, o.r);
			}
			return Integer.compare(this.dist, o.dist);
		}
	}
	
	static class Pos {
		int r, c;
		public Pos(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input_BJ_16236_아기상어.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
	
		N = stoi(br.readLine());
		map = new int[N][N];
		res = 0;
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				map[i][j] = stoi(st.nextToken());
				if(map[i][j]==9) {
					sharkR = i;
					sharkC = j;
					sharkSize = 2;
					eatCnt = 0;
				}
			}
		}		
		
		solve();
		br.close();
	}
	
	static void solve() {
		
		while(true) {
			boolean help = findFish();
			if(help) break;			
		}
		
		System.out.println(res);
	}
	
	static boolean findFish( ) {
		// 현재 상어 위치에서 먹을 수 있는 물고기들과의 거리 계산
		ArrayList<Fish> fishList = new ArrayList<Fish>();
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j]==0 || map[i][j]==9 || map[i][j] >= sharkSize) continue;
				int dist = getDist(i, j);
				if(dist == Integer.MAX_VALUE) continue;
				fishList.add(new Fish(i, j, dist));
			}
		}
		
		if(fishList.size()==0) return true;

		// 정렬하여 가장 가까운 -> 위에 있는 -> 왼쪽에 있는 물고기 찾기
		Collections.sort(fishList);
		
		Fish f  = fishList.get(0);
		
		// 상어가 이동
		res += f.dist;
		map[sharkR][sharkC] = 0;
		sharkR = f.r;
		sharkC = f.c;
		
		// 상어가 먹는다
		map[sharkR][sharkC] = 9; // 0 하면 안됨!!
		
		// 상어 크기 증가
		++eatCnt;
		if(eatCnt == sharkSize) {
			++sharkSize;
			eatCnt = 0;
		}
		
		return false;
	}
	
	static int getDist(int r, int c) {
		// 현재 상어가, 자신보다 큰 물고기를 피해가며
		// 해당 물고기까지 도달하기까지의 거리
		
		int[][] v = new int[N][N];
		for(int i=0; i<N; i++)
			Arrays.fill(v[i], -1);
		Queue<Pos> q = new ArrayDeque<Pos>();
		
		// 상어 위치
		v[sharkR][sharkC] = 0; // 시작 거리는 0
		q.offer(new Pos(sharkR, sharkC));
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			if(cur.r == r && cur.c == c) {
				return v[cur.r][cur.c];
			} 
			
			for(int d=0; d<4; d++) {
				int nr = cur.r + dr[d];
				int nc = cur.c + dc[d];
				
				// v[nr][nc]!=0 아님!!
				if(nr<0 || nr>=N || nc<0 || nc>=N || 
						map[nr][nc]>sharkSize || v[nr][nc]!=-1) continue;
				
				v[nr][nc] = v[cur.r][cur.c] + 1;
				q.offer(new Pos(nr, nc));
			}
			
		}
		return Integer.MAX_VALUE; // 도달할 수 없음
	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}

 

 

# 21/03/17 풀이

 

✔ 접근 과정

1. 현재 남아있는 물고기들을 ArrayList에 저장한다.
2. 2-1. ArrayList가 비어있다면 남은 물고기가 없는 것이므로 종료한다.
   2-2. 1) ArrayList의 물고기들에 대하여 현재 상어와의 거리를 bfs로 계산한다.
          2) 계산 후 거리순 -> 행 번호 작은 것 -> 열 번호 작은 것 순으로 정렬한다. 
3. 거리가 제일 짧은 물고기의 거리가 0이면 이동할 수 없는 것이기 때문에 그 다음으로 짧은 물고기를 택한다
4. 선택된 물고기로 아기 상어가 이동한다.
   1) 선택된 물고기 칸을 0으로 만든다.
   2) 상어의 위치를 선택된 물고기 칸으로 이동시킨다.
   3) 상어가 물고기를 먹은 횟수를 늘린다. (cnt+1)
     늘리고 난 후 먹은 횟수가 현재 상어의size와 같아진다면size+1,cnt=0으로 수정한다.
   4)res에 선택된 물고기와 상어와의 거리를 더한다
   5) 상어를 이동시키지 않았다면 먹을 수 있는 물고기가 없는 것이다. (ArrayList 내의 모든 물고기들의 거리값이 0인 경우다.) 이럴 경우 종료한다.
5. 1로 돌아가 다음으로 먹을 물고기들을 탐색한다.

✔ 주의할 점

• bfs로 거리를 탐색할 시.
  시작 위치로visited처리를 해야 시작 위치로 돌아오지 않는다. 그러나visited배열을 거리 계산용으로도 쓰고 있기 때문에 시작 위치의 거리를 1로 처리해버리면 전체적으로 거리값이 1씩 늘어나게 된다.
  따라서 위치 탐색 시 시작 위치와 같다면 이동하지 않도록 조건문을 추가한다.
• 남아있는 물고기와 상어와의 거리를 계산할때, 단순히 상어와 물고기들의 좌표값을 가지고 길이를 계산해서는 안된다. 중간에 이동할 수 없는 물고기 칸을 피해 갈 때의 거리로 계산해야 한다.
• 물고기와 상어들과의 거리값을 계산했을 때 거리가 모두 0인 경우가 있다. 물고기가 남아있지만 경로 중간에 이동할 수 없는 물고기 칸이 있어 상어가 물고기까지 갈 수 없는 경우다. 이럴 경우 종료시키지 않으면 무한 루프로 시간 초과가 발생한다.

import java.io.*;
import java.util.*;
// 210317

public class Main_BJ_16236_아기상어 {
    static int N;
    static int[][] map;
    static Shark shark;
    static ArrayList<Fish> fishList, smallerList;
    static int res;

    static int stoi(String str) {
        return Integer.parseInt(str);
    }

    static class Pos {
        int r, c;
        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static class Shark {
        int r, c, size=2, cnt=0;

        public Shark(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static class Fish implements Comparable<Fish> {
        int r, c, size, dist;

        public Fish(int r, int c, int size) {
            this.r = r;
            this.c = c;
            this.size = size;
        }

        @Override
        public int compareTo(Fish o) {
            if(this.dist==o.dist) {
                if(this.r==o.r) {
                    return this.c - o.c;
                }
                return this.r - o.r;
            }
            return this.dist - o.dist;

        }

    }

    static void findSmallerFish() {
        smallerList = new ArrayList<>();

        for(Fish f: fishList) {
            // 살아있고 현재 상어보다 크기가 작다면 추가한다.
            if(map[f.r][f.c]>0 && f.size<shark.size) {
                smallerList.add(f);
            }
        }
        goEat();
    }

    static void goEat() {

        if(smallerList.size()==0) {
            return; // 먹을 고기 없음
        }

        for(Fish f: smallerList) {
            f.dist = bfs(shark, f);
            // 중간에 이동할 수 없는 경우를 고려하여 거리 계산
        }

        Collections.sort(smallerList);

        boolean flag = false;
        for(Fish f: smallerList) {
            if(f.dist==0) continue; // 거리가 0면 이동할 수 없다.

            res += f.dist; // 이동
            map[f.r][f.c] = 0; // 물고기가 먹혀서 없어짐
            map[shark.r][shark.c] = 0; // 상어가 떠남
            shark.r = f.r; shark.c = f.c; // 상어 이동
            shark.cnt += 1;
            if(shark.cnt == shark.size) {
                shark.size += 1;
                shark.cnt = 0;
            }
            flag=true;
            break;

        }

        if(!flag) return; // 거리 안에 먹을 수 있는 물고기가 없으면 종료
        else findSmallerFish(); // 다음 물고기를 찾는다.

    }

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int bfs(Shark s, Fish f) {

        int[][] visited = new int[N][N];
        Queue<Pos> q = new ArrayDeque<>();

        // visited[s.r][s.c] = 1;
        q.offer(new Pos(s.r, s.c));

        while(!q.isEmpty()) {
            Pos p = q.poll();

            for(int d=0; d<4; d++) {
                int nr = p.r + dr[d];
                int nc = p.c + dc[d];

                if(nr<0 || nr>=N || nc<0 || nc>=N || map[nr][nc]>s.size) continue;
                if(nr==s.r && nc==s.c) continue;

                if(visited[nr][nc]>0) {// 이미 방문 했는데
                    if(visited[nr][nc] > visited[p.r][p.c] + 1) { // 더 적은 수로 방문할 수 있을 때
                        visited[nr][nc] = visited[p.r][p.c] + 1;
                        q.offer(new Pos(nr, nc));
                    } 
                } else  {
                    visited[nr][nc] = visited[p.r][p.c] + 1;
                    q.offer(new Pos(nr, nc));
                }

            }
        }
        return visited[f.r][f.c];

    }

    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input_16236_아기상어.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = stoi(br.readLine());
        map = new int[N][N];
        fishList = new ArrayList<>();
        res = 0;

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++) {
                map[i][j] = stoi(st.nextToken());
                if (map[i][j]==9) {
                    shark = new Shark(i, j);
                } else if (map[i][j]>0) {
                    fishList.add(new Fish(i, j, map[i][j]));
                }
            }
        }

        findSmallerFish();
        System.out.println(res);

        br.close();
    } //
}