[백준] 17086번 아기 상어 2

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

17086번: 아기 상어 2

---

저번 18405번 경쟁적 전염 문제와 비슷하게, 시작점이 여러 곳이다. 

시작점이 여러 곳이면 큐를 여러개 만들어야 하나? 라고 전에 고민했던 것 같은데, 문제 조건에 따라 객체를 만들면 되는 문제인 것 같다.

객체의 필드값으로 좌표값 (x,y)과 문제에 맞는 필드값 (ex. 해당 문제에서는 length)를 넣어주면 되는 것 같다.

 

이번 문제도 마찬가지로 BFS를 사용하고, Shark 라는 객체에 x,y와 함께 length를 넣어서 최대 길이를 찾으면 될 것 같다. 

내가 처음 생각한 풀이과정은 아래와 같다. 

 

1. 맵 가로,세로(N,M) 값 받아서 맵 초기화 진행
   1. 맵에 들어가는 값이 1이면, q.offer(new Shark(x,y,length));
2. x,y,length 값을 갖는 Shark class 생성
   1. 탐색할 칸을 뜻하는 shark class 이다.
   2. x,y는 칸의 좌표
   3. length는 해당 칸의 안전 거리를 뜻한다. 
3. q가 빌 때까지 bfs 진행
   1. 8방향 탐색하면서 유효한 칸이면 (방문 안했고, 맵의 범위 벗어나지 않음) q에 추가(이 때, length + 1) 하고 방문 처리
   2. q가 비었다면 마지막 poll 한 shark의 length, 즉 안전거리 출력

=> 해당 방법은 상어 위치를 시작점으로 두고 시도한 방법이다.

 

+ ) 상어 위치 말고 그냥 0인 위치 기준으로 BFS 하면서 가장 가까운 상어까지 도달하는 방법으로 안전 거리 구한 후, 모든 값 비교해서 최댓값 찾는 방법도 있긴 하다. -> 훨씬 오래 걸리는 방법이긴 하지만 통과는 한다고 한다. 

package yejin.song;

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 BOJ_아기상어2 {
    // 전역 변수 선언
    static int map[][];
    static int N,M;
    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};

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

        map = new int[N][M];
        visited = new boolean[N][M];

        Queue<Shark> q = new LinkedList<>();

        // 맵 추기화, 큐 offer, 방문 처리
        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){
                    q.offer(new Shark(i,j,0));
                    visited[i][j] = true;
                }
            }
        }

        while (!q.isEmpty()){
            Shark shark = q.poll();
            if (q.isEmpty()){
                System.out.println(shark.length);
            }
            bfs(q, shark);
        }
    }

    static void bfs(Queue<Shark> q, Shark shark){
        for (int i = 0; i<8; i++){
            int nx = dx[i] + shark.x;
            int ny = dy[i] + shark.y;

            if (nx >= 0 && nx < N && ny >= 0 && ny < M && visited[nx][ny] == false){
                q.offer(new Shark(nx,ny, shark.length + 1));
                visited[nx][ny] = true;
            }
        }
    }

    static class Shark {
        int x, y, length;
        Shark(int x, int y, int length){
            this.x = x;
            this.y = y;
            this.length = length;
        }
    }
}

 

근데 채점 80% 쯔음에서 틀렸습니다. 가 뜬다. 왜,, 일까,,? 

 

 

++) 결론 : 아기상어가 1마리 일 때의 while문을 잘못 생각했다. 위의 코드처럼 한다면, print 한 이후에 bfs를 돌기 때문에 두 번 출력이 되고, 처음 print 된 값이 최종 값이 아니다. print문과 bfs의 순서를 바꾸어주면 bfs를 한 후 최종적으로 print 문을 한번만 쓸 수 있게 된다...

최종코드 ->

package yejin.song;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_아기상어2 {
    // 전역 변수 선언
    static int map[][];
    static int N,M;
    static boolean visited[][];
    static int dx[] = {1, -1, -1, 1, 1, 0, -1, 0};
    static int dy[] = {1, 1, -1, -1, 0, 1, 0, -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());

        map = new int[N][M];
        visited = new boolean[N][M];

        Queue<Shark> q = new LinkedList<>();

        // 맵 추기화, 큐 offer, 방문 처리
        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){
                    q.offer(new Shark(i,j,0));
                    visited[i][j] = true;
                }
            }
        }

        while (!q.isEmpty()){
            Shark shark = q.poll();
            bfs(q, shark);
            if (q.isEmpty()){
                System.out.println(shark.length);
            }
        }
    }

    static void bfs(Queue<Shark> q, Shark shark){
        for (int i = 0; i<8; i++){
            int nx = dx[i] + shark.x;
            int ny = dy[i] + shark.y;

            if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]){
                q.offer(new Shark(nx,ny, shark.length + 1));
                visited[nx][ny] = true;
            }
        }
    }

    static class Shark {
        int x, y, length;
        Shark(int x, int y, int length){
            this.x = x;
            this.y = y;
            this.length = length;
        }
    }
}

 

 

++) 4달 후에 해당 문제를 다시 풀었다. 맞긴 했지만, 상어시점으로 탐색하지 않고 전체를 탐색했더니 메모리, 시간을 훨씬 많이 잡아 먹었다. 아래의 시간복잡도는 O(N^2*M*2)로 복잡도 자체는 크지만 N,M의 범위가 작다. ( 2 <= N,M <= 50)

최악의 경우를 따져보아도, 50^4 가 10^8*2 보단 작기때문에 가능하다. 

공간복잡도도 O(NM) 인데, 최악의 경우여도 N*M =2500, 하나당 4바이트라고 하더라도 2500 * 4 = 10KB 기 때문에 조건인 512MB로는 충분하다 

 

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

public class codingtest {

    static int N,M;
    static int[][] map;
    static int[] dx = {1,-1,0,0,-1,-1,1,1};
    static int[] dy = {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());

        map = new int[N][M];

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

        int max = 0 ; // 안전거리 최댓값 담을 변수

        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                int current_dist = bfs(i,j,0);
                max = Math.max(current_dist, max); //리턴된 안전거리와 현재까지의 안전거리 최댓값 비교하여 더 큰수로 업데이트
            }
        }

        System.out.println(max);

    }

    public static int bfs(int x, int y, int dist){
        Queue<Shark> q = new LinkedList<>();
        boolean visited[][] = new boolean[N][M];
        visited[x][y] = true;
        q.add(new Shark(x,y,dist));

        while (!q.isEmpty()){
            Shark shark = q.poll();
            // 만약 뽑은 큐가 1이라면 안전거리 return
            int current_x = shark.x;
            int current_y = shark.y;

            if (map[current_x][current_y] == 1) return shark.dist;

            for (int i = 0; i < 8; i++){
                int search_x = current_x + dx[i];
                int search_y = current_y + dy[i];

                if (search_x < 0 || search_x >= N || search_y < 0 || search_y >= M) continue;
                if (visited[search_x][search_y]) continue;

                visited[search_x][search_y] = true;
                q.add(new Shark(search_x,search_y,shark.dist+1));
            }
        }
        return 0; // 위의 return에서 안전거리 리턴 될것임.
    }

    public static class Shark{
        int x;
        int y;
        int dist;

        Shark(int x, int y, int dist){
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
}