🔗 Problem

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

👩‍💻 Code - BFS

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

// 아기 상어 2

public class BJ17086 {
	
	static int n;
	static int m;
	static int answer;
	static int[] x = {-1, 0, -1, -1, 1, 1, 0, 1};
	static int[] y = {-1, -1, 1, 0, 0, -1, 1, 1};
	static boolean[][] map;
	static int[][] dist;
	static Queue<Shark> queue = new LinkedList<>();
	
	static class Shark {
		
		int x;
		int y;
		
		Shark(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 = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new boolean[n][m];
		dist = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				if(st.nextToken().equals("1")) {
					map[i][j] = true;
					queue.add(new Shark(i, j));
				}
			}
		}
		
		bfs();
		System.out.println(answer);
	}
	
	private static void bfs() {
		
		while(!queue.isEmpty()) {
			
			Shark poll = queue.poll();
			int px = poll.x;
			int py = poll.y;
			for(int i = 0; i < x.length; i++) {
				int xx = px + x[i];
				int yy = py + y[i];
				if(xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
				if(map[xx][yy] || dist[xx][yy] != 0) continue;
				dist[xx][yy] = dist[px][py] + 1;
				answer = Math.max(answer, dist[xx][yy]);
				queue.add(new Shark(xx, yy));
			}
			
		}
	}
}

👩‍💻 Code - Brute Force

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 아기 상어 2

public class BJ17086_2 {
	
	static int n;
	static int m;
	static int answer;
	
	static boolean[][] map;
	static int[][] dist;
	static ArrayList<Shark> sharks = new ArrayList<>();
	
	static class Shark {
		
		int x;
		int y;
		
		Shark(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 = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new boolean[n][m];
		dist = new int[n][m];
		
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				if(st.nextToken().equals("1")) {
					map[i][j] = true;
					sharks.add(new Shark(i, j));
				}
				dist[i][j] = Integer.MAX_VALUE;
			}
		}
		
		solution();
		System.out.println(answer);
	}
	
	private static void solution() {
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				
				if(map[i][j]) continue;
				
				for(int k = 0; k < sharks.size(); k++) {
					int distance = Math.max(Math.abs(sharks.get(k).x - i), Math.abs(sharks.get(k).y - j));
					dist[i][j] = Math.min(dist[i][j], distance);
				}
				
				answer = Math.max(answer, dist[i][j]);
			}
		}
	}
}

📌 Note

아이디어

• 처음에 1인 칸 저장하고 모든 0인 칸에 대해서 1인 칸까지의 거리를 구하려고 했는데 bfs로 풀어야 할 거 같아서 ? 위와 같이 구현하였다.
• 1인 칸들을 queue에 모두 넣어주고, 상하좌우대각선 8 방향을 탐색하며 dist를 업데이트 했다.

틀렸습니다

• 8방향 x[], y[] 값을 잘못 정해서 자꾸 틀렸다..

• bfs 말고 다른 방법으로도 내일 풀어봐야겠다~

아이디어 2

• Brute Force로도 풀어봤는데 통과된다..