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

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

21608번: 상어 초등학교

풀이

먼저 각 학생마다 좋아하는 학생의 번호를 저장해야 하므로 Map 자료구조를 사용하여 key 값은 학생 번호, value는 ArrayList로 학생이 좋아하는 학생의 번호들을 저장했다.

이 때 단순 HashMap이 아닌 LinkedHashMap을 사용한 이유는, 정해진 순서대로 학생들의 자리를 배치해야 하므로 순서를 유지해야 하기 때문이다. HashMap은 값이 들어가는 순서를 보장하지 않는다.

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int n = Integer.parseInt(br.readLine());
    	
    	LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents = readFavoriteStudents(br, n);
    	
    	int[][] seats = locateStudents(n, favoriteStudents);
    	
    	System.out.println(countScore(favoriteStudents, seats));
    }

 

LinkedHashMap<Integer, ArrayList<Integer>> readFavoriteStudents(BufferedReader br, int n)

LinkedHashMap을 선언하여 각 학생마다 좋아하는 학생의 번호를 저장한다.

    private static LinkedHashMap<Integer, ArrayList<Integer>> readFavoriteStudents(BufferedReader br, int n) throws IOException {
    	LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents = new LinkedHashMap<Integer, ArrayList<Integer>>();
    	
    	StringTokenizer st;
    	for (int i = 0; i < n * n; i++) {
    		st = new StringTokenizer(br.readLine());
    		int num = Integer.parseInt(st.nextToken());
    		
    		ArrayList<Integer> students = new ArrayList<>();
    		for (int j = 0; j < 4; j++) {
    			students.add(Integer.parseInt(st.nextToken()));
    		}
    		favoriteStudents.put(num, students);
    	}
    	
    	return favoriteStudents;
    }

 

int[][] locateStudents(int n, LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents)

순서대로 각 학생의 자리를 정한다.

    private static int[][] locateStudents(int n, LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents) {
    	
    	int[][] seats = new int[n][n];  // 각 위치에 앉는 학생의 자리를 저장하는 배열
    	
    	// 순서대로 각 학생의 자리를 정한다. 
    	for (int num : favoriteStudents.keySet()) {
    		ArrayList<Integer> students = favoriteStudents.get(num);
    		
                // -1로 초기화
    		int maxFavoriteStudents = -1;
    		int maxEmptySeats = -1;
    		
    		// 현재 학생이 앉을 자리 위치
    		int r = 0;
    		int c = 0;
    		
    		// 모든 자리를 순차적으로 탐색한다.
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < n; j++) {
    				// 이미 자리가 있으면 스킵
    				if (seats[i][j] != 0) continue;
    				
    				// 인접한 칸에 있는 좋아하는 학생의 수
    				int cnt = countFavoriteStudents(students, seats, i, j, n);
    				
    				if (cnt > maxFavoriteStudents) {
    					maxFavoriteStudents = cnt;
    					maxEmptySeats = countEmptySeats(seats, i, j, n);
    					r = i; c = j;
    				}
    				else if (cnt == maxFavoriteStudents) {
    					// 인접한 칸에 있는 비어있는 칸의 수
    					cnt = countEmptySeats(seats, i, j, n);
    					
    					if (cnt > maxEmptySeats) {
    						maxEmptySeats = cnt;
    						r = i; c = j;
    					}
    				}
    			}
    		}
    		
    		seats[r][c] = num;
    	}
    	
    	return seats;
    }

이 때, maxFavoriteStudents와 maxEmptySeats를 -1로 초기화하는 것이 중요하다.

maxFavoriteStudents와 maxEmptySeats는 각각 현재 정해진, 학생이 앉을 위치의 인접한 칸에 있는 좋아하는 학생의 수, 인접한 칸에 있는 비어있는 칸의 수다. 매 위치를 탐색할 때마다 이 값들을 비교하여 학생이 앉을 위치를 정해야 한다.

 

