BOJ - 상어 초등학교 21608번 (JAVA)

❓ 문제 - 백준 상어 초등학교 21608번 - JAVA 풀이법

 

출처 

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

21608번: 상어 초등학교

 

 

📝 문제해결법

1. 이 문제는 구현의 2가지 방법으로 풀었다.

1) 구현법 1 -> 메모리 21476KB, 시간 212ms

• Student 클래스에 각 학생의 번호와 그 학생이 좋아하는 학생들의 번호를 담은 배열을 저장하고 이것을 ArrayList로 관리한다.
• map이라는 int 2차원 배열로 자리 배치 정보를 담는다. 그리고 empty int 2차원 배열로 해당 위치의 상,하,좌,우에 얼마나 많은 빈자리가 있는지 저장한다.
• 맨 처음의 학생의 배치는 모든 조건을 고려하면 map 배열에 1,1 인덱스에 위치하는 것이 최적이므로 위치시킨다.
• 학생번호 순서에 맞춰서 ArrayList에서 Student 객체를 불러와서 map의 모든 행과열을 돌면서 최적 위치를 찾아낸다.
• 돌면서 상,하,좌,우로 좋아하는 학생이 몇 명 있는지, 빈 자리 갯수의 최대값을 갱신하고, 만약 좋아하는 학생의 최대값과 같으면 빈자리 갯수의 최대값을 갱신한다. 그리고 해당 위치의 행과 열 인덱스를 저장한다.
• 이중 for문을 통해 행 , 열을 0부터 접근하므로 조건(좋아하는 학생의 수, 빈칸의 수가 같을 때 행이 작을 경우로, 행도 같을 때 열이 작은 경우)로 적용된다.
• 그 학생을 위치 시키면 상,하,좌,우의 빈칸의 갯수를 맞춰서 감소시켜준다.
• 마지막에 like_score를 계산하기 위해  다시 한번 ArrayList를 돌면서 like_score를 계산해준다.

2) 구현법 2 -> 메모리 25996KB, 시간 316ms

• 위의 구현방법에서 매번 조건에 해당하는 숫자를 비교하기 위해 empty 배열을 변화시키고, 조건에 맞도록 학생을 자리에 위치시키는 방법을 Seat이라는 클래스에 compareTo라는 메소드를 둬서 해당 조건에 맞춰 Seat 객체를 담은 ArrayList를 정렬하도록 구현했다. -> 정렬 후 0 인덱스에 해당 조건과 가장 부합하는 자리이므로 이 자리에 학생을 위치 시킨다.
• compareTo 메소드 구현 내용에는 만약 행과 열의 위치에서 상,하,좌,우에 좋아하는 학생의 수도 같고, 빈칸의 수도 같고, 행의 값도 같으면 열이 작은 값으로 오름차순 정렬하라. / 만약 행과 열의 위치에서 상,하,좌,우에 좋아하는 학생의 수도 같고, 빈칸의 수도 같으면 행의 값으로 오름차순 정렬하라./ 만약 행과 열의 위치에서 상,하,좌우에 좋아하는 학생의 수가 같으면 빈칸의 수로 내림차순 정렬하라. / 만약 행과 열의 위치에서 상,하,좌우에 좋아하는 학생의 수로 오름차순 정렬하라. ->> 이러한 로직으로 정렬하도록 compareTo 메소드를 구현하면 됨
• 이중 for문을 통해 학생 순서에 맞춰서 seat객체 배열 리스트에 해당 자리 정보를 넣은 후, 위 조건대로 정렬하도록 한다.
• 구현법1과 동일하도록 like_score을 계산한다.

3) 느낀점

• 처음 파이썬에서 구현2번 로직으로 풀었다. 그런데 파이썬에서는 정렬할 때 람다를 간단하게 이용하면 문제를 풀었는데... 자바는 직접 comparable 인터페이스를 통해 compareTo 메소드를 직접 조건에 맞춰 구현했어야 했다..
• 그래서 그냥 구현 방법으로 푼 후, 현재 몸 담고 있는 교육기관에서 해당 강의를 보고 정렬을 통해 자리 착석하도록 열심히 구현했지만 구현1번이 훨씬 메모리적으로나 시간복잡도 면에서 좋은 풀이였다... ㅎㅎㅎ
• 이번 경험은 comparable 인터페이스를 알 수 있게 하는 좋은 경험으로 자리잡겠다 ^_^

 

💻 소스코드 (구현1)

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

public class Main_21608 {
    static class Student {
        int stu_num;
        int[] stu_like;

