[ BOJ ] 21608 상어 초등학교 S1 ( JAVA )

 

---

---

21608번: 상어 초등학교

문제 이해

- 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. - 학교에 다니는 학생의 수는 N^2명이다. 오늘은 모든 학생의 자리를 정하는 날이다.   학생은 1번부터 N^2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다.   교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. - 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. - 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. - 한 칸에는 학생 한 명의 자리만 있을 수 있고,   |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸이 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. - 예를 들어, N = 3이고, 학생 N^2명의 순서와 각 학생이 좋아하는 학생이 다음과 같은 경우를 생각해보자. - 가장 먼저, 4번 학생의 자리를 정해야 한다. 현재 교실의 모든 칸은 빈 칸이다.    2번 조건에 의해 인접한 칸 중에서 비어있는 칸이 가장 많은 칸인 (2, 2/)이 4번 학생의 자리가 된다. - 다음 학생은 3번이다. 1번 조건을 만족하는 칸은 (1, 2), (2, 1), (2, 3), (3, 2) 이다.   이 칸은 모두 비어있는 인접한 칸이 2개이다. 따라서, 3번 조건에 의해 (1, 2)가 3번 학생의 자리가 된다. - 다음은 9번 학생이다. 9번 학생이 좋아하는 학생의 번호는 8, 1, 2, 3이고, 이 중에 3은 자리에 앉아있다.   좋아하는 학생이 가장 많이 인접한 칸은 (1, 1), (1, 3)이다. 두 칸 모두 비어있는 인접한 칸이 1개이고, 행의 번호도 1이다.   따라서, 3번 조건에 의해 (1, 1)이 9번 학생의 자리가 된다. - 이번에 자리를 정할 학생은 8번 학생이다.   (2, 1)이 8번 학생이 좋아하는 학생과 가장 많이 인접한 칸이기 때문에, 여기가 그 학생의 자리이다. - 7번 학생의 자리를 정해보자.   1번 조건을 만족하는 칸은 (1, 3), (2, 3), (3, 1), (3, 2)로 총 4개가 있고,   비어있는 칸과 가장 많이 인접한 칸은 (2, 3), (3, 2)이다.   행의 번호가 작은 (2, 3)이 7번 학생의 자리가 된다. - 이런식으로 학생의 자리를 모두 정하면 다음과 같다. - 이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다.   학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다.   그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다. - 학생의 만족도의 총 합을 구해보자.

아이디어

1. Student Class를 따로 두어 관리했다.    ㄴ 선호하는 번호는 HashMap으로 관리하였다. 2. 실제 배치될 인원을 담을 ArrayList<Student>를 만들었다. 3. 배치인원의 위치를 기준으로 tmp배열의 값을 관리했다. 4. 시뮬..

코드

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

public class Main {

