[Baekjoon] 17086_아기 상어 2

Silver II

문제(출처: https://www.acmicpc.net/problem/17086)

---

<아기 상어 2>

문제 

 

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

어떤 칸의 안전거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

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

 

 

입력

 

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈칸, 1은 아기 상어가 있는 칸이다. 빈칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

 

출력 

 

첫째 줄에 안전거리의 최댓값을 출력한다.

 

 

문제 풀이

- my solution (JAVA)

 

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

class Solution{
	static int distance(int[] xy, int[][]arr, int n, int m) {
		Queue<int[]> queue=new LinkedList<>();
		queue.add(xy);
		
		int visited[][]=new int[n][m];
		visited[xy[0]][xy[1]]=1;
		
		int dx[]= {-1,1,0,0,-1,-1,1,1}; // 인접한 8 방향
		int dy[]= {0,0,-1,1,-1,1,-1,1};
		
		int d=0;
		while(queue.size()!=0) {
			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) {
					if(visited[x][y]==0) {
						d=temp[2]+1;
						if(arr[x][y]==1) {
							return d;
						}else {
							visited[x][y]=1;
							queue.add(new int[] {x,y,d});
						}
					}
				}
			}
		}
		return d;
	}
	public static void main(String args[]) throws Exception{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		String s=bf.readLine();
		int n=Integer.parseInt(s.split(" ")[0]);
		int m=Integer.parseInt(s.split(" ")[1]);
		
		int[][] arr=new int[n][m];
		for(int i=0; i<n; i++) {
			s=bf.readLine();
			for(int j=0; j<m; j++) {
				arr[i][j]=Integer.parseInt(s.split(" ")[j]);
			}
		}
		int result=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(arr[i][j]==0) {
					int temp=distance(new int[] {i,j,0}, arr, n,m);
					if(result<temp) {
						result=temp;
					}
				}
			}
		}
		System.out.println(result);
		}
}

 

• distance ( [x, y, 거리], arr, n, m)
  : visited = 방문 여부
  : dx, dy = 인접한 8 방향
  : queue가 빌 때까지 반복 -> 첫 번째 값을 poll 하여 인접한 8개의 방향의 x좌표, y좌표를 구함 -> arr 범위 안이며 아직 방문하지 않았다면 거리 +1 -> 만약 그 좌표의 값이 1이면 이 거리가 상어와 가까운 거리 이므로 return, 1이 아니라면 방문 표시 및 queue에 추가 
• main
  : n, m 입력
  : arr 입력
  : arr를 순환하며 arr 값이 0이라면 distance 함수 호출 
  : 반환한 값이 현재 result 값 보다 크면 result에 저장
  : result 출력

---

생각🤔

 

보통 Python으로 문제를 해결하는데 시간 초과를 해결할 수 없어 JAVA로 도전해봤다.

다행히 통과하긴 했는데.. Python으로 어떻게 더 시간을 줄여야 하는지 모르겠다.

 

---