백준[자바 java] 17086 : 아기상어 2

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

오래전에 풀었던 문제인데 쉬운 문제부터 다시 감잡으려고 풀었다.

 

bfs로 각 격자 중 아기상어로부터 가장 멀리 떨어져있는 격자의 거리를 구하는 문제이다.

 

이 문제에서는 위, 아래, 양 옆, 대각선 총 8개의 격자를 탐색해야했다.

이를 하나하나 코드화하기는 지저분하고 힘드니까 dx,dy테크닉을 사용하였다.

 

또한 한번 방문한 격자는 다시 방문하는 것은 메모리, 시간 낭비이므로 vis배열을 이용하여 중복탐지를 하였다.

 

bfs의 사이클을 탐지하기 위해서 x,y값이 -1인 값을 매 사이클이 시작할 때마다 넣었다.

만약 방금 poll 한 값이 -1이라면 이건 사이클이 한번 돌았다는 이야기이므로, 거리를 하나 더해주고, 새로운 (-1,-1)객체를 큐에 넣었다.

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

class xy{
  int x;
  int y;

  public xy(int x, int y){
    this.x = x;
    this.y = y;
  }

}

public class Main {

  public static void main(String[] args) throws IOException {
    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());

    int[][] arr = new int[n][m];

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

    int ans = 0;

    int[] dx = {1,0,-1,0,1,1,-1,-1};
    int[] dy = {0,1,0,-1,1,-1,1,-1};



    for(int i = 0;i<n;i++){
      for(int j = 0;j<m;j++){
        int cnt = 0;
        if(arr[i][j] == 0){
          Queue<xy> q = new LinkedList<xy>();
          q.offer(new xy(i,j));
          q.offer(new xy(-1,-1));
          int[][] vis = new int[n][m];
          vis[i][j] = 1;

          while(!q.isEmpty()){
            xy now = q.poll();
            if(now.x == -1) {
              cnt++;
              q.offer(new xy(-1,-1));
              continue;
            }
            if(arr[now.x][now.y] == 1) break;

            for(int k =0 ;k<8;k++){
              int nx = now.x + dx[k];
              int ny = now.y + dy[k];
              if(nx < n && nx >= 0 && ny < m && ny >= 0&&vis[nx][ny] == 0){
                q.offer(new xy(nx,ny));
                vis[nx][ny] = 1;
              }
            }
          }
        }
       // System.out.println(cnt);
        if(cnt > ans) ans = cnt;

      }
    }

    System.out.println(ans);

  }
}