백준 16236 자바 ☆

문제

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

16236번: 아기 상어

import java.util.Scanner;

public class Main16236 {

	static int N;
	static int[][] map;
	static boolean[][] visited;
	static int min = Integer.MAX_VALUE;
	static int[] ax = {-1,1,0,0};
	static int[] ay = {0,0,-1,1};
	
	public static boolean callMotherShark(int[][] clone, int babyShark) {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (babyShark > clone[i][j] && clone[i][j] > 0) {
					return false;
				}
			}
		}
		return true;
	}
	
	public static void dfs(int[][] clone, int cnt, int x, int y, int babyShark, int eatingCount) {
		
		int[][] temp = new int[N][N];
		
		for (int i=0; i<N; i++) {
			temp[i] = clone[i].clone();
		}
		
		if (eatingCount == babyShark) {
			babyShark++;
			eatingCount = 0;
		}

	    if (callMotherShark(temp, babyShark)) { 
			System.out.println(cnt);
		    min = Math.min(min, cnt);  
		    return;
	    
	    } else {
	    	for (int i=0; i<4; i++) {
	    		int nx = x+ax[i];
	    		int ny = y+ay[i];
	    		
	    		if (nx>=0 && ny>=0 && nx<N && ny<N && !visited[nx][ny]) {
					 
	    			if (temp[nx][ny] <= babyShark) {
	    				if (temp[nx][ny] < babyShark && temp[nx][ny] > 0) {
	    					eatingCount++;
	    					temp[nx][ny] = 0;
	    					visited[nx][ny] = true;
	    					dfs(temp, cnt+1, nx, ny, babyShark, eatingCount);
	    				    visited[nx][ny] = false; 
	    				} else if (temp[nx][ny] == babyShark || temp[nx][ny] == 0) {
	    					visited[nx][ny] = true;
	    					dfs(temp, cnt+1, nx, ny, babyShark, eatingCount);
	    				    visited[nx][ny] = false; 
	    				}
	    			} else {
	    				continue;
	    			}
	    		}
	    	}
	    }

		
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		map = new int[N][N];
		visited = new boolean[N][N];
		
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		sc.close();
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j] == 9) {
					map[i][j] = 0;
					dfs(map, 0, i, j, 2, 0);
				}
			}
		}
		
		System.out.println(min);
	}
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main16236_1 {

	static int N;
	static Shark shark;
	static int[][] map;
	static int[] ax = {-1,1,0,0};
	static int[] ay = {0,0,-1,1};
	static int eatingCount = 0;
	static int sharkSize = 2;
	static int moveCount = 0;
	
	private static class Shark {
		int x;
		int y;
		int count;
		
		public Shark(int x, int y, int count) {
			super();
			this.x = x;
			this.y = y;
			this.count = count;
		}
	}
	
	public static void bfs() {
	
		Queue<Shark> q = new LinkedList<>();
		q.add(shark);
		
		while(true) {
			LinkedList<Shark> feeding = new LinkedList<Shark>();
			int[][] dist = new int[N][N];
			
			while(!q.isEmpty()) {
				
				Shark temp = q.poll();
				
				for (int i=0; i<4; i++) {
					int nx = temp.x + ax[i];
					int ny = temp.y + ay[i];
					
					if (nx >= 0 && ny >= 0 && nx < N && ny < N && dist[nx][ny] == 0 && map[nx][ny] <= sharkSize) {
						dist[nx][ny] = dist[temp.x][temp.y] + 1;
						q.add(new Shark(nx, ny, dist[nx][ny]));
						if (map[nx][ny] > 0 && map[nx][ny] < sharkSize) {
							feeding.add(new Shark(nx, ny, dist[nx][ny]));
						}
					}
				}
			}
			
			if (feeding.size() == 0) {
				System.out.println(moveCount);
				return;
			}
			
			Shark currentPoint = feeding.get(0);
			for (int i=1; i<feeding.size(); i++) {
				if (currentPoint.count > feeding.get(i).count) {
					currentPoint = feeding.get(i);
					
				} else if (currentPoint.count == feeding.get(i).count) {
					
					if (currentPoint.x > feeding.get(i).x) {
						currentPoint = feeding.get(i);
					} else if (currentPoint.x == feeding.get(i).x) {
						if (currentPoint.y > feeding.get(i).y) {
							currentPoint = feeding.get(i);
						}
					}
				}
			}
			
			moveCount += currentPoint.count;
			eatingCount++;
			map[currentPoint.x][currentPoint.y] = 0;
			if (eatingCount == sharkSize) {
				sharkSize++;
				eatingCount = 0;
			}
			q.add(new Shark(currentPoint.x, currentPoint.y, 0));

		}
		
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		map = new int[N][N];

		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		sc.close();
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j] == 9) {
					map[i][j] = 0;
					shark = new Shark(i,j,0);
				}
			}
		}
		
		bfs();
	}
}

1. 첫번째 코드는 dfs로 푸는 방식. 결국 정답을 내지 못했다. 이틀동안 삽질한 바로는 dfs는 풀수없다는게 내가 알게 된 사실이다. 하지만 bfs로 문제를 푸는 방법을 찾다보니 가장 가까운 위치의 물고기를 먹고난 후 새로운 배열에서 다시 시작함으로써 해결 할수 있을 듯하다. 나중에 시간이 나면 dfs로 다시 도전해보자.

 

2. bfs로 푸는 방법도 여러 방법이다. 그 중 먹을 수 있는 물고기를 list에 저장해 푸는 해결법을 택했다.

 

3. 타 블로그의 글들을 참고했고 결국 포인트는 

 첫째, 가장 가까운 물고기를 탐색

 둘째, 여러마리일 경우 위쪽, 왼쪽순으로 탐색

 셋째, 해당 물고기를 먹은 후 배열을 초기화해 다시 먹을 수 있는 물고기를 탐색

이다. dfs로 풀 때 해당 부분에서 막혔는데, 왔던 길을 다시 돌아간다는 생각보다는 먹고 난 후 새로운 배열로 진행하는게 타당한듯 하다. 

 

4. 어찌됐건 dfs로도 풀 수 있다는게 지금의 생각이다. 하지만 최단거리를 구하는 문제에선 bfs를 우선적으로 쓰는 습관을 들이자. 그리고 bfs로 푸는건 아직 익숙하지 않아 타블로그를 클론코딩하다 싶이 했으니 나중에 꼭 다시 풀어보자.

 

참고 블로그 : https://moonsbeen.tistory.com/231

[백준]16236: 아기 상어 - JAVA