[백준] 알고리즘 분류(구현,JAVA)21608번, 상어 초등학교

문제 링크

21608번: 상어 초등학교

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. |r₁ - r₂| + |c₁ - c₂| = 0의 만족하면 인접한다고 판단할 수 있습니다.

2. 입력된 학생 순서대로 자리에 착석합니다.

3. 학생들이 자리에 착석하는 곳은 문제에 조건에 맞게 착석합니다.

4. 학생이 모두 앉았을 때 학생의 만족도 값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. N×N명의 학생이 자리에 조건에 맞게 자리에 착석을 진행합니다.

 

3. 모든 학생이 착성했을 때 학생의 만족도를 결과로 출력합니다.

 

 

조건에 맞게 자리에 착석

인접한 공간?

|r₁ - r₂| + |c₁ - c₂| = 0

 

인접하려면 위에 조건을 만족해야합니다.

(0, 0)을 기준으로 위에 조건을 만족하는 것을 찾아보면

(-1, -1)	(-1, 0)	(-1, 1)
(0, -1)	(0, 0)	(0, 1)
(1, -1)	(1, 0)	(1, 1)

위치 기준 상하좌우가 인접한 칸이라는 것을 확인하실 수 있습니다.

 

인접한 공간을 파악했다면!

 

학생들이 순차적으로 앉는 과정의 조건을 살펴봅시다.

 

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.

해석 : 비어있는 칸을 상하좌우 탐색하여 좋아하는 학생이 많은 칸이 우선순위를 갖는다.

 

2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.

해석 : 비어있는 칸을 상하좌우 탐색하여 빈 공간(0)이 많은 칸이 우선순위를 갖는다.

 

3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

해석 : 행의 번호가 작은 칸이 우선순위를 갖는다, 하지만 행도 같으면 열이 작은 칸이 우선순위를 갖는다

 

진행과정은 문제에 그림과 제가 표현하는 예제입력2를 확인하시면 이해하시기 편하실 것입니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 3

 

학생 정보

 

4	{2, 5, 1, 7}
2	{1, 9, 4, 5}
5	{8, 1, 4, 3}
1	{2, 9, 3, 4}
7	{2, 3, 4, 8}
9	{8, 4, 5, 7}
6	{5, 2, 3, 4}
8	{4, 9, 2, 1}
3	{9, 2, 1, 4}

 

2. N×N명의 학생이 자리에 조건에 맞게 자리에 착석을 진행합니다.

 

현재 교실 상태

 

0	0	0
0	0	0
0	0	0

 

4번 학생 착석!

 

최대 좋아하는 친구 : 0 ({0, 0}, {0, 1} .....)

최대 빈 칸 개수 : 4({1, 1})

2번 조건 달성 :  {1 , 1} 착석 진행!

 

0	0	0
0	4	0
0	0	0

 

2번 학생 착석!

 

최대 좋아하는 친구 : 1 ({0, 1}, {1, 0}, {1, 2}, {2, 1})

최대 빈 칸 개수 : 2({0, 1}, {1, 0}, {1, 2}, {2, 1})

최소 행의 값 : 0({0, 1})

3번의 최소 행 조건 달성 :  {0 , 1} 착석 진행!

 

0	2	0
0	4	0
0	0	0

 

5번 학생 착석!

 

최대 좋아하는 친구 : 1 ({0, 0}, {0, 2}, {1, 0}, {1, 2}, {2, 1})

최대 빈 칸 개수 : 2({1, 0}, {1, 2}, {2, 1})

최소 행의 값 : 1({1, 0}, {1, 2})