이 값들을 -1로 초기화하지 않고 0으로 초기화한다면, 마지막 학생의 경우 무조건 남은 자리에 앉아야 하는데, maxFavoriteStudents와 maxEmptySeats 모두 0이고 남은 자리의 인접한 칸에 있는 좋아하는 학생의 수, 인접한 칸에 있는 비어있는 칸의 수가 모두 0이라면 r과 c가 0이므로 첫번째 자리에 앉는다. 그렇다면 남은 빈 자리의 seats값은 0이 되고 그렇다면 이후 최종적으로 만족도를 조사할 때 favoriteStudents.get(seats[i][j]) -> favoriteStudents.get(0)이 호출되므로 NullPointerException이 발생한다.

 

 

int countFavoriteStudents(ArrayList<Integer> students, int[][] seats, int r, int c, int n)

seats[r][c]에 인접한 칸에 있는 좋아하는 학생의 수를 구한다.

  private static int dx[] = {-1, 0, 1, 0};
  private static int dy[] = {0, 1, 0, -1};
    
  private static int countFavoriteStudents(ArrayList<Integer> students, int[][] seats, int r, int c, int n) {
    	int cnt = 0;
    	
    	// 4방향에 있는 칸을 탐색
    	for (int i = 0; i < 4; i++) {
    		int nr = r + dx[i];
    		int nc = c + dy[i];
    		
    		if (!checkIndex(nr, nc, n)) continue;
    		
    		// 인접한 칸에 좋아하는 학생이 있으면 cnt++
    		int student = seats[nr][nc];
    		if (students.contains(student)) {
    			cnt++;
    		}
    	}
    	
    	return cnt;
    }

int countEmptySeats(int[][] position, int r, int c, int n)

seats[r][c]에 인접한 칸 중 비어있는 칸의 수를 구한다.

    private static int countEmptySeats(int[][] seats, int r, int c, int n) {
    	int cnt = 0;
    	
    	// 4방향에 있는 칸을 탐색
    	for (int i = 0; i < 4; i++) {
    		int nr = r + dx[i];
    		int nc = c + dy[i];
    		
    		if (!checkIndex(nr, nc, n)) continue;
    		
    		// 인접한 칸이 비어있는 칸이면 cnt++
    		if (seats[nr][nc] == 0) {
    			cnt++;
    		}
    	}
    	
    	return cnt;
    }

boolean checkIndex(int x, int y, int n)

x, y가 배열의 인덱스를 벗어나는지 체크한다.

    private static boolean checkIndex(int x, int y, int n) {
    	return x >= 0 && x < n && y >= 0 && y < n;
    }

 

 

int countScore(LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents, int[][] seats)

