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

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

21608번: 상어 초등학교

풀이

이번 문제는 설명에 너무 자세하게 적혀있어서 풀이할 게 없다.

문제에서 시키는대로 하면 된다.

 

우선 ArrayList 배열로 선언된 Student 에 학생의 번호와 좋아하는 학생의 번호를 넣어준다.

문제 1, 2, 3번의 조건을 쉽게 해결하려면 우선 순위 큐를 사용하면 된다.

public static class Position implements Comparable<Position>{
    int x;
    int y;
    int nearCount;
    int likeCount;
		
    public Position (int x, int y, int nearCount, int likeCount) {
        this.x = x;
        this.y = y;
        this.nearCount = nearCount;
        this.likeCount = likeCount;
    }
		
    public int compareTo (Position o) {
        if (this.likeCount == o.likeCount) {
            if (this.nearCount == o.nearCount) {
                if (this.x == o.x) {
                    return this.y - o.y;
                } else {
                    return this.x - o.x;
                }
            } else {
                return o.nearCount - this.nearCount;
            }
        } else {
            return o.likeCount - this.likeCount;
        }
    }
}

비어있는 칸과 인접한 칸에 좋아하는 학생의 여부는 완전 탐색으로 검색하면 된다. 모든 자리가 정해졌으면 완전 탐색을 또 진행하면서 학생의 만족도를 찾으면 된다. 완전 탐색을 여러 번 진행하기 때문에 시간 초과가 발생할 수도 있다고 생각하지만 N의 범위가 작아서 괜찮다.

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, ans = 0;
    static int[][] map;
    static int[] order;
    static ArrayList<Integer>[] Student;
	
    public static class Position implements Comparable<Position>{
        int x;
        int y;
        int nearCount;
        int likeCount;
		
        public Position (int x, int y, int nearCount, int likeCount) {
            this.x = x;
            this.y = y;
            this.nearCount = nearCount;
            this.likeCount = likeCount;
        }
		
        public int compareTo (Position o) {
            if (this.likeCount == o.likeCount) {
                if (this.nearCount == o.nearCount) {
                    if (this.x == o.x) {
                        return this.y - o.y;
                    } else {
                        return this.x - o.x;
                    }
                } else {
                    return o.nearCount - this.nearCount;
                }
            } else {
                return o.likeCount - this.likeCount;
            }
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
				
        N = Integer.parseInt(br.readLine()); // N*N (맵크기)
		
        map = new int[N+1][N+1];
        order = new int[N*N+1];
        Student = new ArrayList[N*N+1];
        for (int i=1; i<=N*N; i++) {
            Student[i] = new ArrayList<Integer>();
        }
		
        for (int i=1; i<=N*N; i++) {
            st = new StringTokenizer(br.readLine());
			
            int s = Integer.parseInt(st.nextToken());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int v3 = Integer.parseInt(st.nextToken());
            int v4 = Integer.parseInt(st.nextToken());
			
            order[i] = s;
            Student[s].add(v1);
            Student[s].add(v2);
            Student[s].add(v3);
            Student[s].add(v4);
        }
	
        for (int i=1; i<=N*N; i++) {
            find(order[i]);
        }
		
        ans = getLikeCount();
        System.out.println(ans);
    }
	
    public static void find(int num) {
        PriorityQueue<Position> pq = new PriorityQueue<>();
		
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int nearCount = 0;
                int likeCount = 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 >= 1 && nx <= N && ny >= 1 && ny <= N) {
                        
                        // 좋아하는 학생들이 주변에 있는지 여부
                        for (int now : Student[num]) {
                            if (now == map[nx][ny]) {
                                likeCount++;
                            }
                        }
                        
                        // 근처 자리가 비어있는지 여부
                        if (map[nx][ny] == 0) {
                            nearCount++;
                        }
                    }
                }
                
                pq.add(new Position(i, j, nearCount, likeCount));
            }
        }
 
        Position setPos = pq.poll();       
        map[setPos.x][setPos.y] = num;
    }
	
    public static int getLikeCount() {
        int num = 0;
		
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                int likeCount = 0;
				
                for (int d=0; d<4; d++) {
                    int nx = i + dx[d];
                    int ny = j + dy[d];
					
                    if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
 
                        // 좋아하는 학생들이 주변에 있는지 여부
                        for (int now : Student[map[i][j]]) {
                            if (now == map[nx][ny]) {
                                likeCount++;
                            }
                        }
                    }
                }
				
                if (likeCount == 1) num++;
                if (likeCount == 2) num += 10;
                if (likeCount == 3) num += 100;
                if (likeCount == 4) num += 1000;
            }
        }
		
        return num;
    }
}