[Java]백준 BaekJoon.AC 16236 : 아기 상어 (Queue, bfs)

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

16236번: 아기 상어

 

고려해줘야 할 조건이 많은 까다로운 문제였지만 하나하나 풀어가는 재미가 있던 문제다!

난도는 그리 높지 않았지만 조건을 빠트려 하나씩 넣어주는 묘미(?)가 있었다.

이제 제법 Queue나 bfs에 익숙해진거 같다

 

다른 사람 코드 참고를 크게 안하고 풀어서 그런진 모르겠지만

코드 길이도 길고 선언한 것들도 많아 걱정했는데 별 탈 없이 성공을 안겨준 코드다ㅋㅋ

 

아래 가려둔 코드는 다른 답이 나와서 현황을 확인하기 위한 노력의 흔적들이다..

프린트 코드만 지우면 통과된다.  흔적을 기록하기 위한 코드다.

열심히 했다^^

<틀린코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int skC, skR;
	static int skS = 2;
	static int eat, sec, result = 0;
	static int[] udlrC = {-1, 1, 0, 0};
	static int[] udlrR = {0, 0, -1, 1};
	static int[][] fish;
	static boolean[][] visit;
	static Queue<Dot> queue = new LinkedList<>();
	static Queue<Dot> target = new LinkedList<>();
	
    public static void main(String[] args) throws IOException {
        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	fish = new int[N][N];
    	visit = new boolean[N][N];
    	
    	for(int i=0; i<N; i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0; j<N; j++) {
    			fish[i][j] = Integer.parseInt(st.nextToken());
    			if(fish[i][j]==9) {
    				skC = i;
    				skR = j;
    			}
    		}
    	}
    	
    	visit[skC][skR] = true;
    	fish[skC][skR] = 0;
    	queue.add(new Dot(skC, skR));
    	
    	move();
    	
    	System.out.print(result);
    }
    
    public static void move() {
    	
    	int s = queue.size();
    	
    	if(s==0) {
    		return;
    	}
    	System.out.println(s+"칸이 큐에 있다.");
    	for(int n=0; n<s; n++) {
    		Dot temp = queue.poll();
    		
    		for(int i=0; i<4; i++) {
        		int temC = temp.col+udlrC[i];
        		int temR = temp.row+udlrR[i];
        		if(0<=temC && temC<N && 0<=temR && temR<N) {//사용가능 좌표인지
        			System.out.println(temC + " " + temR + " 이동할까?");
        			if(visit[temC][temR]==false && fish[temC][temR]!=0) {//물고기인지
        				System.out.println("물고기!");
        				if(fish[temC][temR]<=skS) {//지나갈 자격 있는지
        					if(fish[temC][temR]<skS) {//먹을 자격 있는지
        						target.add(new Dot(temC, temR));
        						System.out.println("발견!");
        					}
        					queue.add(new Dot(temC, temR));
        					visit[temC][temR] = true;
        				}
        			}else if(visit[temC][temR]==false && fish[temC][temR]==0) {
        				System.out.println("이쪽 길로 이동!");
        				queue.add(new Dot(temC, temR));
    					visit[temC][temR] = true;
        			}
        		}
        	}
    	}
    	
    	if(target.isEmpty()) {
    		sec = sec + 1;
    		System.out.println(sec + "초!(더 탐색)");
    		move();
    	}else {
    		sec = sec + 1;
    		System.out.println(sec + "초!(먹으러 ㄱ)");
    		eat();
    	}
    	
    }
    
    public static void eat() {

		Dot temp = target.poll();
    	int goodC = temp.col;
    	int goodR = temp.row;
    	
    	
    	while(!target.isEmpty()) {
    		temp = target.poll();
    		
    		//(Math.abs(skC-temp.col)
    		
    		
    		if(temp.col<goodC) {//위에 있을수록
    			goodC = temp.col;
    			goodR = temp.row;
    		}else if(temp.col==goodC) {//같다면
    			if(temp.row<goodR) {//왼쪽일수록
    				goodC = temp.col;
        			goodR = temp.row;
    			}
    		}
    		
    	}
    	System.out.println(goodC + " " + goodR + "먹는다!");
    	skC = goodC;
		skR = goodR;
		fish[skC][skR] = 0;
		result = result + sec;
		sec = 0;
    	eat = eat + 1;
    	
    	if(eat==skS) {
    		skS = skS + 1;
    		eat = 0;
    	}
    	System.out.println("크기: "+skS + "  저장: " + eat);
    	System.out.println(result + "초가 되었다!");
    	queue.clear();
    	queue.add(new Dot(skC, skR));
    	visit = new boolean[N][N];
    	move();
    }
}

