[BOJ - JAVA] SSAFY 8기 코테 후기 + 16236 - 아기 상어 (시뮬레이션, BFS + DP), 삼성 코테 기출

# 주소

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

# 문제

# 문제 해설 및 코드 리뷰

package com.core.hello;

import java.util.*;
class Point{
    int x;
    int y;
    int cnt;
    Point(int x, int y, int cnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}
class  Main{
    static int n;
    static int SIZE = 2;
    static int cnt = 0;
    static int answer = 0;
    static boolean[][] visit;
    static int[][] arr;
    static int[][] map;
    static Queue<Point> queue = new LinkedList<>();
    static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        map = new int[n][n];
        visit = new boolean[n][n];
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        while(true) {
            int mx = 0;
            int my = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(arr[i][j] == 9){
                        mx = i;
                        my = j;
                        break;
                    }
                }
            }
            if(possible(mx, my))
                break;
            int temp = Integer.MAX_VALUE;
            arr[mx][my] = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(map[i][j] < temp && map[i][j] > 0){
                        temp = map[i][j];
                        mx = i;
                        my = j;
                    }
                }
            }
            arr[mx][my] = 9;
            answer += map[mx][my];
            cnt++;
            if(SIZE == cnt){
                SIZE++;
                cnt = 0;
            }
        }
        System.out.println(answer);
    }
    static boolean possible(int x, int y){
        map = new int[n][n];
        visit = new boolean[n][n];
        int temp = SIZE;
        queue = new LinkedList<>();
        queue.offer(new Point(x, y, 0));
        visit[x][y] = true;
        while(!queue.isEmpty()){
            Point now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(arr[nx][ny] > SIZE)
                    continue;
                if(arr[nx][ny] == 0){
                    queue.offer(new Point(nx, ny, now.cnt + 1));
                    visit[nx][ny] = true;
                    continue;
                }
                if(arr[nx][ny] == SIZE){
                    queue.offer(new Point(nx, ny, now.cnt + 1));
                    visit[nx][ny] = true;
                    continue;
                }
                if(arr[nx][ny] < SIZE) {
                    temp = Math.min(arr[nx][ny], temp);
                    queue.offer(new Point(nx, ny, now.cnt + 1));
                    visit[nx][ny] = true;
                    map[nx][ny] = now.cnt + 1;
                }
            }
        }
        return temp == SIZE;
    }
}

 

약 한 달 만에 포스팅 합니다.

그 동안 SSAFY코테 시험 대비를 위해 SWEA D2 ~ D4 문제 푸느라 포스팅보단 더 다양한 문제들을 풀어보려 했습니다.

선택과 집중이란 말이 있잖아요 ㅎ 최대한 많이 풀어봤더니 그래도 2문제가 출제되었는데 한 문제는 확실히 맞을 것 같고 2 번째 문제에서 갈리지 않을까 ... 싶습니다.

2번째 문제가 자꾸 시간초과가 나서 ㅎㅎ 결국 좀 더 간단한 풀이로 바꾸느라 시간을 많이 할애했네요.

총 80분이 주어졌는데 1번 문제는 19분 만에 풀었는데 2번째 문제를 한 시간 할애해도 부족했습니다.

하필 제가 제일 약한 부분에서 출제가 되었더라구요 ㅠㅠㅠ 제 블로그에도 없는 문제입니다..

하지만 코테에서 자주 나오는 영역이라 앞으로 제가 포스팅하는 문제 영역이 해당 문제와 비슷(?)하지 않을까 싶네요.

그래서 2번째 문제는 쉬운 코드로 바꿔서 풀었습니다만 이래도 정답과는 거리가 멀거에요. 나중에 다시 생각해보니 아애 잘못풀었더라고요 ㅋㅋㅋ.

그래서 이번 SSAFY시험도 그냥 떨어졌다 생각하고 취준할려 합니다..

SSAFY시험은 치루면 치룰수록 뭔가 저를 밀어내는? 느낌이 자꾸 들어서 많이 망설여지기도 합니다.. 

