BOJ | Silver 2/17086/아기 상어 2

이 문제는 해법이 아기 상어 노래처럼 깜찍하게 나오지 못한 문제였다. 그 이유는 필자가 BFS를 문제에서 제시한 내용에 맞게 사용하지 못하였기 때문이다. 그래서 게시글로 작성함을 통해 BFS 개념으로 문제를 풀어냈다. 독자도 이 경우에 해당한다면, 아래 태그된 링크를 통해 개념을 먼저 파악한 후 본 문제를 풀어보도록 하자.

2023.07.12 - [개발/Dev | 알고리즘] - 그래프 탐색 알고리즘 (3) 너비 우선 탐색을 중심으로

그래프 탐색 알고리즘 (3) BFS 를 중심으로

필자는 이 문제를 이해하기 위해 나름 많은 고민을 했다. 그래서 그런지 풀이를 쉽게 설명할 수 있게 되었다. 이보다 더 쉽게 풀이한 내용이 없을 정도로 아주 쉽게 풀이해보도록 하겠다.

 

1. 문제 이해

1) N×M 크기의 공간에 아기 상어 여러 마리가 있다.

> N 행, M 열인 입력 값을 의미한다.

2) 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

>  1이 위치하는 곳을 의미한다.

3) 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다.

> 1이 위치한 세 지점으로부터 겹치는 부분의 값은 거리가 가까운, 즉 더 작은 값이 들어간다는 의미이다. 

4) 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

> 방향은 좌표로 표현하면 (x, y) 일 때, (-1, 0), (-1, -1), (-1, 1), (0, 1), (0, -1), (1, 0), (1, 1), (1, -1)에 해당한다.

5) 안전 거리가 가장 큰 칸을 구해보자. 

필자는 그림을 그리면서 풀이를 이어나갔다. 참고로 각 행의 상어의 위치는 편의상 A, B, C로 설정하겠다.

1) A를 기준으로, 다음과 같은 안전거리가 존재한다.

 

2) B를 기준으로, 다음과 같은 안전 거리가 존재한다.

 

3) C를 기준으로 다음과 같은 안전 거리가 존재한다.

4) 1), 2), 3) 를 통합하여 가장 짧은 거리를 기준으로 표현하면 다음과 같다.

최소 안전 거리로 탐색한 결과

 

2. 로직

2-1) 로직 플로우 
로직은 BFS를 이용하는 것이다. 탐색을 할 때는 모든 지점에 대한 탐색을 하는 것이 아닌, 1이 위치한 지점에만 국한되어 탐색을 진행하였다.

2-2) 로직 상세
1) BufferedReader 객체를 생성하고, 객체로 값을 입력받는다.

2) 입력된 값을 N, M(N높이, M너비)에 할당한다.

3) StringTockenizer 객체를 생성하여 0과 1의 값을 배열에 순차적으로 입력받는다.

4) 아기 상어의 위치와, 안전 거리를 저장할 배열은 분리하여 선언한다. (조건문 때문)

5) 아기상어의 위치에 따라 bfs를 실행하고, 방문여부를 확인할 visited 배열을 false로 초기화한다.

6) bfs는 다음과 같은 로직으로 구현한다.

- 안전거리를 저장할 이차원 배열의 인덱스를 bfs의 매개변수로 보낸다. (시작지점)

- 8방향을 확인하기 위해 인덱스를 벗어나는 지점은 탐색하지 않도록 한다.

- 시작 지점으로부터 bfs로 탐색을 하는데,  8방향으로 탐색을 진행하므로 시간 초과 이슈 방지를 위해 방문 여부를 반드시 확인한다. 이미 방문한 위치는 탐색하지 않도록 한다.

- 아기 상어의 위치를 탐색하지 않도록 한다.

- 0일 때는 안전 거리에 1을 더해주고, 이미 값이 할당되어 있는 경우에는 값을 비교하여 최솟값으로 할당한다.

7) 최댓값을 출력하기 위해 각 행을 정렬하여 가장 큰 값을 최댓값으로 사용할 변수에 할당한다.

8) 안전 거리의 최댓값을 출력한다.
 

3. 구현

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] sharks;
    static int[][] distance;
    static boolean[][] visited;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {1, 0, -1, 1, -1, 1, 0, -1};

    private static void bfs(int n, int m) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{n, m});
        visited[n][m] = true;

        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            for (int i = 0; i < 8; i++) {
                int X = temp[0] + dx[i];
                int Y = temp[1] + dy[i];

                if (X < 0 || X >= N || Y < 0 || Y >= M) continue; // 8 방향 탐색 예외
                if (sharks[X][Y] == 1 || visited[X][Y]) continue; // 상어 위치 혹은 이미 방문한 곳 탐색 예외

                if (distance[X][Y] == 0) { // 탐색을 진행할 위치
                    distance[X][Y] = distance[temp[0]][temp[1]] + 1;
                } else {	//이미 값이 존재하는 위치 따라서 최솟값을 할당함.
                    distance[X][Y] = Math.min(distance[X][Y], distance[temp[0]][temp[1]] + 1);
                }

                visited[X][Y] = true;
                queue.add(new int[]{X, Y});
            }
        }
    }

    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());

        sharks = new int[N][M];
        distance = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                sharks[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (sharks[i][j] == 1) { // 아기 상어가 존재하는 위치에서만 탐색을 진행한다.
                    for (boolean[] boolArr : visited) {
                        Arrays.fill(boolArr, false);
                    }
                    bfs(i, j);
                }
            }
        }

        int max=0;
        for(int[] temp:distance){ 
            Arrays.sort(temp); // 최댓값 출력을 위한 배열 정렬, 이차원 배열이므로 각 행마다 나눠서 정렬한다.
            max = Math.max(max, temp[M-1]);
        }

        System.out.println(max);
    }
}

 

위 풀이를 기반으로 BFS 탐색 알고리즘을 사용하여 문제를 풀어보자.

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

17086번: 아기 상어 2

 

끝까지 읽어주셔서 감사합니다-! :)