[BFS] 백준 - 아기상어 2 (17086)

-문제

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

17086번: 아기 상어 2

 

-문제풀이

더 좋은 풀이가 있지만 

나는 기본에 충실한다는 생각으로 기본적인 BFS풀이로 풀었다.

 

1. sea[][] 2차원 배열에 입력값들을 입력받는다.

2. 이중 for문 안에서 BFS() 메서드를 호출한다.

이때 BFS() 메서드의 반환값은 가장 가까운 상어가 있는 공간까지의 거리를 반환해준다.

3. BFS() 메서드의 반환값을 tmp라는 변수에 저장하고 현재 answer과 비교한다.

tmp가 answer보다 크면 answer을 tmp로 교체해준다.

4. 최종적으로 answer를 출력하고 끝낸다.

 

 

BFS메서드를 살펴보면 

위의 2번에서 이중 for문으로 들어올 때 x, y좌표값을 매개변수로 넘겨받는다.

 

그리고 LinkedList인 큐를 생성하고

현재 좌표값을 큐에 1차원 배열로 집어넣는다.

이때 1차원 배열 요소로는 x좌표, y좌표, 현재까지의 거리

 

현재까지의 거리는 상어가 있는 공간까지의 거리를 의미하고

처음 BFS() 메서드를 호출한 좌표에서는 당연히 0이다.

 

그리고 8방향을 탐색하면서 8방향에 상어가 없으면 현재까지의 거리를 1 올려준다.

 

8방향중에 상어가 있다면 현재까지의 거리를 1올려주고 리턴해준다.

 

 

 

-자바

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

class Main {
    
    static int N, M, sea[][], answer;
    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;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt( st.nextToken() );
        M = Integer.parseInt( st.nextToken() );
        
        sea = new int[N][M];
                
        for( int i=0; i<N; i++ ) {
            st = new StringTokenizer( br.readLine() );
            for( int j=0; j<M; j++ ) {
                sea[i][j] = Integer.parseInt( st.nextToken() );
            }
        }
        
        int tmp = 0;
        for( int i=0; i<N; i++ ) {
            for( int j=0; j<M; j++ ) {
                if( sea[i][j] == 1 ) continue;
                
                tmp = BFS(i, j);
                answer = tmp > answer ? tmp : answer;                
            }
        }
        System.out.println( answer );     
    }
    
    
    static int BFS( int x, int y ) {
        boolean visit[][] = new boolean[N][M];
        Queue<int[]> q = new LinkedList<int[]>();
        
        q.add(new int[] {x, y, 0});
        visit[x][y] = true;
        
        while( !q.isEmpty() ) {
            int now[] = q.poll();
            
            for( int i=0; i<8; i++ ) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                int val = now[2];
                
                if( nx<0 || ny<0 || nx>=N || ny>=M ) continue;
                if( visit[nx][ny] == true ) continue;
                if( sea[nx][ny] == 1 ) return val+1;
                visit[nx][ny] = true;
                q.add( new int[] {nx, ny, val+1} );
            }
        }
        return 0;
    }
}

 

-파이썬