전 다가가고 있는데 자꾸 날 밀쳐내 ㅠ

어쨌든 시험 치고 따끈따끈한 삼성 기출 코테 문제룰 한 번 풀어봤는데 공략 삼아서 한 번 풀어보겠습니다 ㅎ.

import java.util.*;
class Point{
    int x;
    int y;
    int cnt;
    Point(int x, int y, int cnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

저는 Point클래스를 오버라이딩하여 x는 x좌표, y는 y좌표, cnt는 이동거리로 설정하였습니다.

static int n;
static int SIZE = 2;
static int cnt = 0;
static int answer = 0;
static boolean[][] visit;
static int[][] arr;
static int[][] map;
static Queue<Point> queue = new LinkedList<>();
static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};

전역 변수는 다음과 같이 설정했습니다.

arr와 visit의 크기를 결정할 n과 현재의 상어의 크기를 뜻하는 SIZE = 2로, 그리고 먹이를 먹은 횟수를 뜻하는 cnt = 0으로 두었습니다.

answer는 정답을 의미하며 visit은 BFS로 탐색할 때 재방문을 피하기 위해 선언합니다.

arr는 입력 먹이 배열을 저장할 2차원 배열, map은 상어의 위치에서 갈 수 있는 먹이들에 한정된 이동거리를 의미합니다.

이를 위해 Queue를 사용할 것이고 방햑 벡터인 dir를 총 4방향으로 설정합니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n][n];
map = new int[n][n];
visit = new boolean[n][n];
for(int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        arr[i][j] = scan.nextInt();
    }
}

입력은 이렇게 받겠습니다.

이후 while문을 사용하여 먹이가 없을 때 while문을 빠져나오는 식으로 하겠습니다.

while(true) {
    int mx = 0;
    int my = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(arr[i][j] == 9){
                mx = i;
                my = j;
                break;
            }
        }
    }

따라서 mx와 my를 선언하는데, 이는 arr가 9값이 나오면(상어의 위치) 해당 인덱스를 my와 my에 저장합니다.

이를 while문 마다 반복해야하는 이유는 상어가 이동할 때마다 9의 위치가 갱신되기 때문입니다.

if(possible(mx, my))
    break;

이후 possible이 true이면 while문을 빠져나오도록 할 것인데요.

static boolean possible(int x, int y){
    map = new int[n][n];
    visit = new boolean[n][n];
    int temp = SIZE;
    queue = new LinkedList<>();
    queue.offer(new Point(x, y, 0));
    visit[x][y] = true;
    while(!queue.isEmpty()){
        Point now = queue.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                continue;
            if(visit[nx][ny])
                continue;
            if(arr[nx][ny] > SIZE)
                continue;
            if(arr[nx][ny] == 0){
                queue.offer(new Point(nx, ny, now.cnt + 1));
                visit[nx][ny] = true;
                continue;
            }
            if(arr[nx][ny] == SIZE){
                queue.offer(new Point(nx, ny, now.cnt + 1));
                visit[nx][ny] = true;
                continue;
            }
            if(arr[nx][ny] < SIZE) {
                temp = Math.min(arr[nx][ny], temp);
                queue.offer(new Point(nx, ny, now.cnt + 1));
                visit[nx][ny] = true;
                map[nx][ny] = now.cnt + 1;
            }
        }
    }
    return temp == SIZE;
}

possible함수를 살펴보겠습니다.

map과 visit을 항상 새로 선언하여야 합니다.

그래야만 다시 possible함수를 실행할 때(먹이를 찾을 수 있는지 확인할 때) 에러 없이 원할하게 실행 가능합니다.

queue도 비워주고 queue에 x,y,0을 삽입한 뒤 visit도 true로 지정합니다.

