BOJ 16236) 아기상어(+bfs 정리)

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

16236번: 아기 상어

 풀이시간 모두 합치면 6~7시간도 넘게 걸린 문제다.ㅜ  풀이과정을 떠올리는데에는 그렇게까지 많은 시간이 걸리지는 않았지만 탐색 문제를 풀때마다 막상 세부 구현에서 문제가 생겨서 정리해놓기 위해 쓴다.

 

 

1. 문제 파악

 

 항상 그렇지만 문제가 길수록 문제의 조건을 읽기X 이해O한  후에 본격적으로 코드를 작성하자. 이 문제를 읽고 정리할 점은 다음과 같다.

- 상어는 자신의 크기보다 작은 크기의 물고기만 먹을 수 있다.

- 상어는 자신과 동일한 크기의 물고기는 지나갈수만 있다.

- 상어의 초기 크기는 2이며, 상어는 자신의 크기에 해당하는 양의 물고기를 먹으면 레벨업한다.

- 상어가 물고기를 먹는 순서는, 가장 가까운 물고기->여러개라면 가장 위의 물고기->여러개라면 가장 왼쪽의 물고기이다.

 

추가로 다음과 같은 사실을 추가로 알 수 있다. (내가 문제풀때 바로 알 순 없고 디버깅하면서 알게 된 것)

+ 상어의 크기는 최대 7로 설정하면 된다. (NxN공간에서 상어의 위치는 9로 나타내지므로 무작정 증가하게 만들면 문제가 발생한다)

+ 상어가 물고기를 먹는 순서 설정을 bfs로 하면 안된다. (남서쪽 물고기가 동동쪽 물고기보다 우선순위가 높아지는 등의 문제가 발생한다)

 

 

 

2. 대략적 설계

 

 상어가 NxN공간을 돌아다니면서 먹을 수 있는 물고기를 모두 잡아먹는데 걸리는 시간(초)를 출력하는 프로그램이다. bfs를 이용하면 상어가 돌아다니는 시간이 자연스럽게 도출될 것이지만, 일반적인 bfs와 다르게 "다음에 먹을 물고기를 탐색하는 과정" 한 번에 한 번의 bfs가 사용될 것이다. 즉, while문을 돌면서 [더 이상 bfs탐색으로 먹을 물고기를 찾을 수 없을 때]까지 [다음에 먹을 물고기를 탐색]하는 bfs를 반복하는 방식으로 설계했다.

 

var 물고기와 상어가 들어갈 공간의 상태: int[N][N]
var visited: boolean[N][N];
var 물고기 정보 리스트: LinkedList<위치 정보>

main() {
  queue.add(맨 처음 상어의 위치)
  visited[상어위치] = true;
  while(더 이상 먹을 수 있는 물고기가 없을 때 까지) {
    var 현재 위치 = queue.remove();
    if(현재 위치==물고기) {
      물고기 정보 저장
    }
    [현재 위치에서 상하좌우 4방향으로 분산하여 검사(4방향 위치정보를 큐에 넣기)]
  }
}

 

 

 

3. 코드 작성

 

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

public class Main
{
    static int N;
    static int[][] board;
    static boolean[][] visited;
    static int size=2;
    static int sizecount=0;
    static int time=0;
    static Queue<Location> queue;
    static LinkedList<Location> fishList;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		for(int i=0; i<N; i++) {
		    String[] line_n = br.readLine().split(" ");
		    for(int j=0; j<N; j++) {
		        board[i][j] = Integer.parseInt(line_n[j]);
		    }
		}
		
		while(true) {
		    int rst = eat();
		    if(rst==-1) {
		        break;
		    }
		    time+=rst;
		}
		
