백준 21608 (상어 초등학교) <우선순위 큐 정렬 응용>

문제

21608번: 상어 초등학교

N * N의 크기의 맵에서 학생을 조건에 맞게 배치하는 문제이다.

조건은 다음과 같다.

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



왼쪽 표와 같이 학생의 번호와 그 학생이 좋아하는 학생의 번호가 주어진다.

 

 

 

 

 

 

 

 

 

예시는 문제 링크에서 살펴보자.

---

처음에 생각한 방법은 1, 2, 3조건에 따라서 그대로 구현하려 했지만, 1 -> 2-> 3 조건은 거칠 수록 거쳐야 하는 부분이 많고 만약 같은 조건을 만족하는 것이 여러개일 경우 무수히 많은 반복문을 실행해야 하기 때문에 다른방법을 찾아보았다.

방법은 우선순위큐를 사용하는 것이다. 현재 학생이 들어갈 수 있는 후보군 자리를 모두 조건에 맞게 정렬하여 큐에 넣는 것이다.

class Student implements Comparable<Student>{
    int x; //행
    int y; //열
    int cnt; //인접한 친구 수
    int zeroCnt; //인접한 빈 공간의 수

    Student(int x, int y, int cnt, int zeroCnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.zeroCnt = zeroCnt;
    }

    @Override
    public int compareTo(Student o){
        if(o.cnt == this.cnt){
            if(o.zeroCnt == this.zeroCnt){
                if(o.x == this.x){
                    return this.y - o.y; //열의 오름차순
                }
                return this.x - o.x; //행의 오름 차순
            }
            return o.zeroCnt - this.zeroCnt; //인접한 빈공간의 수에 따른 내림차순
        }
        return o.cnt - this.cnt; //인접한 친구 수에 따른 내림차순
    }
}

새롭게 Student라는 클래스를 만들어 준다. 여기서 정렬조건을 지정해줘 큐에 넣자마자 정렬할 수 있도록 하였다.

이제 그대로 구현해주면 된다.

private static int n;
private static int[]student; //학생의 번호를 저장할 배열 ex)student[0] = 4 이면 첫번째 학생은 4이다.
private static Map<Integer, Set<Integer>>info; //<현재 학생 번호, 현재 학생과 친한 친구들>
private static int[][]map;

 

n = Integer.parseInt(st.nextToken());

        student = new int[n*n];
        info = new HashMap<>();
        for(int i=0;i<n*n;i++){
            st = new StringTokenizer(br.readLine());
            student[i] = Integer.parseInt(st.nextToken());
            Set<Integer>set = new HashSet<>();
            for(int j = 0;j<4;j++){
                set.add(Integer.parseInt(st.nextToken()));
            }
            info.put(student[i], set);
        }

주어진 정보를 입력받아준다.

현재 학생번호의 친한 친구들을 set으로 받아야 바로 찾을 수 있다.

 

이제 map의 모든 칸을 돌면서 현재 칸의 동서남북으로 친한 친구가 있는지, 빈칸이 있는지 확인해 정보를 저장하고 우선순위큐에 넣을 것이다.

private static void sol(int student){
        PriorityQueue<Student>pq = new PriorityQueue<>();
        Set<Integer>set = info.get(student); //현재 student의 친한 친구들
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(map[i][j]!=0)continue;
                int cnt = 0; //인접한 친한 친구 수
                int zeroCnt = 0; //인접한 빈칸
                if(i-1 >= 0){ //북
                    if(set.contains(map[i-1][j])) cnt++;
                    if(map[i-1][j]==0)zeroCnt++;
                }
                if(j+1<=n-1){ //동
                    if(set.contains(map[i][j+1]))cnt++;
                    if(map[i][j+1]==0)zeroCnt++;
                }
                if(i+1 <=n-1){ //남
                    if(set.contains(map[i+1][j]))cnt++;
                    if(map[i+1][j]==0)zeroCnt++;
                }
                if(j-1>=0){ //서
                    if(set.contains(map[i][j-1]))cnt++;
                    if(map[i][j-1]==0)zeroCnt++;
                }
                pq.add(new Student(i, j, cnt, zeroCnt));
            }
        }

        int x = pq.peek().x;
        int y = pq.peek().y;
        map[x][y] = student;

    }

