[구현] - G5_21608_상어 초등학교

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

21608번: 상어 초등학교

처음에 문제를 읽으면서 이게 무슨 소린가 싶었는데, 하나씩 조건을 따지면서 보니까 할만하다 생각이 들었다.

문제를 보니까 메모리 부분은 아예 신경쓸 필요도 없을 뿐더러, 오히려 그냥 막 써도 되겠다 싶어서 일부러 학생 테이블을 2개 만들어서 하나는 입력받은 대로 학생과 그 학생이 좋아하는 학생의 숫자들을 student에 저장을 했고, 동시에 학생 번호를 순서대로 student2에 저장을 하면서 나중에 사용하기 쉽도록 만들었다.

 

📌- 풀이

1. 입력을 받으면서 student에는 순서대로 학생들을 저장하고, student2에는 학생번호 순서대로 저장함
2. 학생 수만큼 N*N 배열을 처음부터 끝까지 반복하면서 학생이 들어갈 자리를 찾음
3. 예를들어 0,0에서 상,하,좌,우를 살피면서 현재 학생이 좋아하는 학생이 있는지 찾으면서 score를 늘려주고, 빈공간이 있으면 emptyScore를 늘려줌
4. score가 가장 큰 maxScore보다 높으면 갱신을 해주고 x,y값에 해당 위치를 넣어줌 => score가 maxScore와 같다면 emptyScore를 기준으로 반복함
5. 갱신을 하게 되면 마지막 x,y값이 해당 학생이 들어갈 수 있는 최적의 위치이기 때문에 해당 위치에 학생을 배치해준다.
6. 배치한 결과를 바탕으로 점수를 메겨서 result를 구함

 

이 문제는 완전 구현 문제라 숫자 하나하나 print로 찍어보면서 한다고 생각보다 시간이 많이 걸리기도 했고, 중간중간에 조건을 조금이라도 잘못 걸면 완전 틀리게 되어버려서 머리도 아프고 시간도 더 많이 걸린 것 같음. 

 

그리고 마지막에 실수를 했던 부분이

  if(arr[x][y] !=0)
  {
        x=i;
        y=j;
  }

 

 

score도 같고 emptyScore도 같은 자리가 겹칠 경우에 자리를 배치할 때, 해당하는 자리에 이미 학생이 배치되어 있다면 현재 위치에 자리를 배치해줘야 하는데 이걸 빼먹어서 시간을 더 써먹었다.

 

예를 들어서

5 7 6

3 9 2

1 4 0

 

0의 자리에 8을 넣어야 되는데 5가 들어가있는 자리와 현재 0인 자리에서 score와 emptyScore가 같다면 5번 자리에 8을 덮어서 넣어버리는 문제가 생겨서 해당 번호가 0이 아니라면(이미 배치된 자리) 아직 배치가 안된 0에 8을 집어 넣으면 정답이 된다.

🔥 - Java 코드

 

package 구현.G5_21608_상어초등학교;

import java.io.*;
import java.util.*;

public class Main {
    public static int N;
    public static int[][] arr, student,student2;
    public static boolean[] seat;

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        seat = new boolean[N * N + 1];
        arr = new int[N][N];
        student = new int[N * N + 1][5];
        student2 = new int[N * N + 1][5];
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};


        for (int i = 0; i < N * N; i++) {
            st = new StringTokenizer(br.readLine());
            int num1=Integer.parseInt(st.nextToken());
            int num2=Integer.parseInt(st.nextToken());
            int num3=Integer.parseInt(st.nextToken());
            int num4=Integer.parseInt(st.nextToken());
            int num5=Integer.parseInt(st.nextToken());

            student[i][0] = num1;
            student[i][1] = num2;
            student[i][2] = num3;
            student[i][3] = num4;
            student[i][4] = num5;

            student2[num1][0] =num1;
            student2[num1][1] =num2;
            student2[num1][2] =num3;
            student2[num1][3] =num4;
            student2[num1][4] =num5;


        }


        for (int v = 0; v < N * N; v++) {
            int x = 0;
            int y = 0;
            int maxScore = 0;
            int emptyMaxScore = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int score = 0;
                    int emptyScore = 0;
                    if (arr[i][j] != 0) {
                        continue;
                    }
                    for (int z = 0; z < 4; z++) {
                        int nx = i + dx[z];
                        int ny = j + dy[z];
                        if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                            if (arr[nx][ny] == student[v][1] || arr[nx][ny] == student[v][2] || arr[nx][ny] == student[v][3] || arr[nx][ny] == student[v][4]) {
                                score++;
                            }
                            if (arr[nx][ny] == 0) {
                                emptyScore++;
                            }
                        }
                    }
                    if (score > maxScore) {
                        x = i;
                        y = j;
                        maxScore = score;
                        emptyMaxScore = emptyScore;
                    } else if (score == maxScore) {
                        if (emptyScore > emptyMaxScore) {
                            x = i;
                            y = j;
                            emptyMaxScore = emptyScore;
                        }
                    }
                    if(arr[x][y] !=0){
                        x=i;
                        y=j;
                    }
                }
            }
            arr[x][y] = student[v][0];
        }




        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int score = 0;
                for (int z = 0; z < 4; z++) {
                    int nx = i + dx[z];
                    int ny = j + dy[z];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                        if (arr[nx][ny] == student2[arr[i][j]][1] || arr[nx][ny] == student2[arr[i][j]][2] || arr[nx][ny] == student2[arr[i][j]][3] || arr[nx][ny] == student2[arr[i][j]][4]) {
                            score++;
                        }
                    }

                }
                if (score == 0) {
                    result += 0;
                } else if (score == 1) {
                    result += 1;
                } else if (score == 2) {
                    result += 10;
                } else if (score == 3) {
                    result += 100;
                } else {
                    result += 1000;
                }
            }


        }

        System.out.println(result);
    }

}