알고리즘 BFS의 템플릿?

package com.example.demo;

import java.io.*;
import java.util.*;
/*
아기 상어의 위치에서 이웃한 모든 정점을 거리를 한 단계씩 증가시키면서 탐색한다.
아기 상어와 가장 가까운 칸부터 시작하여 거리를 기록하고 그거리가 가장 큰 칸이을 구하는 문제.
 */
public class Main {
    public static int n, m;
    public static int[][] arr;//방문 여부체크
    public static int[] x = {-1, 1, 0, 0, 1, 1, -1, -1};
    public static int[] y = {0, 0, -1, 1, -1, 1, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());//공간 크기
        m = Integer.parseInt(st.nextToken());
        arr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) {
                    q.offer(new int[]{i, j});//아기상어의위치
                }
            }
        }

        int result = bfs(q);

        System.out.printf("%d", result - 1);
    }

    public static int bfs(Queue<int[]> q) {
        int distance = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] shark = q.poll();
                int x1 = shark[0];//아기상어의 xy좌표
                int y2 = shark[1];

                for (int j = 0; j < 8; j++) {
                    int nx = x1 + x[j];//상어이동 위치
                    int ny = y2 + y[j];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && arr[nx][ny] == 0)//범위 안인지 체크 상어가 없는지 체크
                    {
                        q.offer(new int[]{nx, ny});
                        arr[nx][ny] = arr[x1][y2] + 1;
                    }
                }
            }
            distance++;
        }
        return distance;
    }
}

 

 

너비 우선 탐색(BFS, Breadth-First Search)은 기본적으로 템플릿이 존재하는 느낌이다.

상당한 부분이 문제마다 겹친다.

 

1.입력을 받는부분

2.2차원 배열로 맵을 만드는부분

3.큐에 위치 삽입

4.탐색 진행

5.방문한 좌표 저장하는 배열로 중복 체크

 

그래서 여기서 특수한 조건이 붙거나 다른 알고리즘 유형이나 구현문제에 BFS가 첨가되는 문제가실제 코테에서는 대부분이라고 한다.왜냐면 문제가 다 거기서 거기라 단독으로 내기에는 변별력을 가지지 못해 나와도 첫번째 문제정도로처리될 것이라고 한다!