mingssssss

1. 문제

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

2. 코드

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 Main {
	
    // 전역 변수 설정
	static int[][] map;
	static boolean visited[][];
	static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];

		Queue<int[]> q = new LinkedList<>();
		
		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());
                // 상어가 있는 위치 큐에 add
				if (map[i][j] == 1) {
					q.add(new int[] {i, j});
				}
			}
		}
		// 입력 종료
		
        // 거리 시작이 2부터 시작이여서 1을 빼주고 출력
		System.out.println(BFS(N, M, q) - 1);
		
//		// 출력
//		System.out.println("*******");
//		StringBuilder sb = new StringBuilder();
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < M; j++) {
//				sb.append(map[i][j] + " ");
//			}
//			sb.append("\n");
//		}
//		
//		System.out.println(sb);
		
	}

	public static int BFS(int N, int M, Queue<int[]> q) {
		
		visited = new boolean[N][M];
		int check = 2;
		
		while (!q.isEmpty()) {
			
			int[] now = q.poll();
			
            // 좌상, 상, 우상, 우, 우하, 하, 좌하, 좌 순으로 8방향 탐색
			for (int i = 0; i < 8; i++) {
				
				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];
				
				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
					continue;
				}
				
                // 1보다 크다는 것은 이미 값이 들어간 경우이면서 현재 값보다 큰 경우임
				if (map[nextX][nextY] >= 1) {
					continue;
				}
				
				visited[nextX][nextY] = true;
				map[nextX][nextY] = map[now[0]][now[1]] + 1;
				q.add(new int[] {nextX, nextY});
                // 최대거리
				check = map[nextX][nextY] > check ? map[nextX][nextY] : check;
			}
		
		}
		
		return check;
	}

}

3. 리뷰

아기 상어1 문제를 푸려고 했는데 너무 어려워서 좀 더 쉬운 문제를 선택해서 풀었다.

문제를 풀기 전에 BFS가 어떤식으로 구현되는지 다시 한번 공부하고 문제를 풀었다.

전체 배열을 입력을 하면서 1인경우(상어가 있는 경우)를 큐에 집어넣었다.

현재 큐에는 모든 아기 상어가 있는 좌표가 들어있고, 이 상태에서 BFS를 돌렸다.

아기 상어가 있는 위치부터 BFS를 돌려서 아기 상어가 있는 위치를 제외하고

아기 상어로부터의 모든 거리를 구했다.

탐색하는 좌표의 값이 1보다 크다는 것은 이미 값이 들어간 경우이면서

이미 최대 거리가 들어간 경우이므로, continue로 스킵했다.

전체 배열을 순회하면서 최댓값을 찾는 방법도 있지만,

check 변수를 통해 현재 좌표의 값이 비교하는 좌표의 값보다 크면 재할당 하여서

최댓값을 구했다.

시간과 메모리 두 마리 토끼를 모두 잡은 것 같아서 뿌듯했다.