최소 열의 값 : 0({1, 0}

3번의 최소 열 조건 달성 :  {1 , 0} 착석 진행!

 

0	2	0
5	4	0
0	0	0

 

1번 학생 착석!

 

최대 좋아하는 친구 : 1 ({1, 2}, {2, 1})

최대 빈 칸 개수 : 2({1, 2}, {2, 1})

최소 행의 값 : 1({1, 2})

3번의 최소 행 조건 달성 :  {1 , 2} 착석 진행!

 

0	2	0
5	4	1
0	0	0

 

.......

 

모두 자리 착석 후

 

6 : 2	2 : 1	8 : 2
5 : 1	4 : 4	1 : 2
9 : 2	7 : 2	3 : 1

 

3. 모든 학생이 착성했을 때 학생의 만족도를 결과로 출력합니다.

 

교실 정보

 

6	2	8
5	4	1
9	7	3

 

인접하고 좋아하는 사람의 수 정보

 

6 : 2명	2 : 1명	8 : 2명
5 : 1명	4 : 4명	1 : 2명
9 : 2명	7 : 2명	3 : 1명

 

4명 : 1개(7)

 

3명 : 0개

 

2명 : 5개(1, 6, 7, 8, 9)

 

1명 : 3개(2, 3, 5)

 

0명 : 0개

 

1000×1 + 100×0 + 10×5 + 1×3 + 0×0 = 1053

 

1053을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 학생들의 정보를 띄어쓰기 기준 나누었습니다.
• search를 실행하여 순차적으로 들어오는 학생들의 착석을 진행합니다.
• cal을 실행하여 학생의 만족도를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 조건에 최우선순위 칸으로 착석하도록 진행합니다.
• inSpace함수는 이동하려는 칸이 교실 내에 존재하는지 확인합니다.
• cal함수는 교실의 정보를 토대로 학생 만족도를 구합니다.

 

결과코드

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

public class Main {
    //착석 조건 관련 정보 클래스
    static class info{
        //blank : 인접 빈 칸, favoriteCount : 인접 좋아하는 친구
        int blank, favoriteCount, x, y;
        //생성자
        public info(int blank, int favoriteCount, int x, int y){
            this.blank = blank;
            this.favoriteCount = favoriteCount;
            this.x = x;
            this.y = y;
        }
    }
    static int[][] room;	//교실 정보 저장 배열
    //각 학생별 좋아하는 친구 저장 리스트
    static ArrayList<ArrayList<Integer>> favorite = new ArrayList<>();
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y변경값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        room = new int[N][N];
        //좋아하는 친구 리스트 초기화
        for(int i=0;i<=N*N;i++)
            favorite.add(new ArrayList<>());

        StringTokenizer st;
        //각 학생별 순차적으로 착석 진행!
        for(int i=0;i<N*N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int index = Integer.parseInt(st.nextToken());
            //좋아하는 학생 정보 리스트에 저장
            for(int j=0;j<4;j++)
                favorite.get(index).add(Integer.parseInt(st.nextToken()));
            search(index, N);	//착석 진행!
        }
        bw.write(cal(N) + "");	//학생 만족도 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //학생 착석 진행하는 함수
    static void search(int index ,int N){
        //조건에 가장 높은 우선순위 값
        info max = new info(0, 0, N, N);
        //착석할 칸 탐색 진행!
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                //이미 착석한 친구가 있을 때
                if(room[i][j]!=0)
                    continue;
                int blank = 0;
                int favoriteCount = 0;
                //인접한 칸 탐색
                for(int s = 0;s<4;s++){
                    int tempX = j + dx[s];
                    int tempY = i + dy[s];
                    if(inSpace(tempX,tempY, N)){
                        if(room[tempY][tempX] == 0)	//빈 공간일 때
                            blank++;
                        //좋아하는 친구일 때
                        else if(favorite.get(index).contains(room[tempY][tempX])){
                            favoriteCount++;
                        }
                    }
                }
                //조건 1. 좋아하는 친구 수 기준
                if(favoriteCount > max.favoriteCount)
                    max = new info(blank, favoriteCount, j, i);
                else if(favoriteCount == max.favoriteCount){
                    if(blank > max.blank)	//조건 2. 인접한 빈칸 수 기준
                        max = new info(blank, favoriteCount, j, i);
                    else if(blank == max.blank){
                        if(i<max.y)	//조건 3. 행 낮은 값 기준
                            max = new info(blank, favoriteCount, j, i);
                        else if(i == max.y){
                            if(j > max.x)	//조건 3. 열 낮은 값 기준
                                max = new info(blank, favoriteCount, j, i);
                        }
                    }
                }
            }
        }
        room[max.y][max.x] = index;	//학생 착석!
    }
    //학생 만족도 계산하는 함수
    static int cal(int N){
        int result = 0;
        for (int i = 0; i < N; i++){
             for (int j = 0; j < N; j++){
                 int count = 0;
                 //인접한 칸 탐색
                 for(int s = 0;s<4;s++){
                     int tempX = j + dx[s];
                     int tempY = i + dy[s];
                     //인접하고 좋아하는 친구일 때
                     if(inSpace(tempX,tempY, N) && favorite.get(room[i][j]).contains(room[tempY][tempX])){
                         count++;
                     }
                 }
                 //해당 학생 행복도 더하기!
                 if(count > 0)
                    result += Math.pow(10, count-1);
             }
        }
        return result;
    }
    //이동하려는 칸이 교실에 벗어나는지 확인하는 함수
    static boolean inSpace(int x, int y, int N){
        //교실 내에 있는 칸일 때
        if(x>=0 && y>=0 && x< N && y<N)
            return true;
        return false;
    }
}