[백준/JAVA] 21608번: 상어 초등학교

📖 문제

21608번: 상어 초등학교

 

💡  풀이 방식

• 구현 + dx/dy

1. 2차원 배열로 학생 번호와, 그 학생이 좋아하는 학생들을 기록한다.

int[][] arr = new int[N * N + 1][5];

for(int i = 1 ; i <= N * N ; i++) {
    String[] str = br.readLine().split(" ");
    
    // 첫 번째 숫자 : 학생 번호 기록
    arr[i][0] = Integer.parseInt(str[0]);
    
    // 나머지 숫자 4개 : 얘가 좋아하는 학생들 기록
    for(int j = 1 ; j < 5 ; j++) {
        arr[i][j] = Integer.parseInt(str[j]);
    }
}

 

 

2. 자리를 채운다.

완전탐색으로 배열을 돌며 올바른 위치를 탐색해 해당 위치에 값을 넣는다.

  - 조건1) 비어있는 칸 中 좋아하는 학생이 인접한 칸에 가장 많은 칸

  - 조건2) 1을 만족하는 칸이 여러 개면, 인접한 칸 中 비어있는 칸이 가장 많은 칸

  - 조건3) 2를 만족하는 칸도 여러 개면, 행의 번호가 가장 작은 칸 > 열의 번호가 가장 작은 칸 💥

if(a < pos[0] || (a == pos[0] && b < pos[1])) {
    pos = new int[] {a, b};
}

 

3. 학생 만족도를 계산한다.

1부터 N*N번째 학생까지 돌며 교실에서 해당 학생의 자리를 찾고, 해당 학생 주변의 좋아하는 학생 수를 계산해 그에 따라 결과값에 누적해 더한다.

