[JAVA] 백준 상어초등학교

구현문제이다. 생각보다 구현에있어서 많은 시간이 든 문제이다.

실버 1문제인데 체감은 골드5정도 되는 느낌이다.

 

구현 방식대로 one,two,three는

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

위 사항을 그대로 구현한 것이다.

 

단, 구현하면서 인접한 칸에 좋아하는사람이 있는지 확인할때는 contains메소드를 통해서 Set(좋아하는 사람 모음)에 해당 num(좋아하는사람)이 있는지 존재여부만 확인한다.

 

contains를 생각해내서 활용한 부분은 매우 좋았던 것 같다.

 

 

클래스는 두가지가 있다.

- Student : num(해당학생의 번호), loveSet(좋아하는사람들 명단)

- CandidateLoc : 저장할 좌표값(r,c)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int n;
    static Student[][] grid;
    static Student[] numlove;
    static int[] dr= {0,1,0,-1};
    static int[] dc= {1,0,-1,0};
    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());
        numlove= new Student[n*n];//번호(0)-좋아하는사람(1~4)
        grid = new Student[n+2][n+2];//1~n이용
        for(int ni = 0; ni<n*n; ni++){
            st = new StringTokenizer(br.readLine());
            int[] arr = new int[5];
            for(int k=0; k<5; k++) arr[k] = Integer.parseInt(st.nextToken());
            numlove[ni] = new Student(arr[0],arr[1], arr[2],arr[3], arr[4]);
        }

        for(int i=0; i<n*n; i++){
            one(i, numlove[i].num);
        }

        int answer=0;
        for(int r=1; r<=n; r++){
            for(int c=1; c<=n; c++){
                Student s = grid[r][c];
                int count=0;
                for(int d=0; d<4; d++) {
                    int searchR = r + dr[d];
                    int searchC = c + dc[d];
                    if(searchR>=1&&searchC>=1&&searchR<=n&&searchC<=n) {
                        if(s.loveSet.contains(grid[searchR][searchC].num)) count++;
                    }
                }

                if(count==1) answer+=1;
                else if(count==2) answer+=10;
                else if(count==3) answer+=100;
                else if(count==4) answer+=1000;
            }
        }
        System.out.println(answer);
    }
    static void one(int i, int num){
        int max=1;//전부 빈경우를 위해 1부터 시작.
        ArrayList<CandidateLoc> list = new ArrayList<>();
        for(int r=1; r<=n; r++){
            for(int c=1; c<=n; c++){//각각의 위치에서 인접한 좋아하는학생수 카운트
                if(grid[r][c]!=null) continue;
                int count=0;
                for(int d=0; d<4; d++){
                    int searchR = r+dr[d];
                    int searchC = c+dc[d];
                    if(grid[searchR][searchC]!=null){//비어있지않으면 현재위치가 좋아하는사람에 포함되어있는지
                        Student s = grid[searchR][searchC];
                        if(numlove[i].loveSet.contains(s.num)) {
                            count++;
                        }
                    }
                }

                //카운트한값 무조건 ArrayList에넣기, 최대값 새로갱신이면 지우고 넣기
                if(count>max){
                    max=count;
                    list.clear();
                    list.add(new CandidateLoc(r,c));
                }else if(count==max){
                    list.add(new CandidateLoc(r,c));
                }else{
                    //최대값보다 작으면 아무것도 x
                }
            }
        }
        //1. 맨처음처럼 빈경우
        if(list.size()==0){
            two(i,list);
        }
        else if(list.size()==1){
            CandidateLoc cl = list.get(0);
            grid[cl.r][cl.c] = numlove[i];
            return;
        }
        else{//확장된 two
            two(i,list);
        }
    }
    static void two(int i, ArrayList<CandidateLoc> list){
        if(list.size()==0){//0인경우 빈칸인부분은 모두 집어넣어서 아래 진행
            for(int r=1; r<=n; r++)
                for(int c=1; c<=n; c++) {
                    if (grid[r][c] == null) list.add(new CandidateLoc(r, c));
                }
        }

        ArrayList<CandidateLoc> manyEmptyNearBy = new ArrayList<>();
        int max=0;
        for(int s=0; s<list.size(); s++){
            CandidateLoc cl = list.get(s);
            int count=0;
            for(int d=0; d<4; d++) {
                int searchR = cl.r + dr[d];
                int searchC = cl.c + dc[d];
                if(searchR>=1&&searchC>=1&&searchR<=n&&searchC<=n&&grid[searchR][searchC]==null) {
                    count++;
                }
            }
            if(count>max){
                max=count;
                manyEmptyNearBy.clear();
                manyEmptyNearBy.add(cl);
            }else if(count == max) {
                manyEmptyNearBy.add(cl);
            }
        }

        if(manyEmptyNearBy.size()==1){
            CandidateLoc cl = manyEmptyNearBy.get(0);
            grid[cl.r][cl.c] = numlove[i];

            return;
        }
        else{//확장된 three
            three(i, manyEmptyNearBy);
        }

    }

    static void three(int i, ArrayList<CandidateLoc> list){
        int minR=100;
        int minC=100;
        for(int s=0; s<list.size(); s++){
            CandidateLoc cl = list.get(s);
            if(cl.r<minR){
                minR=cl.r;
                minC=cl.c;
            }else if(cl.r == minR){
                if(cl.c<minC){
                    minC=cl.c;
                }
            }
        }
        grid[minR][minC]= numlove[i];
        //System.out.println(minR+"three"+minC+ "=" + grid[minR][minC].num);

    }
    static class CandidateLoc{
        int r,c;
        CandidateLoc(int r, int c){
            this.r =r;
            this.c =c;
        }
    }
    static class Student{
        int num;
        Set<Integer> loveSet = new HashSet<>();

        Student(int a, int b, int c, int d, int e){
            num=a;
            loveSet.add(b);
            loveSet.add(c);
            loveSet.add(d);
            loveSet.add(e);
        }


    }
}