문제 탐색하기
입력 자료 정리하기
- N과 M은 각각 배열의 세로와 가로 길이이다
- 이후 들어오는 값은 상어의 위치정보가 담겨있는 정보다
해결방법 추론
- 좌표평면 문제인데 n과 m의 크기가 작아 dp 사용 없이 BFS를 사용하면 되겠다고 생각하였다
- 브루트포스로 시작지점을 찾아야하는데, 다음 방법을 고민해볼 수 있다
(모든 위치에서 시작, 상어 위치에서 시작, 상어가 없는 위치에서 시작) - 문제에서 주어진 조건을 보았을 때, 안전거리를 구해야하는 문제이고
안전거리란 상어간의 가장 가까운 거리를 의미한다 - 따라서 상어가 없는 위치에서 시작했을 때 bfs를 통해서 안전거리를 구하고,
그 거리가 최대가 되도록 찾으면 해당 문제를 해결할 수 있다!
시간복잡도 계산
- 시간복잡도는 이전 문제와 비슷하게 계산하면 된다.
시작위치를 찾기위해 탐색하므로 n x m만큼의 연산이 발생한다 - bfs에서는 8방 탐색을 해야하므로 시작 위치당 8번의 연산이 발생한다
- 따라서 시간복잡도는 O(n x m x 8)이 발생하므로
해당 문제는 브루트포스 + BFS로 해결할 수 있다!
코드 설계하기
입력값 상태 관리하기
- 크기 입력은 n과 m 변수로 받아 관리하고 각 좌표에 해당하는 값들을 arr 배열로 받아 관리한다
탐색전 설계
- BFS를 위해서는 방문배열을 하나 만들어야한다. 좌표평면이므로 2차원 방문배열을 만들어 관리한다
- 최대값을 구하기 위해 0으로 초기화된 max 변수를 하나만들어 관리한다
브루트포스 설계
- 이중포문을 통해 모든 좌표를 탐색하면서 상어가 없으면 bfs 탐색을 진행한다
- 이때 이전 bfs 탐색의 영향을 받지 않기 위해 매 탐색전 방문배열을 초기화한다
BFS 탐색 설계
- 큐를 이용해서 BFS 탐색을 진행한다. Y,X좌표를 위해 int 타입 배열로 설정한다
- 큐에는 y,x 좌표와 함께 한가지를 더 넣어야한다. 상어가 현재 위치에서 이동했을 때의 누적 거리이다
- 0으로 초기화해서 넣어주고 시작지점 방문체크를 진행한다
- 큐에서 하나씩 뽑아 8방 탐색을 진행한다. 누적거리는 큐에서 꺼낸 이전 누적거리에 +1을 해주면 된다
- 인덱스 범위를 벗어나는지 체크하고 방문했는지도 체크하며,
모두 조건을 만족하면 해당 위치를 큐에 넣고 방문체크도 진행한다 - 이 BFS는 이전 다른 bfs와는 조금 다르게 반환값이 있다.
누적된 거리를 메인 메소드로 넘겨서 최댓값을 찾아야하기 때문이다 - 따라서 탐색 도중 만약 탐색 위치가 1이라면 탐색 누적거리를 리턴해준다
- 만약 모든 bfs 탐색에도 찾지 못한다면 0을 리턴해서 max값 변동에 영향이 없도록 한다
출력값 설계
- 앞선 bfs 탐색을 하면서 구한 max 최댓값을 출력하면 정답이 된다
정답 코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
static boolean[][] visited;
static int[] dy = {-1,-1,-1,0,0,1,1,1};
static int[] dx = {-1,0,1,-1,1,-1,0,1};
static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
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());
}
}
visited = new boolean[n][m];
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(arr[i][j] != 1){
visited = new boolean[n][m];
max = Math.max(max, bfs(i, j, n, m));
}
}
}
bw.write(max+"");
br.close();
bw.close();
}
private static int bfs(int i, int j, int n, int m) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{i, j, 0});
visited[i][j] = true;
while(!q.isEmpty()){
int[] pos = q.poll();
for (int k = 0; k < 8; k++) {
int ny = dy[k] + pos[0];
int nx = dx[k] + pos[1];
int nz = pos[2] + 1;
if(ny >= 0 && ny < n && nx >= 0 && nx < m && !visited[ny][nx]){
if(arr[ny][nx] == 1){
return nz;
}
visited[ny][nx] = true;
q.add(new int[]{ny, nx, nz});
}
}
}
return 0;
}
}
문제 링크
Software Developer