백준 21608 상어 초등학교 (Java)

1. 문제 링크

21608번: 상어 초등학교

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 학생에 대한 정보를 입력받으면서 자리를 찾는다. (이 자리가 정해져야 다음 자리를 정할 수 있기 때문)
2. 모든 자리를 탐색하면서 인접칸에 좋아하는 학생의 수를 체크하고, 빈칸의 수를 체크한다.
3. 1번 조건 확인 - 좋아하는 학생이 가장 많은 자리를 찾는다(list에 자리 추가)
4. 2번 조건 확인 - 1번 조건이 1인 경우 자리 배치, 1보다 큰 경우 다음 조건을 확인한다.
   4-1. 빈 칸이 가장 많은 자리를 찾는다. (list2에 자리 추가)
   4-2. 3번 조건은 탐색 순서 때문에 자연스럽게 순서대로 들어가서 list2의 0번째 인덱스로 정한다.
5. 모든 학생에 대한 자리 배치가 끝나면 사방 탐색으로 인접한 좋아하는 학생 수를 구해 만족도를 구한다.

 

4. 코드

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

public class Main {
	static StringBuilder sb;
	static int N, map[][], many[][], empty[][], result; 
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	static int[] score = {0, 1, 10, 100, 1000};
	static ArrayList<Integer> favorite[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		map = new int[N][N]; //기존 교실 배치도
		
		favorite = new ArrayList[N*N+1]; //자리 배치 끝나고 만족도 조사해서 나중에도 필요..
		for(int s=0;s<N*N+1;s++) {
			favorite[s] = new ArrayList<>();
		}
		
		//입력 받으면서 자리 찾기
		String[] split;
		int student = 0;
		for(int s=0;s<N*N;s++) {
			split = br.readLine().split(" ");
			student = Integer.parseInt(split[0]);
			for(int i=0;i<4;i++) {
				favorite[student].add(Integer.parseInt(split[i+1]));
			}
			where(student); //번호와 친구 목록 넘기기
		}
		//모든 학생의 자리 배치 끝
		
		
		satis();
		
		sb.append(result);
				
		System.out.println(sb);
	}
	private static void where(int student) {
		many = new int[N][N]; //인접 칸 수 세는 용도
		empty = new int[N][N]; //빈 칸 수 세는 용도
		for(int i=0; i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j] == 0) { //아직 아무도 안 앉은 자리
					for(int d=0;d<4;d++) { //인접한 구역 => 사방 탐색
						int X = i +dx[d];
						int Y = j +dy[d];
						if(X>=0 && X<N && Y>=0 && Y<N) { //일단 범위 안에서
							if(favorite[student].contains(map[X][Y])) { //좋아하는 학생이 있으면
								
								many[i][j]++;
							}
							else if(map[X][Y] == 0) { //빈칸인 경우
								empty[i][j]++; 
							}
						}
					}
				}
			}	
		} //모든 자리를 돌면서 사방탐색

		int max = 0;
		ArrayList<int[]> list = new ArrayList<>();
		for(int i=0; i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j] == 0) {
					if(max < many[i][j]) {
						max = many[i][j];
						list.clear(); //새로운 최댓값이 나왔으니까 전부 지우고 넣기
						list.add(new int[] {i, j});
					}
					else if(max == many[i][j]) {
						list.add(new int[] {i, j});
					}
				}
			}		
		} //모든 자리를 돌면서 1번 조건을 만족하는 칸 찾기
		
		ArrayList<int[]> list2 = new ArrayList<>();
		if(list.size()==1) { //1번 조건 만족하는 자리가 하나인 경우
			map[list.get(0)[0]][list.get(0)[1]] = student;
		}
		else {
			max = 0; //초기화
			for(int i=0;i<list.size();i++) { //list에 들어있는 개수만큼
				int[] now = list.get(i);
				
				if(max < empty[now[0]][now[1]]) { //빈 칸 수가 제일 많은 위치 찾기
					max = empty[now[0]][now[1]];
					list2.clear(); //새로운 최댓값이 나왔으니까 전부 지우고 넣기
					list2.add(new int[] {now[0], now[1]});
				}
				else if (max == empty[now[0]][now[1]]){
					list2.add(new int[] {now[0], now[1]});
				}
			}
			map[list2.get(0)[0]][list2.get(0)[1]] = student;
		}
		//2번 조건 확인 끝, 3번 조건은 탐색 순서때문에 list2에 자연스럽게 순서대로 들어감
	}
	
	private static void satis() {
		int count;
		for(int i=0; i<N;i++) {
			for(int j=0;j<N;j++) {
				count = 0;
				for(int d=0;d<4;d++) { //인접한 구역 => 사방 탐색
					int X = i +dx[d];
					int Y = j +dy[d];
					if(X>=0 && X<N && Y>=0 && Y<N) {
						if(favorite[map[i][j]].contains(map[X][Y])) { 
							count++;
						}
					}
				}
				result += score[count];
			}
		}
	}
}