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

문제내용

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

21608번: 상어 초등학교

---

문제풀이

삼성 기출문제답게 상하좌우로 인덱스를 이동시키고 추가적인 조건을 걸어서 푸는 문제다.

문제에서 인접한 곳이란 결국 현재 인덱스 기준 상하좌우를 의미한다.

 

필자는 해당문제를 상하좌우 인덱스이동 + 정렬로 풀어냈다. 이를 풀기 위해 저장공간의 선언이 필요한데

1. 학생수 n.

2. 2차원 배열 arr -> arr[학생번호][좋아하는 학생수 4명] = 좋아하는 학생.

3. 2차원 배열 map -> 학생을 배치할 배열

4. List<Integer> seq -> 입력받은 학생의 순서를 저장해줄 리스트

5. List<Node> list -> 입력받은 학생을 탐색할때 map전체를 순회하면서 "비어있는 공간 , 좋아요, 행, 열" 정보를 저장.

 

총 5가지의 저장공간이 핵심이라고 볼수 있다.

 

이를 이용해 seq 크기만큼 반복문을 돌리고,

각 학생마다 어디에 좌석을 배치할지 체크한다.

이후, 모든 학생이 좌석에 앉았다면 map배열 전체를 순회하면서 각 학생의 상하좌우에 좋아하는 학생 수에 따른 만족도를 올려주면된다.

 

또한, 문제에서 초기 map은 비어있고 1,2,3번 조건에 의해 첫번째 학생은 무조건 (1,1)자리에 위치하게 된다는걸 참고하자.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int n,ans;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static int[][] map;//좌석
	static int[][] arr;//학생, 좋아하는 학생
	static ArrayList<Integer> seq = new ArrayList<>();//입력받은 학생의 순서
	static List<Node> list;//탐색하는 학생이 어디 앉을지 정하기 위해 필요한 배열
	static class Node{
		int x,y,like,space;
		public Node(int x, int y, int like, int space) {
			this.x = x;
			this.y = y;
			this.like = like;
			this.space = space;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		ans = 0;
		n = Integer.parseInt(br.readLine());
		arr = new int[(n*n)+1][4];
		map = new int[n][n];
		
		for(int i=0; i<n*n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			seq.add(a);
			
			for(int j=0; j<4; j++) {
				arr[a][j] = Integer.parseInt(st.nextToken());
			}	
		}
		
		solve();
		
		System.out.println(ans);
	}
	
	
	public static void solve() {
		map[1][1] = seq.get(0);//첫번째 학생은 무조건 1,1
		
		//모든학생 탐색
		for(int k=1; k<seq.size(); k++) {
			int num = seq.get(k);
			list = new ArrayList<>();
			
			for(int i=0; i<map.length; i++) {
				for(int j=0; j<map.length; j++) {
					if(map[i][j]!=0) continue;//비어있는 자리가 아니면 무시
					UDRL(i,j,num);//상하좌우 탐색해서 비어있는공간, 좋아하는 학생수 알아내기.
				}
			}
			
			//1, 2, 3 번조건에 의한 정렬.
			Collections.sort(list, new Comparator<Node>() {
				@Override
				public int compare(Node o1, Node o2) {
					int l1=o1.like, l2=o2.like;
					if(l1>l2) return -1;
					else if(l1<l2) return 1;
					else {
						int s1=o1.space, s2=o2.space;
						if(s1>s2) return -1;
						else if(s1<s2) return 1;
						else {
							int x1=o1.x, x2=o2.x;
							if(x1>x2) return 1;
							else if(x1<x2) return -1;
							else {
								int y1=o1.y, y2=o2.y;
								if(y1>y2) return 1;
								else if(y1<y2) return -1;
								else return 0;
							}
							
						}
					}
				}
			});//정렬 완료
			
			//정렬후 첫번째 좌석이 앉을자리임.
			Node node = list.get(0);
			map[node.x][node.y] = num;
			
		}//for(모든학생 탐색 반복문 끝)
		
		//만족도 구하기 위해 map 순회
		for(int x=0; x<n; x++) {
			for(int y=0; y<n; y++) {
				int stud = map[x][y];
				int cnt = 0;
				for(int i=0; i<4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					
					if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
					
					//현재 학생이 좋아하는애가 인접한곳에 있으면 cnt 증가.
					for(int j=0; j<4; j++) {
						if(arr[stud][j]==map[nx][ny]) cnt++;
					}
				}
				if(cnt==1) ans+=1;
				else if(cnt==2) ans+=10;
				else if(cnt==3) ans+=100;
				else if(cnt==4) ans+=1000;
			}
		}
	}
	
	public static void UDRL(int cx, int cy, int num) {
		int space=0, like=0;
		//상하좌우 탐색
		for(int i=0; i<4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			
			if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
			
			//인접한곳에 누군가 있다면
			if(map[nx][ny]!=0) {
				//좋아하는 학생이 있는지 찾기
				for(int j=0; j<4; j++) {
					if(arr[num][j]==map[nx][ny]) {//좋아하는 학생있을때
						like++;
						break;
					}
				}
			}
			else space++;//인접한곳에 아무도 없을때
		}//for(상하좌우)
		
		//탐색한 좌석 정보 넣기
		list.add(new Node(cx,cy,like,space));
	}
}

---

마치며

크게 어렵다고 생각한 문제는 아니지만 이것저것 조건을 따지는 코드를 넣다보니 굉장히 길어졌고 시간도 좀 잡아먹었던 문제다.