이제 마지막으로 점수만 계산해 주면 된다.

int sum = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int cnt = 0; //인접한 친한 친구 수
                Set<Integer>set = info.get(map[i][j]);
                if(i-1 >= 0){
                    if(set.contains(map[i-1][j])) cnt++;
                }
                if(j+1<=n-1){
                    if(set.contains(map[i][j+1]))cnt++;
                }
                if(i+1 <=n-1){
                    if(set.contains(map[i+1][j]))cnt++;
                }
                if(j-1>=0){
                    if(set.contains(map[i][j-1]))cnt++;
                }

                if(cnt==1)sum+=1;
                else if(cnt==2)sum+=10;
                else if(cnt ==3)sum+=100;
                else if(cnt==4)sum+=1000;
            }
        }
        System.out.println(sum);

---

전체 코드이다.

public class 연습용 {
    private static int n;
    private static int[]student;
    private static Map<Integer, Set<Integer>>info;
    private static int[][]map;
    private static int[][]zero;
    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());

        student = new int[n*n];
        info = new HashMap<>();
        for(int i=0;i<n*n;i++){
            st = new StringTokenizer(br.readLine());
            student[i] = Integer.parseInt(st.nextToken());
            Set<Integer>set = new HashSet<>();
            for(int j = 0;j<4;j++){
                set.add(Integer.parseInt(st.nextToken()));
            }
            info.put(student[i], set);
        }

        map = new int[n][n];

        map[1][1] = student[0];
        for(int i=1;i<n*n;i++){
            sol(student[i]);
        }

        int sum = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int cnt = 0;
                Set<Integer>set = info.get(map[i][j]);
                if(i-1 >= 0){
                    if(set.contains(map[i-1][j])) cnt++;
                }
                if(j+1<=n-1){
                    if(set.contains(map[i][j+1]))cnt++;
                }
                if(i+1 <=n-1){
                    if(set.contains(map[i+1][j]))cnt++;
                }
                if(j-1>=0){
                    if(set.contains(map[i][j-1]))cnt++;
                }

                if(cnt==1)sum+=1;
                else if(cnt==2)sum+=10;
                else if(cnt ==3)sum+=100;
                else if(cnt==4)sum+=1000;
            }
        }
        System.out.println(sum);

    }
    private static void sol(int student){
        PriorityQueue<Student>pq = new PriorityQueue<>();
        Set<Integer>set = info.get(student);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(map[i][j]!=0)continue;
                int cnt = 0;
                int zeroCnt = 0;
                if(i-1 >= 0){ //북
                    if(set.contains(map[i-1][j])) cnt++;
                    if(map[i-1][j]==0)zeroCnt++;
                }
                if(j+1<=n-1){ //동
                    if(set.contains(map[i][j+1]))cnt++;
                    if(map[i][j+1]==0)zeroCnt++;
                }
                if(i+1 <=n-1){ //남
                    if(set.contains(map[i+1][j]))cnt++;
                    if(map[i+1][j]==0)zeroCnt++;
                }
                if(j-1>=0){ //서
                    if(set.contains(map[i][j-1]))cnt++;
                    if(map[i][j-1]==0)zeroCnt++;
                }
                pq.add(new Student(i, j, cnt, zeroCnt));
            }
        }

        int x = pq.peek().x;
        int y = pq.peek().y;
        map[x][y] = student;


    }

}
class Student implements Comparable<Student>{
    int x; //행
    int y; //열
    int cnt; //인접한 친구 수
    int zeroCnt; //인접한 빈 공간의 수

    Student(int x, int y, int cnt, int zeroCnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.zeroCnt = zeroCnt;
    }

    @Override
    public int compareTo(Student o){
        if(o.cnt == this.cnt){
            if(o.zeroCnt == this.zeroCnt){
                if(o.x == this.x){
                    return this.y - o.y; //열의 오름차순
                }
                return this.x - o.x; //행의 오름 차순
            }
            return o.zeroCnt - this.zeroCnt; //인접한 빈공간의 수에 따른 내림차순
        }
        return o.cnt - this.cnt; //인접한 친구 수에 따른 내림차순
    }
}