첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
진짜 조건이 많아도 너무 많다..
우선은 가중치가 1인 그래프에서의 최단거리이기때문에 bfs
로 결정
코드에 대한 세세한 설명은 주석으로 처리해 표기해두었다
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 Node {
int x, y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static int N;
static int[][] maps, dist; // 0: 빈칸, 9: 상어의 위치, 1~6: 칸에 있는 물고기 크기
static int minDist,minX, minY;
static int sharkSize = 2;
static int sharkX = 0, sharkY = 0;
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());
maps = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
maps[i][j] = Integer.parseInt(st.nextToken());
if (maps[i][j] == 9) {
sharkX = i;
sharkY = j;
maps[i][j] = 0;
}
}
}
int cnt = 0;
int eat = 0;
while (true) {
// dist[][]는 방문 여부 체크와 함께 시작점에서 해당 좌표까지의 거리를 표시한다.
// (dist[][] == 0이면 방문 안한 곳)
dist = new int[N][N];
minX = -1;
minY = -1;
minDist = Integer.MAX_VALUE;
bfs(sharkX, sharkY);
// 상어 사이즈와 물고기를 먹은 횟수를 비교해 같으면 -> 상어 사이즈++
if (minX >=0 && minY >=0) {
// 물고기가 먹힌 경우에는 물고기 좌표의 값을 0으로 바꿔주고
// 상어 좌표의 값을 기존의 물고기 좌표값으로 바꿔줌
// 그리고 해당 칸에 담긴 거리값을 총 거리에 추가
eat++;
maps[minX][minY] = 0;
sharkX = minX;
sharkY = minY;
cnt += dist[minX][minY];
if (eat == sharkSize) {
sharkSize++;
eat = 0;
}
}else break;
}
System.out.println(cnt);
}
static void bfs(int x, int y) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(x, y));
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
// 상어가 움직일 수 있는 칸인지, 방문 안한 곳인지 확인
if (isInArea(nx, ny) && isAbleToMove(nx, ny) && dist[nx][ny] == 0) {
dist[nx][ny] = dist[cur.x][cur.y] + 1;
// 해당 칸에 먹을 수 있는 물고기가 존재하는 경우
// 최소값에 대한 정보 저장
if (maps[nx][ny]!= 0 && maps[nx][ny]<sharkSize) {
if (minDist > dist[nx][ny]) {
minDist = dist[nx][ny];
minX = nx;
minY = ny;
} else if (minDist == dist[nx][ny]) {
// 가장 거리가 짧은 물고기가 여러 마리인 경우
// 위부터, 그것도 같으면 왼쪽부터
if (minX == nx) {
if (minY > ny) {
minY = ny;
}
} else if (minX > nx) {
minX = nx;
minY = ny;
}
}
}
queue.add(new Node(nx, ny));
}
}
}
}
// 해당 좌표가 maps의 범위 내에 존재하는지
static boolean isInArea(int x, int y) {
return (x<N && x>=0 && y<N && y>=0);
}
// 해당 칸을 상어가 지나쳐갈 수 있는지 (상어 사이즈보다 작거나 같은 값이어야함)
static boolean isAbleToMove(int x,int y){
return maps[x][y] <= sharkSize;
}
}
*참고 - 풀이를 쓸거면 이렇게 써야하는데..라고 생각이 들 정도로 자세하게 설명해두셨다