private static int aroundLike(int num, int r, int c) {
    int cnt = 0;
    
    // 인접 4방향 탐색
    for(int d = 0 ; d < 4 ; d++) {
        int nr = r + dx[d];
        int nc = c + dy[d];
        
        if(!inRange(nr, nc))    continue;
        
        // ans[nx][ny]가 num이 좋아하는 학생이면, 좋아하는 학생 수 + 1
        if(like(num, ans[nr][nc])) {
            cnt++;
        }
    }
    
    return cnt;
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    static int N;
    static int[][] arr, ans;
 
    static int result = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        arr = new int[N * N + 1][5];
 
        for(int i = 1 ; i <= N * N ; i++) {
            String[] str = br.readLine().split(" ");
 
            arr[i][0] = Integer.parseInt(str[0]);  // 첫 번째 숫자 : 학생 번호 기록
 
            // 나머지 숫자 4개 : 좋아하는 학생 기록
            for(int j = 1 ; j < 5 ; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
 
        // (1) 자리 배치 채우기
        ans = new int[N + 1][N + 1];
 
        for(int i = 1 ; i <= N * N ; i++) {
            int num = arr[i][0];
 
            int[] pos = {N, N}; // 💥 처음에 0으로 설정했음ㅠ
            int aroundCnt = 0; // 인접한 칸들 중 좋아하는 학생 수
            int emptyCnt = 0; // 인접한 칸들 중 비어있는 갯수
 
            // 배열의 올바른 위치 탐색
            for(int a = 1 ; a <= N ; a++) {
                for(int b = 1 ; b <= N ; b++) {
                    if(ans[a][b] != 0)  continue;
 
                    // 조건1. 비어있는 칸 中 좋아하는 학생이 인접한 칸에 가장 많은 칸
                    if(aroundLike(num, a, b) != aroundCnt) {
                        if(aroundLike(num, a, b) > aroundCnt) {
                            pos = new int[] {a, b};
                            aroundCnt = aroundLike(num, a, b);
                            emptyCnt = aroundEmpty(num, a, b);  // 💥 여기서 갱신 안 함
                        }
                    }
                    else {
                        // 조건2. 1을 만족하는 칸이 여러 개면, 인접한 칸 中 비어있는 칸이 가장 많은 칸
                        if(aroundEmpty(num, a, b) != emptyCnt) {
                            if(aroundEmpty(num, a, b) > emptyCnt) {
                                pos = new int[] {a, b};
                                emptyCnt = aroundEmpty(num, a, b);
                            }
                        }
                        else {
                            // 💥 조건3. 2를 만족하는 칸도 여러 개면, 행의 번호가 가장 작은 칸 > 열의 번호가 가장 작은 칸
                            if(a < pos[0] || (a == pos[0] && b < pos[1])) {
                                pos = new int[] {a, b};
                            }
                        }
                    }
                }
            }
 
            // 찾은 위치에 값 넣기
            ans[pos[0]][pos[1]] = num;
        }
 
        // (2) 학생 만족도 계산하기
        for(int i = 1 ; i <= N * N ; i++) {
            int num = arr[i][0];    // 해당 학생
 
            // 교실에서 해당 학생 자리 찾기
            int[] pos = new int[2];
 
            for(int a = 1 ; a <= N ; a++) {
                for(int b = 1 ; b <= N ; b++) {
                    if(ans[a][b] == num) {
                        pos = new int[] {a, b};
                        break;
                    }
                }
            }
 
            // 해당 학생 주변의 좋아하는 학생 수 구하기
            addResult(aroundLike(num, pos[0], pos[1]));
        }
 
        System.out.println(result);
    }
 
    // 인접 칸 中 좋아하는 학생 수 세는 메소드
    private static int aroundLike(int num, int r, int c) {
        int cnt = 0;
 
        for(int d = 0 ; d < 4 ; d++) {
            int nr = r + dx[d];
            int nc = c + dy[d];
 
            if(!inRange(nr, nc))    continue;
 
            // ans[nx][ny]가 num이 좋아하는 학생인지 판별
            if(like(num, ans[nr][nc])) {
                cnt++;
            }
        }
 
        return cnt;
    }
 
    // 인접한 칸 中 비어있는 칸 세는 메소드
    private static int aroundEmpty(int num, int r, int c) {
        int cnt = 0;
 
        for(int d = 0 ; d < 4 ; d++) {
            int nr = r + dx[d];
            int nc = c + dy[d];
 
            if(!inRange(nr, nc))    continue;
 
            // 인접한 칸이 빈 칸인지 판별
            if(ans[nr][nc] == 0) {
                cnt++;
            }
        }
 
        return cnt;
    }
 
    // num이 좋아하는 학생 中 findNum이 있는지 확인하는 메소드
    private static boolean like(int num, int findNum) {
        for(int i = 1 ; i <= N * N ; i++) {
            if(arr[i][0] == num) {
                for(int j = 1 ; j < 5 ; j++) {
                    if(arr[i][j] == findNum) {
                        return true;
                    }
                }
            }
        }
 
        return false;
    }
 
    // 만족도 계산 메소드
    private static void addResult(int cnt) {
        result += Math.pow(10, cnt - 1);
    }
 
    private static boolean inRange(int r, int c) {
        return (1 <= r && r <= N && 1 <= c && c <= N);
    }
}
 

 

 

 

➕ 다른 풀이 방식

- HashMap 사용!

 

[백준] 21608 - 상어 초등학교 (JAVA)

[백준] 21608. 상어 초등학교 (Java, 자바)

[백준] 21608번 : 상어 초등학교 - 자바[Java]

 

 

- 우선순위 큐로 여러 조건에서의 정렬 사용하심

[백준]21608: 상어 초등학교(java)

---

💦 어려웠던 점

- 처음에 자리 배치할 때 위치 배열의 초기값을 제일 작은 값 (1,1)로 설정했었다.ㅠ > (N,N)으로 설정해야 했다.

- 조건1) 비어있는 칸 中 좋아하는 학생이 인접한 칸에 가장 많은 칸을 계산할 때, 주변에 좋아하는 학생 수는 구해서 갱신했는데, 주변의 빈 칸 수는 갱신하지 않았었다.ㅠ > 주변 빈 칸 수도 함께 갱신해주었다.

- 조건 3 작성할 때 좀 헷갈렸다.

- 2시간 조금 넘게 걸렸다ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V