[백준 16236] 아기상어
문제
NXN (2 <= N <= 20)
물고기 M 마리 크기 (1~6)
상어 1마리(초기 크기 2), 1초에 상하좌우 인접 한칸씩 이동가능
자신보다 작은 물고기 먹을 수 있음
작거나 같은 물고기 있는 칸 지나갈 수 있음
먹을 수 잇는 물고기 없으면 끝
먹을 수 있는 물고기 1마리 이상 -> 1. 가까운 물고기부터, 2. 가장 위에 있는 물고기부터, 3. 가장 왼쪽에 있는 물고기부터 먹는다
이동과 동시에 물고기를 먹음(빈칸됨)
자신의 크기만큼의 물고기 수를 먹을 때 1씩 증가
기존 코드
static int n;
static int[][] map;
static boolean[][] visited;
//상 0,-1 좌-1,0 우1,0 하0,1
static int[] dx = new int[]{0,-1,1,0};
static int[] dy= new int[]{-1,0,0,1};
static int result =0;
static class Shark{
int x;
int y;
int size;
int eat;
int time;
public Shark(int x, int y, int size, int eat, int time){
this.x = x;
this.y = y;
// 만약 먹은 물고기 수가 상어 크기 수와 같다면 먹은 물고기수 0, 상어크기 +1/
// 더 작다면 먹은 물고기수 +1, 상어크기 동일)
if(eat == size) {
this.eat = 0;
this.size = size+1;
} else {
this.eat = eat;
this.size = size;
}
this.time = time;
}
private void setLocation(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
map = new int[n][n];
visited = new boolean[n][n];
Shark first = new Shark(0,0,2,0,0);
for(int i =0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
int num = Integer.parseInt(st.nextToken());
if(num == 9) {
first.setLocation(j,i);
map[i][j]= 0;
} else map[i][j]= num;
}
}
//풀이
//상어객체 : 9인곳 좌표 + 상어 크기(2) + 먹은 물고기 수, result = 0; / time 넣음
//visited 배열 필요
bfs(first);
System.out.println(result);
}
static void bfs(Shark first){
Queue<Shark> queue = new LinkedList<>();
queue.offer(first);
visited[first.y][first.x] = true;
while (!queue.isEmpty()){
Shark shark = queue.poll();
//상 , 좌 , 하 , 우 순으로 돌면서 방문 안한곳 방문, 물고기 탐색
for(int i =0; i<4; i++) {
int changeX = shark.x + dx[i];
int changeY = shark.y + dy[i];
//배열 밖 벗어나면 다음턴
if(changeX <0|| changeX>= n|| changeY<0|| changeY>=n) {
continue;
} //방문 안했고 물고기 크기가 상어 크기보다 작으면 지나감
if(!visited[changeY][changeX] && map[changeY][changeX] <= shark.size) {
visited[changeY][changeX] = true;
//해당좌표 0일 시 Shark에 좌표만 변경
if(map[changeY][changeX] ==0) {
queue.offer(new Shark(changeX,changeY,shark.size, shark.eat, shark.time+1));
}
//물고기 발견 시 (해당 좌표 0이 아닐 시)
if(map[changeY][changeX] !=0) {
// 같으면 -> 상어 객체 좌표 해당 좌표로 변경 , 크기, 먹은 물고기 수 , time+1
if(map[changeY][changeX] == shark.size){
queue.offer(new Shark(changeX,changeY,shark.size, shark.eat, shark.time+1));
}
// 물고기 크기가 상어 크기보다 작으면 먹음, ->
if(map[changeY][changeX] < shark.size){
// 상어 객체 해당 좌표로 변경, 크기, 먹은 물고기수 +1 해당 그래프 0으로 바꿈
// time+1 result = time+1로 갱신
// visited 배열 초기화
result = shark.time +1;
map[changeY][changeX] = 0;
resetVisited();
bfs(new Shark(changeX,changeY,shark.size, shark.eat +1, shark.time+1));
}
}
}
}
}
}
static void resetVisited() {
visited = new boolean[n][n];
}
기존코드 로직
1)BFS를 상 , 좌, 우 , 하 순으로 돌다가 map[y][x] < shark.size인 물고기를 만나면 → 그 즉시 result = time + 1 하고
2) map[y][x] = 0 해서 먹은 뒤,
3) visited 초기화, bfs()를 재귀 호출해서 상어를 새 위치에서 다시 BFS 시작
같은 거리 안에 여러 마리의 먹을 수 있는 물고기가 있다면, 그 중 가장 위쪽(y가 작고), 가장 왼쪽(x가 작은) 물고기를 먹어야 한다는 조건 때문에 상 , 좌, 우 , 하 순으로 돌면 무조건 위쪽, 왼쪽인 물고기 순으로 발견할 것이라고 생각했다.
그러나 특정 테스트케이스에서 정답과 다르게 나왔고,
문제가 뭔지 파악해보았다.
기존코드의 논리적 오류
내 코드에서 문제되는건 상,좌,우,하 순으로 돌더라도 위쪽, 왼쪽인 물고기 순으로 발견하지 않는 경우가 있다는 것이다.
다음과 같은 경우를 예로 들어보겠다
🦈 현재 위치: (0, 2)
현재 시간: 10
상어 크기: 4
[map은 다음과 같다]
5 4🦈0 3 4
4 3 0 3 4 5
3 2 0 5 6 6
2 0 0 3 4 5
3 2 0 6 5 4
6 6 6 6 6 6
이때 먹을 수 있는 물고기중(크기 3이하) 가장 가까운 물고기는
(1,1)
(0,4)
(1,4)
3마리며 이들과의 거리는 2이다
이중 가장 위쪽에 있는 물고기는 0,4에 있는 물고기이다. 따라서 다음 순위에 이를 가장 먹어야 한다.
그러나 내 코드의 경우에는
상 좌 우 하 순으로 그래프를 탐색하지만, 상단으로 갈 수 있는 경우는 막혀있으니
상어는 좌측인 1,0을 가장 먼저 지나가며 탐색할 것이다.
그렇기에 가장 먼저 도달하게 되는것은 우선순위가 높은 0,4가 아닌 1,1이다.
이외에도 큰 물고기가 있어서 돌아가야 하거나 여러 지형에 따라서 무조건 상, 우, 좌, 하의 순서를 지키며 탐색할 수 있는 보장이 없다.
0 0 0 0 0 0
0 0 9 1 0 0
1 0🦈 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
따라서 각 시간마다 탐색하며 먹을 수 있는 가장 가까운 물고기를 넣어준 후 우선순위에 맞는 물고기를 먹는 방식으로 탐색하는 것이 정확하다.
정답 코드
static void bfs(Shark first){
Queue<Shark> queue = new LinkedList<>();
visited = new boolean[n][n];
queue.offer(first);
visited[first.y][first.x] = true;
List<Shark> fishes = new ArrayList<>(); //먹을 수 있는 물고기 후보 리스트
while (!queue.isEmpty()){
Shark shark = queue.poll();
//돌면서 방문 안한곳 방문, 물고기 탐색
for(int i =0; i<4; i++) {
int changeX = shark.x + dx[i];
int changeY = shark.y + dy[i];
//배열 밖 벗어나면 다음턴
if(changeX <0|| changeX>= n|| changeY<0|| changeY>=n) {
continue;
} //방문 안했고 물고기 크기가 상어 크기보다 작으면 지나갈 수 있음
if(!visited[changeY][changeX] && map[changeY][changeX] <= shark.size) {
visited[changeY][changeX] = true;
Shark next = new Shark(changeX, changeY, shark.size, shark.eat, shark.time + 1); //다음 상어객체 생성
//해당좌표에 물고기가 있고, 먹을수 있는 크기인 경우
if(map[changeY][changeX] > 0 && map[changeY][changeX] < shark.size) {
fishes.add(next); //먹을 수 있는 물고기 후보 따로 저장
} else { // 해당 좌표에 물고기가 없거나 상어랑 크기가 같아서 지나갈 수 만 있는경우
queue.offer(next); //큐에 넣어서 계속 탐색
}
}
}
}
if(fishes.isEmpty()) {
return; // 더이상 먹을 물고기가 없음
}
fishes.sort((a,b) -> {
if(a.time != b.time) return a.time - b.time; //1. 시간 오름차순 정렬 : 가장 가까운 순
if(a.y != b.y) return a.y - b.y; //2.y값 오름차순 정렬 : 가장 위에 있는 순
return a.x - b.x; //3. x값 오름차순 정렬: 가장 왼쪽에 있는 순
});
Shark target = fishes.get(0);
map[target.y][target.x] = 0; // 물고기 먹음
result = target.time; // 시간 갱신
bfs(new Shark(target.x, target.y, target.size, target.eat + 1, target.time)); //새 bfs 시작
}
정답 로직
bfs를 돌며 먹을 수 있는 모든 물고기 List에 담음
List에 있는 물고기 중 우선순위별로 정렬(1. 가까운순, 2. 위에있는 순 3. 왼쪽에 있는 순)
가장 가까운 물고기를 먹고 result 갱신 후 다시 bfs 순환
위 코드로 변경하니 문제를 맞을 수 있었다.
우선순위 큐
그리고 이런 문제에서 쓸수 있는 개념 중 하나는 우선순위 큐이다.
위 문제에서는 전부 탐색 해서 담은 후 한번만 정렬해서 1마리만 먹고 끝이라 리스트 를 정렬하는것과 큰 성능차이는 없겠지만,
1) 우선순위 조건이 있는 정렬 문제
2 )실시간으로 가장 작은 값/큰 값을 빠르게 꺼내야 할 때
우선순위 큐를 쓰면 쉽게 풀 수 있는 문제들이 많으니 알아두면 좋겠다.
우선순위 큐란, 일반적인 큐처럼 먼저 들어온 순서대로 나오는 큐가 아니라, 우선순위가 높은것이 먼저 나오는 큐다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
pq.offer(1);
pq.poll() 하면?
➡ 작은 수부터 나옴 (기본 정렬 기준: 오름차순)
출력 순서:
1 → 2 → 5 → 8
why? PriorityQueue는 내부적으로 자동 정렬된 힙(Heap) 구조이기 때문
- 값을 넣으면 → 자동 정렬
- 값을 꺼내면 → 항상 우선순위 가장 높은 값이 먼저 나옴
큐 정의 시, 객체에 우선순위를 줄 수도 있다.(Comparator 사용)
ex ) 상어 객체를 거리 → y → x 우선순위로 정렬하고 싶다면
class Shark {
int y, x, time;
Shark(int y, int x, int time) {
this.y = y;
this.x = x;
this.time = time;
}
}
PriorityQueue<Shark> pq = new PriorityQueue<>(
(a, b) -> {
if (a.time != b.time) return a.time - b.time;
if (a.y != b.y) return a.y - b.y;
return a.x - b.x;
});이제 pq.offer(shark) 해주면
pq.poll() 했을 때 →
거리 가장 짧고 → 위쪽에 있고 → 왼쪽에 있는 상어가 자동으로 나옴.
이렇게 fishes List를 매번 정렬하는 대신 fishes 를 해당 조건의 우선순위 큐로 선언해 주는 방법으로 조금 더 효율적으로 문제를 풀 수 있을 것이다.