		System.out.println(time);
	}
	
	//한마리 잡아먹기 위해 이동
	public static int eat() {
	    queue = new LinkedList<>();
	    visited = new boolean[N][N];
	    fishList = new LinkedList<>();
        
	    for(int i=0; i<N; i++) {
		    for(int j=0; j<N; j++) {
		        if(board[i][j]==9) {
		            queue.add(new Location(i, j, 0));
		            visited[i][j] = true;
		            return bfs(i, j);
		        }
		    }
		}
		
		return -1;
	}
	
	//리스트에서
	//거리가 동일하면 가장 위에 있는(x가 가장 작은),
	//높이가 동일하면 가장 왼쪽에 있는(y가 가장 작은) 물고기 찾기.
    //리스트에 최소 하나의 물고기가 들어있는 상태라는 전제조건
	public static int moveProperPoint(int cx, int cy) {
            Location compare = fishList.get(0);
            
            for(int i=1; i<fishList.size(); i++) {
                Location fish = fishList.get(i);
                if(fish.x<compare.x) {
                    compare = fish;
                }
                else if(fish.x==compare.x && fish.y<compare.y) {
                    compare = fish;
                }
            }
            
        	sizecount++;
           	if(sizecount==size && size<7) {
                sizecount=0;
                size++;
            }
            board[compare.x][compare.y]=9;
            board[cx][cy]=0;
            
            return compare.time;
	}
	
	public static int bfs(int cx, int cy) {
	    int searchtimeLimit = -1;
	    
	    while(!queue.isEmpty()) {
	        Location loc = queue.remove();
	        int x = loc.x;
	        int y = loc.y;
	        int searchtime = loc.time;
	        
	        //물고기를 먹을 수 있으면 먹고 리스트에 저장
	        //searchtimelimit==-1: 첫접근,
	        //searchtimelimit==searchtime: 두번째이상 접근일 경우 
	        if(0<board[x][y] && board[x][y]<size && (searchtimeLimit==-1 || searchtimeLimit==searchtime)) {

	            if(searchtimeLimit==-1) {
	                searchtimeLimit = searchtime;
	            }
	            fishList.add(new Location(x, y, searchtime));
	            continue;
	        }
	        
	        //상어가 갈 수 있는 경로
	        if(x-1>=0 && board[x-1][y]<=size && !visited[x-1][y]) {
	            queue.add(new Location(x-1, y, searchtime+1));
	            visited[x-1][y] = true;
	        }
	        if(y-1>=0 && board[x][y-1]<=size && !visited[x][y-1]) {
	            queue.add(new Location(x, y-1, searchtime+1));
	            visited[x][y-1] = true;
	        }
	        if(y+1<N && board[x][y+1]<=size && !visited[x][y+1]) {
	            queue.add(new Location(x, y+1, searchtime+1));
	            visited[x][y+1] = true;
	        }
	        if(x+1<N && board[x+1][y]<=size && !visited[x+1][y]) {
	            queue.add(new Location(x+1, y, searchtime+1));
	            visited[x+1][y] = true;
	        }
	    }
	    
	    if(fishList.size()!=0) {
	       // System.out.println(fishList.size());
    	    return moveProperPoint(cx, cy);
	    }
    	else
    	    return -1;
	}
}

class Location {
    int x;
    int y;
    int time;
    
    public Location(int x, int y, int time) {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

 

 

 

- eat()함수는 한번의 bfs가 실행될 때마다 실행되는 함수로, 초기화 등의 로직을 모듈화하기 위해서 함수로 분리하였다. 이름이 의미하듯이 한 번의 bfs는 다음에 잡아먹을 물고기를 찾는 로직인데, 한번의 bfs실행마다 bfs를 위한 queue와 방문여부를 확인하는 visited배열, 마지막으로 밑에서 설명할 fishList리스트를 초기화한다.

 

- 일반적인 bfs와 다르게 목표를 찾아내도 바로 return하면 안되기 때문에(같은 최소거리를 갖는 물고기가 여러마리라면 문제에서 주어진 조건대로 선택해야 한다) 한번의 bfs탐색이 이루어질때마다 fishList라는 물고기(좌표) 리스트에 저장하고 조건에 맞는 물고기 좌표 정보를 찾아서 상어의 위치를 그곳으로 이동시키고 소요시간을 반환하는 moveProperPoint함수를 만들어서 관리하였다.

 

- 추가로 bfs나 dfs안에서의 로직 순서는 (조건 충족여부 체크(break/return))->(추가 경로 체크)와 같이 설정하였다. 할 때마다 헷갈려서 그런데 나중에 이 순서대로 했을 경우 문제가 생기면 수정할 것.

 

- 예전부터 사용했던 스킬(?)인데 좌표상에서 bfs를 할 경우 Location이라고 객체를 하나 만들어서 x,y,depth정보를 넣고 관리하는 것도 괜찮은것 같다. 아직까지는 문제푸는데 문제가 발생한 적은 없음.

 

 

+ 문제풀면서 개고생하고 디버깅하면서 애먹었던 포인트들도 있는데 알고보면 간단한 실수이거나 (+,-를 잘못쓴다던지 변수 사용을 헷갈린다던지) 기억이 안나는것들도 있음ㅜ 담에 또 반복되면 여따가 정리할것!