백준 17086번 : 아기 상어2

 문제

www.acmicpc.net/problem/17086

17086번: 아기 상어 2

17086 아기 상어2

 

 구현 방법

 처음에는 브루트포스로 구할 수 있는 전부를 구했습니다. 각자의 위치에서 bfs를 통해 제일 가까운 상어까지의 거리를 저장 후 최댓값을 구해주었습니다.

 

채점 후 시간차가 많이 나는 코드를 참고해보니 다른 생각으로 접근할 수 있다는 걸 깨달았고 참고해서 다시 짜보았습니다.

빈 칸이 중점이 아닌 상어를 중점으로 하여 입력되는 상어를 전부 queue에 넣어준 후 bfs를 통해 방문체크를 해주면 퍼지다가 알아서 방문한곳을 만나 멈춥니다. 그 멈춘 구간이 해당 상어에서 최대로 먼 부분이기 때문에 카운트를 체크한 변수를 따로 최댓값인지 비교할 필요 없이 그대로 출력해주면 끝입니다.

 

 구현 코드

- 빈 칸 중점

package BOJ.Silver.bfsdfs;

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 B17086_아기상어2 {
	static int R, C, MAX;
	static int[][] map, deltas= {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
	static Queue<move> bfs;
	static int[][] check;
	static class move{
		int r, c, cnt;

		public move(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		check = new int[R][C];
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		MAX = Integer.MIN_VALUE;
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c]==0) { // 빈칸일 때 bfs 돌리기
					bfs = new LinkedList<>();
					bfs.add(new move(r, c, 1));
					bfsL();
					check = new int[R][C];
				}
			}
		}
		
		System.out.println(MAX);
	}
	
	static void bfsL() {
		while(!bfs.isEmpty()) {
			int size = bfs.size();
			for (int i=0;i<size;i++) {
				move now = bfs.poll();
				for (int d=0;d<8;d++) {
					int nr = now.r+deltas[d][0];
					int nc = now.c+deltas[d][1];
					if (isIn(nr,nc) && check[nr][nc]==0) {
						if (map[nr][nc]==1) { // 상어를 발견하면 최댓값 구하고 끝내기
							MAX = Math.max(MAX, now.cnt); 
							return;
						}
						check[nr][nc]=1;
						bfs.offer(new move(nr, nc, now.cnt+1));
					}
				}
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

- 상어 중점

package BOJ.Silver.bfsdfs;

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 B17086_아기상어2 {
	static int R, C, cnt;
	static int[][] map, deltas= {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
	static Queue<int[]> bfs;
	static boolean[][] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		visit = new boolean[R][C];
		bfs = new LinkedList<>();
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
				if (map[r][c]==1) { // 상어일 때
					bfs.add(new int[] {r, c}); // 다 넣어주기
 					visit[r][c] = true;
				}
			}
		}
		bfsL();
		
		System.out.println(cnt-1);
	}
	
	static void bfsL() {
		while(!bfs.isEmpty()) {
			cnt++;
			int size = bfs.size();
			for (int i=0;i<size;i++) {
				int[] now = bfs.poll();
				for (int d=0;d<8;d++) {
					int nr = now[0]+deltas[d][0];
					int nc = now[1]+deltas[d][1];
					if (isIn(nr,nc) && visit[nr][nc]==false) {
						visit[nr][nc] = true;
						bfs.offer(new int[] {nr, nc});
					}
				}
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!