[백준] 17086번 아기상어2 (BFS_JAVA)

무난한 BFS 문제!

 

BFS와 DFS가 익숙해져가니

구현을 더 연습해야겠다.

 

 

---

문제

 

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

17086번: 아기 상어 2

 

 

---

설계

 

알고리즘 설계 [접근 방법] : BFS

 

무난한 BFS 문제다!

각각의 좌표가 상어가 있는 1의 지점으로부터 얼마나 멀어져있는지 확인하고, 가장 멀리 있는 거리를 출력하면 된다.

일단 상어가 있는 좌표를 찾고, 그 지점들로부터 8방향으로 탐색하며 그래프를 뻗어나가면 된다.

기준을 각각의 좌표로 두지 않고, 상어가 있는 좌표를 시작점으로 두는 것이 실행시간에 훨씬 유리하다!

 

 풀이 과정

1.

2차원 배열 map을 생성한 후, 값을 입력받는다.

이 때, 입력 값이 1이라면 상어가 있다는 뜻이고, 그 좌표 값을 -1로 변경한다. 왜냐하면 배열 map의 값을 BFS로 탐색하면서 상어와의 거리로 갱신할 것이기 때문이다. 

그 후 8방향 탐색을 위해 배열 r, c와 방문체크를 위한 2차원 배열을 생성한다.

 

2.

정답 변수 answer를 0으로 초기화한 후 BFS 메서드를 실행한다.

 

3.

BFS 메서드에서는 Queue를 생성한 후, 반복문을 돌아 상어 좌표를 방문체크 한 후  queue에 넣는다.

이 때, 좌표 i, j와 상어와의 거리인 0을 배열로 만들어 큐에 넣는다.

 

4.

큐에서 값을 꺼낸다.

값은 좌표와, 그 좌표와 상어의 차이 길이를 담은 배열이다. 

상어와의 길이 차이와 answer와 값을 비교해서, 더 큰 값으로 갱신한다. 

 

5.

그 후, 현재 좌표에서 8방향을 탐색한다.

map의 범위 밖에 있거나, 상어가 있는 좌표일 때는 탐색하지않고 넘어간다.

또, 이미 방문한 좌표해서 탐색한 좌표인데, 이미 상어와의 거리가 현재보다 작다면 넘어간다.

만약 이미 방문했지먄, 현재 탐색한 거리가 이미 탐색했을 때의 거리보다 작다면 넘어가지 않고 갱신해야한다. 

 

6.

배열 map 좌표에 현재 탐색길이 +1의 값으로 갱신한다.

그리고 방문체크 한 후, 좌표를 큐에 넣는다.

 

 

---

코드

 

import java.util.*;

public class Test_17086_아기상어2 {
	
	static int h, w, answer;
	static int[][] map;
	static int[] r, c;
	static boolean[][] isvisited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		h = sc.nextInt();
		w = sc.nextInt();
		
		map = new int[h][w];
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				map[i][j] = sc.nextInt();
				
				if(map[i][j]==1) map[i][j]=-1;
			}
		}

		r = new int[] {-1, 0, 1, 0, -1, 1, 1, -1};
		c = new int[] {0, 1, 0, -1, 1, 1, -1, -1};
		isvisited = new boolean[h][w];
		
		answer = 0;
		BFS();
		
		System.out.println(answer);
	}
    
	
	//BFS
	public static void BFS() {
		Queue<int[]> queue = new LinkedList();
		
        //상어가 있는 지점 찾고, queue에 넣기
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(map[i][j]==-1) {
					isvisited[i][j]=true;
					queue.add(new int[] {i, j, 0});
				}
			}
		}
		
		
		while(!queue.isEmpty()) {
			
			int[] cur = queue.poll();
			
			int i = cur[0];
			int j = cur[1];
			int depth = cur[2];
			
			answer = Math.max(answer, depth);	//answer 갱신하기
		
			for(int k=0; k<8; k++) {
				int dr = i+r[k];
				int dc = j+c[k];
				
				if(!(0<=dr && dr<h && 0<=dc && dc<w )) continue;
				if(map[dr][dc]==-1) continue;
				if(isvisited[dr][dc] &&  map[dr][dc]<=depth+1) continue; //현재 값이 더 크면 넘어가기
				
				map[dr][dc]=depth+1;
				isvisited[dr][dc]=true;
				queue.add(new int[] {dr, dc, depth+1});
				
			}
		}
	}
}

 

 

(❁´◡`❁)

끝!