[백준 / JAVA] 21608. 상어 초등학교 (G5)

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

21608번: 상어 초등학교

 

사방탐색으로 풀리는 간단한 문제다. 이런 문제를 풀 땐 공책 같은 곳에 내가 구현하고자 하는 것을 적으면서 풀자. 그렇지 않으면...

 

그렇지 않으면...

 

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		order = new int[N * N];
		map = new int[N][N];
		hMap = new HashMap<>();
		for (int i = 0; i < N * N; i++) {
			st = new StringTokenizer(br.readLine());
			int student = Integer.parseInt(st.nextToken());
			order[i] = student;
			HashSet<Integer> likeSet = new HashSet<>();
			for (int j = 0; j < 4; j++)
				likeSet.add(Integer.parseInt(st.nextToken()));
			hMap.put(student, likeSet);
		}
		for (int o : order)
			setStudent(o);
		System.out.println(calcScore());
	}

	static int N, map[][], dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 }, order[], scores[] = { 0, 1, 10, 100, 1000 };
	static HashMap<Integer, HashSet<Integer>> hMap;

	static int calcScore() {
		int score = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int count = 0;
				for (int d = 0; d < 4; d++) {
					int nr = i + dr[d];
					int nc = j + dc[d];
					if (nr < 0 || nr >= N || nc < 0 || nc >= N)
						continue;
					if (hMap.get(map[i][j]).contains(map[nr][nc]))
						count++;
				}
				score+=scores[count];
			}
		}
		return score;
	}

	static void setStudent(int student) {
		int maxScore = -1;
		int empty = -1;
		int row = -1;
		int col = -1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0) {
					int score = 0;
					int tmpEmpty = 0;
					for (int d = 0; d < 4; d++) {
						int nr = i + dr[d];
						int nc = j + dc[d];
						if (nr < 0 || nr >= N || nc < 0 || nc >= N)
							continue;
						if (map[nr][nc] == 0)
							tmpEmpty++;
						else if (hMap.get(student).contains(map[nr][nc]))
							score++;
					}
					if (score > maxScore) {
						maxScore = score;
						empty = tmpEmpty;
						row = i;
						col = j;
					} else if (score == maxScore) {
						if (tmpEmpty > empty) {
							empty = tmpEmpty;
							row = i;
							col = j;
						}
					}
				}
			}
		}
		map[row][col] = student;
	}
}