문제 설명
풀이
일단 상어마다 모두 주변을 확인해서, 안전거리를 모두 구해야한다. 그렇게 생각하면 어떻게 모두 확인해볼지 생각해봐야 한다.
계속해서 안전거리를 추가해줘야하니 DFS나 BFS를 해줘야하는데, 끝까지 갈필요 없이, 최대한 인접한 곳을 보는 것이니 BFS로 하였다.
그리고 매우 기초적인 BFS라서 BFS의 흐름을 풀어보기에 좋은 문제였다.
코드
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N,M;
static int count;
static int[][] map;
static int[][] dis;
static int[] dx = {-1,0,1,-1,1,-1,0,1};
static int[] dy = {-1,-1,-1,0,0,1,1,1};
public static void main(String[] args) throws IOException {
// 1. 값 입력받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
count = 0;
map = new int[N+1][M+1];
dis = new int[N+1][M+1];
Queue<int[]> que = new LinkedList<int[]>();
for(int i =0; i< N; i++){
st = new StringTokenizer(br.readLine());
for(int j =0; j<M; j++){
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 1){
que.add(new int[] {i,j});
}
}
}
while (!que.isEmpty()) {
int[] now = que.poll();
int x = now[0];
int y = now[1];
for(int z=0; z<8; z++){
int cx = x + dx[z];
int cy = y + dy[z];
if(cx < 0 || cy < 0 || cx >= M || cy >= N || map[cx][cy] == 1 || dis[cx][cy] != 0){
continue;
}
dis[cx][cy] = dis[x][y] + 1;
if (dis[cx][cy] > count){
count = dis[cx][cy];
}
que.add(new int[] {cx,cy});
}
}
System.out.println(count);
}
}https://www.acmicpc.net/problem/17086
17086번: 아기 상어 2
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다.
www.acmicpc.net
'개발합시다. > JAVA 알고리즘 문제풀이' 카테고리의 다른 글
| BOJ_1139 단어 수학 [Java] (G5) (0) | 2021.11.01 |
|---|---|
| BOJ_2178 미로탐색 [Java] (S1) (0) | 2021.11.01 |
| BOJ_16948 데스나이트 [Java] (S1) (0) | 2021.10.29 |
| BOJ_6603 로또 [Java] (S2) (0) | 2021.10.29 |
| BOJ_11724 연결 요소의 개수 풀이 [Java] (S2) (0) | 2021.10.27 |