        public Student(int stu_num, int[] stu_like){
            this.stu_num = stu_num;
            this.stu_like = stu_like;
        }

    }


    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static ArrayList<Student> stu;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        stu = new ArrayList<>();
        Map<Integer, Student> h_stu = new HashMap<>();


        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n*n;i++){
            String[] like = br.readLine().split(" ");

            int[] l = new int[4];
            for(int j=1;j<5;j++){
                l[j-1] = Integer.parseInt(like[j]);
            }
            Student s = new Student(Integer.parseInt(like[0]), l);
            stu.add(s);
        }
        int[][] empty = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                empty[i][j] = 4;
                if(i == 0 || i == n-1)
                    empty[i][j]--;
                if(j == 0 || j == n-1)
                    empty[i][j]--;
            }
        }
        int[][] map = new int[n][n];
        map[1][1] = stu.get(0).stu_num;
        empty[0][1]--;
        empty[2][1]--;
        empty[1][0]--;
        empty[1][2]--;


        for(int k=1;k<n*n;k++){
            Student  s = stu.get(k);
            int[][] like = new int[n][n];

            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(map[i][j] != 0)
                        continue;

                    for(int d=0;d<4;d++){
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        if(0 <= nx && nx < n && 0 <= ny && ny < n) {
                            for (int s_n : s.stu_like) {
                                if(s_n == map[nx][ny]){
                                    like[i][j]++;
                                }
                            }
                        }
                    }
                }
            }

            int max_empty = -1;
            int max_like = -1;
            int row = -1;
            int col = -1;

            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(map[i][j] != 0)
                        continue;
                    if(like[i][j] > max_like){
                        max_like = like[i][j];
                        max_empty = empty[i][j];
                        row = i;
                        col = j;
                    } else if(like[i][j] == max_like && empty[i][j] > max_empty){
                        max_empty = empty[i][j];
                        row = i;
                        col = j;
                    }
                }
            }

            map[row][col] = s.stu_num;
            h_stu.put(s.stu_num, s);
            for(int d=0;d<4;d++){
                int nx = row + dx[d];
                int ny = col + dy[d];
                if(0 <= nx && nx < n && 0 <= ny && ny < n){
                    empty[nx][ny]--;
                }
            }


        }


        int like_score = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int cnt = 0;
                for(int k=0;k<stu.size();k++){
                    if(stu.get(k).stu_num == map[i][j]){
                        for(int d=0;d<4;d++){
                            int nx = i + dx[d];
                            int ny = j + dy[d];
                            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                                for(int s_n:stu.get(k).stu_like){
                                    if(map[nx][ny] == s_n){
                                        cnt++;
                                    }
                                }
                            }
                        }

                    }
                }

                if(cnt == 1){
                    like_score++;
                } else if(cnt == 2){
                    like_score += 10;
                } else if(cnt == 3){
                    like_score += 100;
                } else if(cnt == 4){
                    like_score += 1000;
                }

            }
        }

        bw.write(String.valueOf(like_score));
        bw.flush();
        bw.close();
    }
}

💻 소스코드 (구현2)

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

public class Main_21608_2 {
    static class Student {
        int stu_num;
        int[] stu_like;

        public Student(int stu_num, int[] stu_like){
            this.stu_num = stu_num;
            this.stu_like = stu_like;
        }

    }


    static class Seat implements Comparable<Seat>{
        int row;
        int col;
        int like_cnt;
        int empty_cnt;
        public Seat(int row, int col, int like_cnt, int empty_cnt){
            this.row = row;
            this.col = col;
            this.like_cnt = like_cnt;
            this.empty_cnt = empty_cnt;
        }

        @Override
        public int compareTo(Seat o) {
            if(this.like_cnt == o.like_cnt){
                if(this.empty_cnt == o.empty_cnt){
                    if(this.row == o.row){
                        return this.col - o.col;
                    } else {
                        return this.row - o.row;
                    }
                } else{
                    return -(this.empty_cnt - o.empty_cnt);
                }
            }
            return -(this.like_cnt - o.like_cnt);
        }


    }


    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static ArrayList<Student> stu;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        stu = new ArrayList<>();


        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n*n;i++){
            String[] like = br.readLine().split(" ");

            int[] l = new int[4];
            for(int j=1;j<5;j++){
                l[j-1] = Integer.parseInt(like[j]);
            }
            Student s = new Student(Integer.parseInt(like[0]), l);
            stu.add(s);
        }

        int[][] map = new int[n][n];
        map[1][1] = stu.get(0).stu_num;

        for(int k=1;k<n*n;k++){
            Student  s = stu.get(k);
            ArrayList<Seat> seat_list = new ArrayList<>();
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    int sum_like = 0;
                    int sum_empty = 0;
                    if(map[i][j] != 0) continue;

                    for(int d=0;d<4;d++){
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1){
                            continue;
                        }

                        for(int l:s.stu_like){
                            if(map[nx][ny] == l){
                                sum_like += 1;
                            }
                        }

                        if(map[nx][ny] == 0){
                            sum_empty++;
                        }

                    }

                    seat_list.add(new Seat(i, j, sum_like, sum_empty));
                }
            }
            Collections.sort(seat_list);
            int row = seat_list.get(0).row;
            int col = seat_list.get(0).col;

            map[row][col] = s.stu_num;

        }


        int like_score = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int cnt = 0;
                for(int k=0;k<stu.size();k++){
                    if(stu.get(k).stu_num == map[i][j]){
                        for(int d=0;d<4;d++){
                            int nx = i + dx[d];
                            int ny = j + dy[d];
                            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                                for(int s_n:stu.get(k).stu_like){
                                    if(map[nx][ny] == s_n){
                                        cnt++;
                                    }
                                }
                            }
                        }

                    }
                }

                if(cnt == 1){
                    like_score++;
                } else if(cnt == 2){
                    like_score += 10;
                } else if(cnt == 3){
                    like_score += 100;
                } else if(cnt == 4){
                    like_score += 1000;
                }

            }
        }

        bw.write(String.valueOf(like_score));
        bw.flush();
        bw.close();
    }
}