백준 21608번 상어 초등학교

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

import java.util.StringTokenizer;

public class Shark_School {
    static int N;
    static int[][] studentLike;
    static int[][] map;
    static int answer =0;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        studentLike = new int[N*N][5];
        map = new int[N][N];
        for (int i = 0; i < N*N; i++) {
            st = new StringTokenizer(br.readLine());
            studentLike[i][0] = Integer.parseInt(st.nextToken());//학생의 번호
            studentLike[i][1] = Integer.parseInt(st.nextToken());//좋아하는 학생의 번호
            studentLike[i][2] = Integer.parseInt(st.nextToken());
            studentLike[i][3] = Integer.parseInt(st.nextToken());
            studentLike[i][4] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N*N; i++) {
            List<int[]> list = new ArrayList<>();
            MapSearch(i,list);//자리 하나씩 탐색
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                satisfaction(i,j);//만족도 탐색
            }
        }

        System.out.println(answer);
    }
    public static void satisfaction(int row,int col){
        int num = 0;
        for (int i = 0; i < N * N; i++) {
            if(map[row][col]==studentLike[i][0]){// 해당 자리에 앉은 학생이 studentLike에 몇번째 배열 학생인지 num에 담는다.
                num = i;
                break;
            }
        }
        int count = 0;
        for (int i = 0; i < 4; i++) {// 상하좌우 탐색
            int nrow = row+dr[i];
            int ncol = col+dc[i];
            if(nrow<0||ncol<0||nrow>=N||ncol>=N)
                continue;
            for (int k = 1; k < 5; k++) {// studentLike배열을 탐색하며 좋아하는 학생인지 탐색
                if(map[nrow][ncol]==studentLike[num][k]){
                    count++;
                }

            }
        }
        if(count==1){//만족도 환산
            answer+=1;
        }else if(count==2){
            answer+=10;
        }else if(count==3){
            answer+=100;
        }else if(count==4){
            answer+=1000;
        }
    }
    /**
     * seq: 몇번째 학생인지
     */
    public static void MapSearch(int seq,List<int[]> list){//자리 하나씩 탐색 
        int max = Integer.MIN_VALUE;
        int[][] likeCount = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j]!=0)// 자리에 누가 앉아있다면 해당자리는 탐색하지 않음
                    continue;
                likeCount[i][j] = LikeSearch(seq,i,j);// 현재 좌표에서, 좋아하는 학생수가 몇명 인접해있는지 탐색
                max = Math.max(max,likeCount[i][j]);
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(max==likeCount[i][j]&&map[i][j]==0){// 인접한 좋아하는 학생수가 최대이면서, 그자리에 앉을 수 있는지
                    list.add(new int[]{i,j});
                }
            }
        }

        int len = list.size();
        max = Integer.MIN_VALUE;
        int[] emptyCount = new int[len];
        for (int i = 0; i < len; i++) {
            emptyCount[i] = emptySearch(i,list); // 1번조건 만족하는 자리중에서 인접한 빈칸 수가 몇개인지
            max = Math.max(max,emptyCount[i]);
        }
        for (int i = 0; i < len; i++) {
            if(max==emptyCount[i]){ //인접한 빈칸수가 최대인 경우 해당 자리에 학생이 앉는다.
                int row = list.get(i)[0];
                int col = list.get(i)[1];
                map[row][col] = studentLike[seq][0];
                return;
            }
        }
    }
    public static int emptySearch(int index,List<int[]> list){// 인접한 빈칸 찾는 함수
        int row = list.get(index)[0];
        int col = list.get(index)[1];
        int count=0;
        for (int i = 0; i < 4; i++) {
            int nrow = row+dr[i];
            int ncol = col+dc[i];
            if(nrow<0||ncol<0||nrow>=N||ncol>=N)
                continue;
            if(map[nrow][ncol]==0){
                count++;
            }
        }
        return count;
    }
    public static int LikeSearch(int seq,int row, int col){ // 좋아하는 학생이 몇명 인접해있는지 찾는 함수

        int count=0;
        for (int i = 0; i < 4; i++) {
            int nrow = row+dr[i];
            int ncol = col+dc[i];
            if(nrow<0||ncol<0||nrow>=N||ncol>=N)
                continue;
            for (int j = 1; j < 5; j++) {
                if(map[nrow][ncol]==studentLike[seq][j]){
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

문제 조건

1. 좋아하는 학생이 가장 많이 인접해있는 자리
2. 비어있는 칸이 가장 많이 인접해있는 자리
3. 그중에 제일 작은 행, 열

풀이 방법

이 문제는 크게 보면 조건에 따라 학생들의 자리를 배치하고, 자리별로 탐색하며 만족도를 구하는 문제이다.

1. 2차원 배열 studentLike에 인덱스 0에는 학생의 번호를, 1~4에는 좋아하는 학생의 번호를 담는다.
2. 학생의 자리인 2차원 배열 map을 생성한다.
3. 첫번째 순서의 학생부터 어디 앉을지 탐색한다. 맵 전체를 완전탐색하며 해당 칸에 앉았을때, 좋아하는 학생이 몇명 인접해 있는지 구한다.
4. 2차원 배열 likecount에, map에 각 자리에 앉았을때 자리별로 좋아하는 학생이 몇명 인접해 있는지 넣는다.
5. likecount의 최댓값을 구한다.
6. likecount가 최댓값이면서 map이 0으로 빈자리 일때(1번조건) 해당 좌표를 list에 담는다
7. list에 담긴 좌표를 하나씩 탐색하며(1번조건 해당하는 자리만), 인접한 비어있는 칸을 확인하고, emptycount에 인접한 빈칸의 갯수를 담는다.
8. emptycount의 최댓값을 구한다.
9. emptycount를 인덱스 0부터 탐색하며, 처음으로 emptycount가 최댓값과 동일한 값일때(2번조건,3번조건) 해당 좌표에 학생을 앉힌다.

📢 3번 조건은 2번조건에 해당하는 값을 모아서 다시 탐색할 필요없이, 낮은 행,열 부터 탐색하므로,
2번조건을 처음으로 만족하는 좌표가 곧 3번 조건도 만족한다.

10. map을 처음부터 탐색하며, 인접한 학생 중 좋아하는 학생의 수의 따라
    만족도를 환산해서 최종 answer값에 더해준다.

후기

처음 자리탐색시 if(map[i][j]!=0) continue; 처리를 해주어서 이후에는 따로 빈자리인지 확인을 안해줬다.
하지만 likecount와 최댓값을 비교하면서 처음부터 다시 탐색하므로, if(map[i][j]!=0) continue; 처리를 한번 더 해줘야 한다.
문제의 테스트 케이스로는 모두 통과가 됐어서 더욱 찾기 힘든 실수였다.
학생마다 print문을 찍어보며 map을 확인해가며 겨우 찾아냈다.

함수로 분리하지 않았다면 몇중for문이 됐는지도 모를정도로 조건도 많고, 탐색도 많았다.

코드를 보면 좋아하는 학생탐색, 빈자리탐색, 만족도 탐색시 중복되는 코드가 있다.
아마 인접부분을 탐색하는 함수로 따로 빼서 설계했다면 더 코드가 깔끔했을것 같다.