백준 21608 : 상어 초등학교

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

21608번: 상어 초등학교

[ 문제풀이 ]

4월 25일 오전에 삼성 공채 SW 역량 테스트를 치르고 왔다. 약 2시간 만에 2문제를 풀었지만 혹시나 예외나 엣지케이스를 처리하지 못한 것이 있을까 걱정됐는데 마침 백준에 비슷하게 복원되어 올라왔기에 확인하려고 풀어봤다.

​시험 칠 때 체감 난이도는 상당히 쉬운 편이었는데 백준에서 매긴 난이도를 보니 역시 남들에게도 쉬운 난이도였던 것 같다.

​N이 최대 20밖에 되지 않기 때문에 학생들이 입력될 때마다 모든 map을 탐색하면서 최적의 자리에 학생을 배치해 주면 쉽게 해결할 수 있는 문제이다.

​문제 조건이 까다롭지 않기 때문에 그냥 주어진 지문대로 구현만 해주면 된다.

​다행히도 이 문제는 해당 풀이로 AC을 받았다. 다른 한 문제도 맞는지 확인해봐야겠다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static class Student {
		int[] ps;

		public Student() {
			ps = new int[4];
		}
	}

	static class Seat implements Comparable<Seat> {
		int y, x, sc, ec;

		public Seat(int y, int x, int sc, int ec) {
			this.y = y;
			this.x = x;
			this.sc = sc;
			this.ec = ec;
		}

		@Override
		public int compareTo(Seat o) {
			if (this.sc == o.sc) {
				if (this.ec == o.ec) {
					if (this.y == o.y) {
						return this.x - o.x;
					}
					return this.y - o.y;
				}
				return o.ec - this.ec;
			}
			return o.sc - this.sc;
		}
	}

	static int N;
	static int[][] map;
	static Student[] student;
	static List<Seat> list;
	
	static int[] score = {0, 1, 10, 100, 1000};
	static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));) 
		{
			N = Integer.parseInt(br.readLine());
			map = new int[21][21];
			student = new Student[401];
			list = new ArrayList<>();

			for (int i = 0; i < N * N; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int idx = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());

				student[idx] = new Student();
				student[idx].ps[0] = a;
				student[idx].ps[1] = b;
				student[idx].ps[2] = c;
				student[idx].ps[3] = d;

				solve(idx);
			}

			bw.write(getAnswer() + "\n");
			bw.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	//idx 학생이 착석할 수 있는 모든 자리를 구해준 다음 정렬을 통해 최적의 자리를 구해줌
	public static void solve(int idx) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				//다른 사람이 착석한 자리라면 Pass
				if (map[i][j] != 0) continue;

				Seat seat = new Seat(i, j, 0, 0);
				
				for (int d = 0; d < 4; ++d) {
					int ny = i + dir[d][0];
					int nx = j + dir[d][1];

					if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
					//인접한 빈 자리 수 +1
					if (map[ny][nx] == 0) {
						seat.ec++;
						continue;
					}

					for (int k = 0; k < 4; ++k) {
						//인접한 좋아하는 학생 수 +1
						if (student[idx].ps[k] == map[ny][nx]) {
							seat.sc++;
							break;
						}
					}
				}

				list.add(seat);
			}
		}

		Collections.sort(list);
		
		//최적의 자리에 idx 학생을 착석
		map[list.get(0).y][list.get(0).x] = idx;
		list.clear();
	}

	//모든 학생을 탐색하면서 선호 학생의 수를 카운트
	public static int getAnswer() {
		int ans = 0;
		
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				int cnt = 0;
				int idx = map[i][j];
				for (int d = 0; d < 4; ++d) {
					int ny = i + dir[d][0];
					int nx = j + dir[d][1];

					if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
					for (int k = 0; k < 4; ++k) {
						if (map[ny][nx] == student[idx].ps[k]) {
							cnt++;
							break;
						}
					}
				}
				ans += score[cnt];
			}
		}
		
		return ans;
	}
}