백준 21608 - 상어 초등학교

[문제 바로가기]

 

1. 유형

구현

2. 문제 분석

21년 상반기 문제입니다. SDI를 지원했을 때 오전 타임 1번으로 나온 문제라서 반갑네요.

유형은 우선순위 큐를 사용해야 하고, 기준을 잘 설정해야 해요.

 

주변에 친구가 많은 칸을 선택, 주변에 빈칸이 많은곳선택 -> 행번호오름차순->열번호 오름차순

저 같은 경우엔 람다식+배열을 많이 써요. 코테 칠 때 클래스를 만들고 Comparable을 구현한 후 컬렉션에 넣으면 시간이 많이 소요됩니다.

나머지 조건 쉽습니다.

4방향을 탐색해주면서 주변에 친구가 있으면 카운트를 증가시켜요. 친구 여부는 Set으로 판단해줬습니다.

4방향 탐색하면서 빈칸이 있으면 빈칸 수 를 증가시켜주고 우선순위 큐에 삽입하면 됩니다.

 

설계

총 N^2을 탐색 -> 빈칸중에서 -> 친구수, 빈칸수, 행, 열 기준 우선순위큐 탐색 -> peek를 뽑아서 배열에 할당 

-> 마지막에 점수 계산

 

3. 코드

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

public class Main{
	static int grid[][];
	static int N;
	static int D[][] = {{-1,0},{0,1},{1,0},{0,-1}};
	static Set<Integer> set[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		int K = (N*N)+1;
		set = new HashSet[K];
		int arr[] = new int[K];
		grid = new int[N][N];
		for(int i=0; i<K; i++)
			set[i] = new HashSet<>();
		for(int i=0; i<N*N; i++) {
			st = new StringTokenizer(br.readLine());
			int a= stoi(st.nextToken());
			arr[i+1] = a;
			for(int j=0; j<4; j++) {
				int freind =  stoi(st.nextToken());
				set[a].add(freind);
			}
		}
		int idx=1;
		while(idx<K) {
			Queue<int[]> pq = new PriorityQueue<>((int a[], int b[])->{
				if(b[0] == a[0]) {
					if(b[1]==a[1]) {
						if(a[2]==b[2])
							return a[3]-b[3];
						return a[2]-b[2];
					}
					return b[1] - a[1];
				}
				return b[0] - a[0];
			});
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(grid[i][j]==0) {
						int fn=findFreinds(i,j, arr[idx]);
						int bn = findBrank(i,j);
						pq.add(new int[] {fn, bn, i ,j});
					}
				}
			}
			int pos[] = pq.poll();
			int nr = pos[2];
			int nc = pos[3];
			grid[nr][nc] = arr[idx];
			idx++;
		}
		System.out.println(calc());
	}
	static int calc() {
		int sum=0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				int cnt=0;
				for(int k=0; k<4; k++) {
					int nr= i+D[k][0];
					int nc= j+D[k][1];
					if(nr<0|| nr>=N || nc<0 || nc>=N) continue;
					if(set[grid[i][j]].contains(grid[nr][nc])) {
						cnt++;
					}
				}
				if(cnt==0) sum+=0;
				else if(cnt==1) sum+=1;
				else if(cnt==2) sum+=10;
				else if(cnt==3) sum+=100;
				else if(cnt==4) sum+=1000;
			}
		}
		return sum;
	}
	static int findFreinds(int r, int c, int me) {
		int res=0;
		for(int k=0; k<4; k++) {
			int nr= r+D[k][0];
			int nc= c+D[k][1];
			if(nr<0|| nr>=N || nc<0 || nc>=N || grid[nr][nc]==0) continue;
			if(set[me].contains(grid[nr][nc])) {
				res++;
				
			}
		}
		return res;
	}
	static int findBrank(int r, int c) {
		int res = 0;
		for(int k=0; k<4; k++) {
			int nr= r+D[k][0];
			int nc= c+D[k][1];
			if(nr<0|| nr>=N || nc<0 || nc>=N || grid[nr][nc]>0) continue;
			res++;
		}
		return res;
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}