	static class Student {
		int sId;
		int x, y; // 배치되었을 때의 위치
		HashMap<Integer, Integer> likes = new HashMap<>();
		public Student(int sId, int[] likes) {
			this.sId = sId;
			for (int i = 0; i < likes.length; ++i) {
				this.likes.put(likes[i], 1);
			}
			this.x = this.y = -1; // 배치 되기 전이므로 -1로 둔다.
		}
	}
	static int N, map[][];
	static int[] score = { 0, 1, 10, 100, 1000 }; // 점수표
	static int[][] dir = { { -1, 1, 0, 0 }, { 0, 0, -1, 1 } };
	static ArrayList<Student> batchedStudent = new ArrayList<>(); // 배치된 학생들의 리스트
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		Queue<Student> students = new LinkedList<>(); // 배치할 학생들
		for (int i = 0; i < N * N; ++i) {
			st = new StringTokenizer(br.readLine());
			students.offer(new Student(stoi(st.nextToken()), new int[] { stoi(st.nextToken()), stoi(st.nextToken()),
					stoi(st.nextToken()), stoi(st.nextToken()) }));
		}
		// map을 인접 빈칸 갯수로 초기화한다.
		map = new int[N][N];
		initEmptyBlock(map);
		// 학생들을 배치한다.
		while (!students.isEmpty()) {
			Student now = students.poll();
			batchStudent(now);
		}
		// 학생의 만족도 총 합을 출력한다.
		System.out.println(getScore());
	}
	
	// 만족도의 총 합
	static int getScore() {
		int answer = 0;
		for (Student s : batchedStudent) {
			int cnt = 0;
			for (int d = 0; d < 4; ++d) {
				int nx = s.x + dir[0][d];
				int ny = s.y + dir[1][d];
				if(!isBoundary(nx,ny)) continue;
				if (s.likes.containsKey(map[nx][ny] * -1)) {
					++cnt;
				}
			}
			answer += score[cnt]; // 점수를 합산한다.
		}
		return answer;
	}
	
	// 주위 빈 칸의 개수를 반환
	static int getEmptyCnt(int x, int y) {
		int cnt = 0;
		for(int d=0;d<4;++d) {
			int nx = x+dir[0][d];
			int ny = y+dir[1][d];
			if(isBoundary(nx,ny) && map[nx][ny]>0) ++cnt;
		}
		return cnt;
	}
	
	// 입력받은 배열에 주위 좋아하는 학생
	static void batchStudent(Student now) {
		int max = -1, x = -1, y = -1;
		if (batchedStudent.size() == 0) { // 배치된 학생이 없다면
			// 빈칸이 가장 많은 곳에 넣는다.
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					if (max < map[i][j]) {
						max = map[i][j];
						x = i;
						y = j;
					}
				}
			}
		} else { // 배치된 사람이 있다면
			int[][] tmp = new int[N][N]; // 주위에 선호하는 사람의 수
			for (Student s : batchedStudent) {
				if (now.likes.containsKey(s.sId)) { // 선호 목록에 있으면
					for (int d = 0; d < 4; ++d) {
						int nx = s.x + dir[0][d];
						int ny = s.y + dir[1][d];
						if (isBoundary(nx, ny) && map[nx][ny] > 0) {
							tmp[nx][ny]++;
						}
					}
				}
			}
			// 가장 큰 값 찾기
			boolean isDupl = false; // 여러개인 경우의 플래그
			Queue<int[]> big = new LinkedList<>(); // 여러개일 때 비교할 대상을 담을 큐
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					if (map[i][j]>0) { // 이미 배치된 곳을 제외한 곳을 검사
						if (max < tmp[i][j]) {
							max = tmp[i][j];
							x = i;
							y = j;
							isDupl=false;
							big.clear(); // 초기화를 해주고 담아준다.
							big.add(new int[] {i,j});
						} else if (max == tmp[i][j]) { // 같은 곳이 여러곳
							big.add(new int[] {i,j});
							isDupl = true; // 플래그
						}
					}
				}
			}
			if(isDupl) {
				// 빈칸을 가장 많이 가진 것을 저장한다. 최상단 최좌측부터 담겨져있음. 2,3번 조건
				max = -1;
				while(!big.isEmpty()) {
					int[] b = big.poll();
					int bCnt = getEmptyCnt(b[0], b[1]);//주위 빈칸의 개수를 가져온다.
					if(max < bCnt) { // 최초값만 저장하면되므로
						max = bCnt;
						x=b[0];
						y=b[1];
					}
				}
			}
		}
		now.x = x;
		now.y = y;
		batchedStudent.add(now);
		map[x][y] = -1 * now.sId; // 음수로 학생의 번호를 저장해둔다.
	}

	// 입력받은 배열에 주위 빈칸의 개수를 반환
	static void initEmptyBlock(int[][] map) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				int cnt = 4;
				if (i == 0 || i == N - 1) --cnt;
				if (j == 0 || j == N - 1) --cnt;
				map[i][j] = cnt;
			}
		}
	}

	static boolean isBoundary(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < N;
	}

	static int stoi(String s) {
		return Integer.parseInt(s) - 1;
	}
}

 

 

 

---

 

CPDM