학생의 총 만족도의 합을 구한다.

    private static int countScore(LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents, int[][] seats) {
    	int n = seats.length;
    	int score = 0;	// 총 만족도
    	
    	// 모든 위치에 대해 탐색
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			int num = seats[i][j];
    			ArrayList<Integer> students = favoriteStudents.get(num);
    			
    			// 인접한 칸에 있는 좋아하는 학생의 수
    			int cnt = countFavoriteStudents(students, seats, i, j, n);
    			
    			score += Math.pow(10, cnt-1);
    		}
    	}
    	
    	return score;
    }

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	
	private static int dx[] = {-1, 0, 1, 0};
	private static int dy[] = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int n = Integer.parseInt(br.readLine());
    	
    	LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents = readFavoriteStudents(br, n);
    	
    	int[][] seats = locateStudents(n, favoriteStudents);
    	
    	System.out.println(countScore(favoriteStudents, seats));
    }
    
    private static LinkedHashMap<Integer, ArrayList<Integer>> readFavoriteStudents(BufferedReader br, int n) throws IOException {
    	LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents = new LinkedHashMap<Integer, ArrayList<Integer>>();
    	
    	StringTokenizer st;
    	for (int i = 0; i < n * n; i++) {
    		st = new StringTokenizer(br.readLine());
    		int num = Integer.parseInt(st.nextToken());
    		
    		ArrayList<Integer> students = new ArrayList<>();
    		for (int j = 0; j < 4; j++) {
    			students.add(Integer.parseInt(st.nextToken()));
    		}
    		favoriteStudents.put(num, students);
    	}
    	
    	return favoriteStudents;
    }
    
    private static int[][] locateStudents(int n, LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents) {
    	
    	int[][] seats = new int[n][n]; // 각 위치에 앉는 학생의 자리를 저장하는 배열
    	
    	// 순서대로 각 학생의 자리를 정한다. 
    	for (int num : favoriteStudents.keySet()) {
    		ArrayList<Integer> students = favoriteStudents.get(num);
    		
    		int maxFavoriteStudents = -1;
    		int maxEmptySeats = -1;
    		
    		// 현재 학생이 앉을 자리 위치
    		int r = 0;
    		int c = 0;
    		
    		// 모든 자리를 순차적으로 탐색한다.
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < n; j++) {
    				// 이미 자리가 있으면 스킵
    				if (seats[i][j] != 0) continue;
    				
    				// 인접한 칸에 있는 좋아하는 학생의 수
    				int cnt = countFavoriteStudents(students, seats, i, j, n);
    				
    				if (cnt > maxFavoriteStudents) {
    					maxFavoriteStudents = cnt;
    					maxEmptySeats = countEmptySeats(seats, i, j, n);
    					r = i; c = j;
    				}
    				else if (cnt == maxFavoriteStudents) {
    					// 인접한 칸에 있는 비어있는 칸의 수
    					cnt = countEmptySeats(seats, i, j, n);
    					
    					if (cnt > maxEmptySeats) {
    						maxEmptySeats = cnt;
    						r = i; c = j;
    					}
    				}
    			}
    		}
    		
    		seats[r][c] = num;
    	}
    	
    	return seats;
    }
    
    private static int countFavoriteStudents(ArrayList<Integer> students, int[][] seats, int r, int c, int n) {
    	int cnt = 0;
    	
    	// 4방향에 있는 칸을 탐색
    	for (int i = 0; i < 4; i++) {
    		int nr = r + dx[i];
    		int nc = c + dy[i];
    		
    		if (!checkIndex(nr, nc, n)) continue;
    		
    		// 인접한 칸에 좋아하는 학생이 있으면 cnt++
    		int student = seats[nr][nc];
    		if (students.contains(student)) {
    			cnt++;
    		}
    	}
    	
    	return cnt;
    }
    
    private static int countEmptySeats(int[][] seats, int r, int c, int n) {
    	int cnt = 0;
    	
    	// 4방향에 있는 칸을 탐색
    	for (int i = 0; i < 4; i++) {
    		int nr = r + dx[i];
    		int nc = c + dy[i];
    		
    		if (!checkIndex(nr, nc, n)) continue;
    		
    		// 인접한 칸이 비어있는 칸이면 cnt++
    		if (seats[nr][nc] == 0) {
    			cnt++;
    		}
    	}
    	
    	return cnt;
    }
    
    private static boolean checkIndex(int x, int y, int n) {
    	return x >= 0 && x < n && y >= 0 && y < n;
    }
    
    private static int countScore(LinkedHashMap<Integer, ArrayList<Integer>> favoriteStudents, int[][] seats) {
    	int n = seats.length;
    	int score = 0;	// 총 만족도
    	
    	// 모든 위치에 대해 탐색
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			int num = seats[i][j];
    			ArrayList<Integer> students = favoriteStudents.get(num);
    			
    			// 인접한 칸에 있는 좋아하는 학생의 수
    			int cnt = countFavoriteStudents(students, seats, i, j, n);
    			
    			score += Math.pow(10, cnt-1);
    		}
    	}
    	
    	return score;
    }
   
}

 

LinkedHashMap<Integer, ArrayList>는 다음과 같은 경고가 뜬다.
"ArrayList is a raw type. References to generic type ArrayList<E> should be parameterized"
ArrayList 에 사용할 객체 타입이 정해지지 않았다는 의미인데, 사용할 객체 타입을 정하지 않았기 때문에 여러 종류의 객체를 담을 수 있게 되고, 여러 종류의 객체를 담았기 때문에 데이터를 가져올 때 타입을 일일이 확인해야 한다.
따라서 ArrayList에 사용할 객체 타입을 다음과 같이 명시해야 한다.
-> LinkedHashMap<Integer, ArrayList<Integer>>