이번문제는 bfs를 사용해야겠다 라는 감은 잡았지만 bfs+까다로운 조건이라 생각보다 어려웠다.
그래서 다른분들의 접근방법을 보고 다시 정리하여 풀었다.
내가 생각하기에 가장 핵심 조건은
1. 초기 상어의 크기는 2이다.
2. 상어는 자기보다 작은 크기의 물고기만 먹을 수 있다.
3. 상어의 크기만큼 물고기를 먹으면 크기가 커진다. (만약 상어 크기가 2이면 물고기를 2개 먹으면 상어의 크기가 3이 된다. 그리고 각 맵에 적힌 1부터 6까지는 물고기의 크기이고 어느 크기의 물고기를 먹어도 1개의 물고기를 먹은 것이기 때문에 추후의 사용된 변수 eatFishCount를 1을 더해줘야 한다.)
4. 상어는 자기와 같은 크기의 물고기는 먹지 못하고 이동만 가능하다.
5. 현재 상어 위치에서 먹을 수 있는 물고기 중 가장 가까운 물고기를 먹는다.
6. 만약 거리가 같다면 가장 위쪽에 위치한 물고기, 다 같은 y축에 있다면 가장 왼쪽에 있는 물고기 부터 먹는다.
이 두개를 통해 로직의 흐름은 이렇게 된다.
1. 먹을 수 있는 물고기의 정보(좌표, 거리)를 list에 저장한다.
2. 먹을 수 있는 물고기를 다 저장했다면 위의 조건6을 바탕으로 적합한 물고기를 먹으러 간다.
그래서 이 문제는 현재 상어 위치에서 가장 거리가 가깝고 위쪽이며 왼쪽에 있는 물고기를 찾는 while문 1개와 찾은 최적의 위치를 넣어서 더이상 이동하지 먹을 수 있는 물고기가 없을 때까지 반복하는 while문 1개로 총 2개의 while문으로 이루어져있다.
부분 코드
물고기의 위치와 거리를 저장할 class
class Node{
int x;
int y;
int dis;
public Node(int x, int y, int dis){
this.x = x;
this.y = y;
this.dis = dis;
}
}초기값 세팅
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
matrix = new int[n][n];
int sharkX = 0;
int sharkY = 0;
// 초기 상어의 크기
int sharkLevel = 2;
// 상어가 먹은 물고기의 갯수
int eatFishCount = 0;
for (int i = 0; i < n; i++) {
String[] arr = br.readLine().split(" ");
for (int j = 0; j < matrix.length; j++) {
matrix[i][j] = Integer.parseInt(arr[j]);
// 9면 상어의 위치 잡아주기
if (matrix[i][j] == 9) {
sharkX = i;
sharkY = j;
}
}
}로직
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(sharkX, sharkY, 0));
matrix[sharkX][sharkY] = 0;변수 queue는 상어가 조건에서 만족하는 물고기를 먹었을때 담길 queue이다.
queue에다가 초기에 상어의 위치를 넣어주고 상어의 위치를 0으로 해야 나중에 그 위치를 지나갈 수 있다.
while (!queue.isEmpty()) {
List<Node> findFishList = new ArrayList<>();
Queue<Node> fishQueue = new LinkedList<>();
visited = new int[n][n];
Node currentShark = queue.poll();
fishQueue.offer(currentShark);
visited[currentShark.x][currentShark.y] = 1;findFishList는 먹을 수 있는 물고기의 위치정보가 담기는 List이다.
fishQueue는 먹을 수 있는 물고기를 찾는 bfs에 사용 될 queue이다.
물고기를 찾는 bfs로직
while(!fishQueue.isEmpty()){
Node fishLocation = fishQueue.poll();
for(int i=0;i<4;i++){
int newX = fishLocation.x + dx[i];
int newY = fishLocation.y + dy[i];
if(newX >= 0 && newY >= 0 && newX < matrix.length && newY < matrix.length && visited[newX][newY] == 0 && matrix[newX][newY] <= sharkLevel){
visited[newX][newY] = visited[fishLocation.x][fishLocation.y] + 1;
fishQueue.offer(new Node(newX, newY, fishLocation.dis + 1));
if(matrix[newX][newY] < sharkLevel && matrix[newX][newY] != 0){
findFishList.add(new Node(newX, newY, fishLocation.dis+1));
}
}
}
}첫번째 if문은 단순이 이동할 수 있는 위치를 fishQueue에다가 넣어주는 것이다. 여기에서는 현재 상어의 크기와 같은 크기의 물고기의 위치도 지나갈 수 있다.
그런데 두번째 if문은 잡아먹을 수 있는지에 대한 if문이기 때문에 현재 상어의 크기보다 작아야 된다. 그래서 먹을 수 있다면 findFishList에다가 넣어준다.
위의 bfs 로직이 끝나고 난 후
if(findFishList.size() == 0) break;
Collections.sort(findFishList, (o1, o2) -> {
if(o1.dis == o2.dis){
if(o1.x == o2.x){
return o1.y - o2.y;
}
return o1.x - o2.x;
}
return o1.dis - o2.dis;
});
Node changeSharkInfo = findFishList.get(0);
matrix[changeSharkInfo.x][changeSharkInfo.y] = 0;
queue.add(changeSharkInfo);
result = changeSharkInfo.dis;
eatFishCount++;
if(eatFishCount == sharkLevel){
eatFishCount = 0;
sharkLevel++;
}만약 먹을 수 있는 물고기가 없다면 끝이 난다.
현재 거리와 위치를 통해 정렬을 한 후 가장 첫번째 값이 먹을 수 있는 물고기 중 가장 최적의 값이기 때문에 상어의 위치를 바꿔준다.
상어의 위치를 바꾸면서 물고기가 없다는 표시인 0을 넣어준다. 그리고 상어의 거리를 저장할 result 변수에 거리를 넣어주고 eatFishCount를 1 증가시켜준다.
만약 먹은 물고기의 수 == 상어 크기 라면 상어 크기를 1 올려준다.
전체코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Node{
int x;
int y;
int dis;
public Node(int x, int y, int dis){
this.x = x;
this.y = y;
this.dis = dis;
}
@Override
public String toString() {
return "Node{" +
"x=" + x +
", y=" + y +
", dis=" + dis +
'}';
}
}
public class Algorithm {
public static int[][] matrix = null;
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, -1, 0, 1};
public static boolean[][] outer = null;
public static final int INF = 10000000;
public static int[][] visited;
public static List<Integer> list = new ArrayList<>();
public static int ans = 201;
public static int result = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
matrix = new int[n][n];
int sharkX = 0;
int sharkY = 0;
int sharkLevel = 2;
int eatFishCount = 0;
for (int i = 0; i < n; i++) {
String[] arr = br.readLine().split(" ");
for (int j = 0; j < matrix.length; j++) {
matrix[i][j] = Integer.parseInt(arr[j]);
if (matrix[i][j] == 9) {
sharkX = i;
sharkY = j;
}
}
}
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(sharkX, sharkY, 0));
matrix[sharkX][sharkY] = 0;
while (!queue.isEmpty()) {
List<Node> findFishList = new ArrayList<>();
Queue<Node> fishQueue = new LinkedList<>();
visited = new int[n][n];
Node currentShark = queue.poll();
fishQueue.offer(currentShark);
visited[currentShark.x][currentShark.y] = 1;
// 먹이 리스트 찾아서 findFishList에 넣고 상어의 위치를 갱신해서 다시 돌리자
while(!fishQueue.isEmpty()){
Node fishLocation = fishQueue.poll();
// System.out.println("fishLocation = " + fishLocation.toString());
for(int i=0;i<4;i++){
int newX = fishLocation.x + dx[i];
int newY = fishLocation.y + dy[i];
if(newX >= 0 && newY >= 0 && newX < matrix.length && newY < matrix.length && visited[newX][newY] == 0 && matrix[newX][newY] <= sharkLevel){
visited[newX][newY] = visited[fishLocation.x][fishLocation.y] + 1;
fishQueue.offer(new Node(newX, newY, fishLocation.dis + 1));
if(matrix[newX][newY] < sharkLevel && matrix[newX][newY] != 0){
// System.out.println("들어갈때 fishLocation = " + fishLocation.dis);
findFishList.add(new Node(newX, newY, fishLocation.dis+1));
}
}
}
}
if(findFishList.size() == 0) break;
// for(int i=0;i<matrix.length;i++) System.out.println(Arrays.toString(visited[i]));
//
// for(Node element : findFishList){
// System.out.println("x = " + element.x + ", y = " + element.y + ", dis = " + element.dis);
// }
Collections.sort(findFishList, (o1, o2) -> {
if(o1.dis == o2.dis){
if(o1.x == o2.x){
return o1.y - o2.y;
}
return o1.x - o2.x;
}
return o1.dis - o2.dis;
});
Node changeSharkInfo = findFishList.get(0);
// System.out.println("채택된 fishList = " + findFishList.get(0).toString());
matrix[changeSharkInfo.x][changeSharkInfo.y] = 0;
queue.add(changeSharkInfo);
result = changeSharkInfo.dis;
eatFishCount++;
if(eatFishCount == sharkLevel){
eatFishCount = 0;
sharkLevel++;
}
}
System.out.println(result);
}
}
0개의 댓글
