[백준] 21608 - 상어 초등학교 (JAVA)

개츠비·2023년 5월 5일

목록 보기

74/84

소요시간 : 30분
문제 사이트 : 백준
문제 수준 : 골드 5
문제 유형 : 구현
다른 사람의 풀이를 참고 했는가 ? : X
문제 링크 : https://www.acmicpc.net/problem/21608
푼 날짜 : 2023.05.05

1. 사용한 자료구조 & 알고리즘

구현. 해시맵, 정렬

2. 사고과정

1. 좋아하는 친구를 어떻게 저장할 것인가?
-> 좋아하는 친구는 4명이므로, 해시맵을 통해서 해당 학생의 좋아하는 친구를 저장했다. 단순히 자리를 배치할 때만이면 해시맵을 쓰지 않아도 되지만, 나중에 만족도 조사를 할때, 해당 학생의 친구를 다시 알아야 하므로 해시맵을 쓰면 편할 것이라고 생각했다.

2. 해당 좌표의 우선순위를 어떻게 알아낼 수 있나?
학생이 추가될 떄마다 정렬을 하면 된다. 학생이 추가될 때마다 정렬하므로 , 학생은 N N 명, 정렬은 NN log N *N으로 최대 N^3 log N 이 걸릴 것으로 생각했다. N이 20이므로 충분히 가능하다. 정렬한 후 해당 좌표가 빈 공간이라면 학생을 배치한다.

그 외에는 문제가 쉬워서 별달리 설명할 게 많이 없다.

3. 풀이과정

해시맵에 좋아하는 친구 저장.
입력받은 학생의 자리를 구한다. 우선순위 (좋아하는 친구 많은 순, 빈 공간 많은 순, 행 작은 순, 열 작은 순 ) 에 따라 정렬하고, 정렬된 좌표들을 보며 해당 map이 빈 공간이라면 그 공간에 학생을 배치한다.
만족도 조사를 하는데, (상,하,좌,우)를 보면서 좋아하는 친구가 몇명인지 세어준다.

4. 소스코드

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


public class Main{
	static int map[][];
	
	static HashMap<Integer,Integer[]> hashMap=new HashMap<>();
	static int dy[] = {-1,1,0,0};
	static int dx[] = {0,0,-1,1};
	public static void main(String[] args) throws IOException{

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n=Integer.parseInt(br.readLine());
		map=new int[n][n];
		
		for(int i=0;i<n*n;i++) {
			st=new StringTokenizer(br.readLine());
			int s1 = Integer.parseInt(st.nextToken());
			int s2 = Integer.parseInt(st.nextToken());
			int s3 = Integer.parseInt(st.nextToken());
			int s4 = Integer.parseInt(st.nextToken());
			int s5 = Integer.parseInt(st.nextToken());
			//해시맵에 좋아하는 친구 저장.
			hashMap.put(s1,new Integer[] {s2,s3,s4,s5});
			//현재 학생의 자리를 구함
			putStudent(s1);
		}
		//만족도 조사.
		int sum = 0;
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				
				int count = 0;
				Integer friends[] = hashMap.get(map[i][j]);
				for(int k=0;k<4;k++) {
					int nextY=i+dy[k];
					int nextX=j+dx[k];
					if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
						continue;
					int now = map[nextY][nextX];
					
					//상,하,좌,우가 친구면 count 증가
					for(int p=0;p<4;p++)
						if(now == friends[p]) count++;
					
				}
				//count 개수에 따라 sum 증가
				switch(count) {
				case 1: sum += 1; break;
				case 2: sum += 10; break;
				case 3: sum += 100; break;
				case 4: sum += 1000; break;
				}
				
				
			}
		}
		
		System.out.println(sum);
		
		

	}
	public static void putStudent(int student) {
		
		Integer friends[] = hashMap.get(student);
		int f1 = friends[0];
		int f2 = friends[1];
		int f3 = friends[2];
		int f4 = friends[3];
		
		
		ArrayList<Integer[]> list=new ArrayList<>();
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				int friendsCount = 0;
				int emptyCount = 0;
				for(int k=0;k<4;k++) {
					int nextY=i+dy[k];
					int nextX=j+dx[k];
					if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
						continue;
					//해당 좌표가 좋아하는 학생이면 친구 count 증가
					//해당 좌표가 빈 공간이면 빈 공간 count 증가
					int now = map[nextY][nextX];
					if(now==f1||now==f2||now==f3||now==f4)
						friendsCount++;
					if(now==0)
						emptyCount++;
					
				}
				list.add(new Integer[] {friendsCount,emptyCount,i,j});
				
			}
		}
		//정렬함. 정렬 기준 -> 선호 학생의 수, 빈 자리의 수, 행, 열
		Collections.sort(list,new Comparator<>() {
			@Override
			public int compare(Integer n1[],Integer n2[]) {
				if(n1[0]<n2[0]) return 1;
				else if(n1[0]==n2[0]) {
					if(n1[1]<n2[1]) return 1;
					else if(n1[1]==n2[1]) {
						if(n1[2]>n2[2]) return 1;
						else if(n1[2]==n2[2]) {
							if(n1[3]>n2[3]) return 1;
						}
						
					}
				}
				return -1;
			}
		});
		
		//0번째 인덱스부터 시작해서 해당 좌표가 0이 아니라면, 그 좌표가 현재 학생의 자리가 됨.
		for(int i=0;i<list.size();i++) {
			int y = list.get(i)[2];
			int x = list.get(i)[3];
			if(map[y][x]==0) {
				map[y][x] = student;
				return;
			}
			
		}
		
		
		
	}

}