Point now = queue.poll();
for(int i = 0; i < 4; i++){
    int nx = now.x + dir[i][0];
    int ny = now.y + dir[i][1];
    if(nx < 0 || ny < 0 || nx >= n || ny >= n)
        continue;
    if(visit[nx][ny])
        continue;
    if(arr[nx][ny] > SIZE)
        continue;
    if(arr[nx][ny] == 0){
        queue.offer(new Point(nx, ny, now.cnt + 1));
        visit[nx][ny] = true;
        continue;
    }

이후 4방향에 대해 인덱스 설정을 다음과 같이 진행합니다.

만약 방문했거나 arr가 SIZE보다 크거나(못 먹는 먹기) 인덱스 밖으로 튀어나가면 모두 continue해줍니다.

또한 arr값이 0인 지점은 그냥 통과할 수 있는 곳이므로 queue에 새로 삽입하고 visit도 true로 한 뒤 continue합니다.

if(arr[nx][ny] == SIZE){
    queue.offer(new Point(nx, ny, now.cnt + 1));
    visit[nx][ny] = true;
    continue;
}
if(arr[nx][ny] < SIZE) {
    temp = Math.min(arr[nx][ny], temp);
    queue.offer(new Point(nx, ny, now.cnt + 1));
    visit[nx][ny] = true;
    map[nx][ny] = now.cnt + 1;
}

이후 arr값이 SIZE와 같은 곳이면 지나갈 수만 있는 곳이므로 queue에 삽입하고 visit도 true로 두고 똑같이 continue합니다.

또한 만약 arr가 SIZE보다 적을 때에는 temp에 arr값과 temp를 비교하여 temp에 삽입합니다.

이후 queue에 nx,ny를 넣고 visit도 true로 두며 map에는 현재의 now.cnt + 1을 한 값을 삽입합니다.

이는, 먹이가 생길 때마다 map에 값도 유효하게 들어갈 것을 의미합니다.

모두 마친 뒤 만약 temp가 SIZE와 같다면 먹을 수 있는 먹이가 없다는 뜻이므로 false를, temp != SIZE면 true를 return합니다.

예를 들어

3

9 2 4

2 2 3

1 3 1 이런 예제가 들어왔다 생각해봅시다.

9의 위치에서 방문할 수 있는 지점은 왼쪽 아래의 1밖에 없을 것입니다.

따라서 정답도 2가 출력되어야 합니다.

그러므로 무작정 방문할 수 있는 지점을 탐색할 수 있는 것이 아니고 먹을 수 있는 먹이가 1이상 존재하는 곳에 대한 map을 새로 꾸려야만 이 문제를 풀 수 있다고 접근해야합니다.

이 모든 것을 마치면 map에는 먹을 수 있는 먹이가 담긴 2차원 배열이 생성될 것입니다.

int temp = Integer.MAX_VALUE;
arr[mx][my] = 0;
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        if(map[i][j] < temp && map[i][j] > 0){
            temp = map[i][j];
            mx = i;
            my = j;
        }
    }
}

이후 arr의 9가 있던 지점은 0으로 꼭 바꾸어 주고 2중 for문을 이용하여 temp보다 작은 map의 값을(0보다 큰) 찾아서 temp로 갱신합니다.

여기에서 아래보다 위쪽 행이 우선순위이고 오른쪽보다 왼쪽 열이 우선적이라는 문제 조건을 만족시킬 수 있습니다.

이렇게 갱신된 mx와 my는 아기 상어가 다음에 먹으러 갈 먹이를 찾은 것입니다. 

따라서 아기 상어는 해당 mx와 my를 9로 바꾸고 그 위치로 이동하며 해당 map의 값을 answer에 더해줍니다.

또한 cnt도 1 증가시켜주며 만약 cnt가 SIZE가 된다면 SIZE를 1 증가시키고 cnt는 0으로 초기화시킵니다.

이 모든 것을 먹을 수 있는 먹이만 있다면 계속 반복시켜주기 때문에 while문을 이용하는 것입니다.

그리고 먹을 수 있는 값이 없고 SIZE와 같은 지점만 존재하거나 먹을 수 없는 먹이만 근처에 있다면 즉시 while문은 종료될 것입니다.

감사합니다.