BOJ_17086_아기 상어2

1

구분: 그래프 이론, 그래프 탐색, BFS, DFS
언어: Java
전략:

• 상어와 그 주변(8방)을 BFS를 통해 탐색하면서, 그 값을 갱신한다.
• 어떤 지점의 안전거리는 나를 부른(내 주변, 나를 인접해하는) 것보다 1 크다 -> 나를 부른 것의 값+1 
• 상어가 있는 자리를 -1로 처음 설정하여 +1 할 때, 진짜 값과 상어의 값의 혼란을 줄인다. 
• 최대 값을 매번 갱신한다. 현 최대 값과, 새로 갱신되는 map의 값을 비교한다.

---

2. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	
	//배열의 x,y좌표를 담는 class 생성
	static class Node{
		int y;
		int x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int h = scanner.nextInt(); //높이
		int w = scanner.nextInt(); //너비
		
		int[][] map = new int[h][w];
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				int input = scanner.nextInt();
				if(input ==1){ //상어가 있는 자리는 -1로 설정
					map[i][j] = -1;
				}
				else map[i][j] = input;
			}
		}
		Queue<Node> q = new LinkedList<>();
		
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				if(map[i][j]==-1)
				//상어가 있는 곳을 큐에 삽입
				q.offer(new Node(i,j));
			}
		}
		
		//시계방향 - 8방 탐색
		int[] dx = {0,1,1,1,0,-1,-1,-1};
		int[] dy = {-1,-1,0,1,1,1,0,-1};
		//구하고자 하는 최대값
		int max = Integer.MIN_VALUE;
		
		while(!q.isEmpty()) {
			
			//뺴낸다
			Node node = q.poll();
			int py = node.y;
			int px = node.x;
			
			//뿌리가 되는 칸의 값 - 인접한 값들은 prev에서 1씩 증가한 거리를 가짐
			int prev = map[py][px];
			//상어가 있는 자리면 0으로 처리
			if(prev == -1) prev = 0;
			
			//8방 탐색
			for(int d = 0; d<8; d++) {
				//인접한 노드의 좌표를 구함
				int nx = px + dx[d];
				int ny = py + dy[d];
				
				//범위를 벗어나거나 아기상어면 지나가
				if(nx<0||ny<0||nx>=w||ny>=h || map[ny][nx]==-1)
					continue;
				//이미 채워져 있는곳이야 - 지나가 
				if(map[ny][nx]!=0) continue;
				
				//인접한 곳들을 큐에 삽입, 그 자리의 값을 상어와의 거리로 갱신
				q.offer(new Node(ny, nx));
				map[ny][nx] = prev+1;
				
				//매번 최대값을 갱신한다. 
				max = Math.max(max, map[ny][nx]);
				
			}//8방탐색
		}//while

		System.out.println(max);

	}//main
	
}//class

---

3

처음에는 상어 하나를 기준으로 BFS적용, 그 다음 적용, 하면서 만약 상어와 0이 아니면(이미 갱신 되어 있으면) 현재의 값과, 새로 갱신하려는 값의 최소 값으로 map을 변경하는 로직을 세웠다. 하지만 무한 루프에 빠져서 이 방법을 버렸다.