class Dot{
	int col;
	int row;
	
	Dot(int col, int row){
		this.col = col;
		this.row = row;
	}
}

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int skC, skR;
	static int skS = 2;
	static int eat, sec, result = 0;
	static int[] udlrC = {-1, 1, 0, 0};
	static int[] udlrR = {0, 0, -1, 1};
	static int[][] fish;
	static boolean[][] visit;
	static Queue<Dot> queue = new LinkedList<>();
	static Queue<Dot> target = new LinkedList<>();
	
    public static void main(String[] args) throws IOException {
        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	fish = new int[N][N];
    	visit = new boolean[N][N];
    	
    	for(int i=0; i<N; i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0; j<N; j++) {
    			fish[i][j] = Integer.parseInt(st.nextToken());
    			if(fish[i][j]==9) {
    				skC = i;
    				skR = j;
    			}
    		}
    	}
    	
    	visit[skC][skR] = true;
    	fish[skC][skR] = 0;
    	queue.add(new Dot(skC, skR));
    	
    	move();
    	
    	System.out.print(result);
    }
    
    public static void move() {
    	
    	int s = queue.size();
    	
    	if(s==0) {
    		return;
    	}
    	for(int n=0; n<s; n++) {
    		Dot temp = queue.poll();
    		
    		for(int i=0; i<4; i++) {
        		int temC = temp.col+udlrC[i];
        		int temR = temp.row+udlrR[i];
        		if(0<=temC && temC<N && 0<=temR && temR<N) {//사용가능 좌표인지
        			if(visit[temC][temR]==false && fish[temC][temR]!=0) {//물고기인지
        				if(fish[temC][temR]<=skS) {//지나갈 자격 있는지
        					if(fish[temC][temR]<skS) {//먹을 자격 있는지
        						target.add(new Dot(temC, temR));
        					}
        					queue.add(new Dot(temC, temR));
        					visit[temC][temR] = true;
        				}
        			}else if(visit[temC][temR]==false && fish[temC][temR]==0) {
        				queue.add(new Dot(temC, temR));
    					visit[temC][temR] = true;
        			}
        		}
        	}
    	}
    	
    	if(target.isEmpty()) {
    		sec = sec + 1;
    		move();
    	}else {
    		sec = sec + 1;
    		eat();
    	}
    	
    }
    
    public static void eat() {
    	Dot temp = target.poll();
    	int goodC = temp.col;
    	int goodR = temp.row;
    	
    	
    	while(!target.isEmpty()) {
    		temp = target.poll();
    		
    		
    		if(temp.col<goodC) {//위에 있을수록
    			goodC = temp.col;
    			goodR = temp.row;
    		}else if(temp.col==goodC) {//같다면
    			if(temp.row<goodR) {//왼쪽일수록
    				goodC = temp.col;
        			goodR = temp.row;
    			}
    		}
    		
    	}
    	skC = goodC;
		skR = goodR;
		fish[skC][skR] = 0;
		result = result + sec;
		sec = 0;
    	eat = eat + 1;
    	
    	if(eat==skS) {
    		skS = skS + 1;
    		eat = 0;
    	}
    	
    	queue.clear();
    	queue.add(new Dot(skC, skR));
    	visit = new boolean[N][N];
    	move();
    }
}

class Dot{
	int col;
	int row;
	
	Dot(int col, int row){
		this.col = col;
		this.row = row;
	}
}