[ Baekjoon - 10/08 ] - 21608번: 상어 초등학교

• 문제 링크 : https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

 

• 소요 시간 : 1시간

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 1024MB
   • 문제
     • NxN의 격자(3≤N≤20), 학생의 번호 ni(1≤ni≤N*N)
     • 각 학생마다 좋아하는(인접하길 바라는) 학생이 4명씩 있다.
     • 자리를 배치할때, 
       1. 좋아하는 학생이 많이 인접하도록
       2. 좋아하는 학생이 같은수로 인접한 곳이 여러개라면, 인접한 칸중 빈곳이 많도록
       3. 빈곳도 마찬가지로 같은수가 있다면, 행번호가 가장작은곳으로
       4. 행번호가 같다면, 열번호가 가장 작은곳으로 배치한다.
   • 이해
     • 위 조건은 이해했는데 실제로 배치될때 어떤흐름인지 알기위해 예제를 그려보며 따라가보았다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 조건을 나열해보고, 문제에서 준 예제를 따라가며 이해했다.
3. 문제를 어떻게 해결할 것인가
   • 위 문제는 문제에서 준 조건대로 조건문을 이용해 분기점만 주면 될것같았고, N의 크기가 매우 작으며 메모리도 많이 주었기때문에 고민없이 완탐으로만 생각했다.
   • DFS와 BFS중에서, 인접한 곳을 중점적으로 다루고 이를 이용해 배치를 달리하기 때문에 BFS가 적합하다 생각했다.
   • 이중 반복문으로 map을 전체 순회하며, 각 칸마다 인접한 좋아하는사람과, 인접한 빈칸의 개수를 세고
      문제에서 준 4가지의 조건을 각각 만족하는지를 체크하며 처리해주면 될 듯했다.
   • 후에 한번더 BFS를 통해 점수를 계산하면 결과를 낼 수 있을거라 생각했다.
4. 위 계획을 검증
   • 정말.. 문제에서준 조건 그대로만 따라간 것이고 완탐이라 생략하겠다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main {
            static int N,ans=0;
            static HashMap<Integer, ArrayList<Integer>> check;
            static int[][] map;
            static int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                N = Integer.parseInt(br.readLine());
                map = new int[N + 1][N + 1];
        
                //해쉬맵 생성 (학생 - 좋아하는 학생 4명 번호)
                check = new HashMap<>();
                for (int nn = 0; nn < N * N; nn++) {
                    ArrayList<Integer> nearList = new ArrayList<>();
                    int[] likeStuList = new int[4];
        
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    int stu = Integer.parseInt(st.nextToken());
                    for (int dxy = 0; dxy < 4; dxy++) {
                        int likeStu = Integer.parseInt(st.nextToken());
                        nearList.add(likeStu);
                        likeStuList[dxy] = likeStu;
                    }
                    check.put(stu, nearList);
        
                    int near = -1;
                    int empty = -1;
                    int xx = 0;
                    int yy = 0;
                    for (int x = 1; x <= N; x++) {
                        for (int y = 1; y <= N; y++) {
                            if (map[x][y] != 0) {
                                continue;
                            }
                            int tNear = 0;
                            int tEmpty = 0;
                            for (int z = 0; z < 4; z++) {
                                int nx = x + dx[z];
                                int ny = y + dy[z];
                                // 맵안
                                if (0<nx && nx<=N && 0<ny && ny<=N) {
                                    // 좋아하는 사람이 있는 칸이라면, 인접한 사람 인원수 +1
                                    if (map[nx][ny] > 0 && (map[nx][ny] == likeStuList[0] || map[nx][ny] == likeStuList[1] || map[nx][ny] == likeStuList[2] || map[nx][ny] == likeStuList[3])) {
                                        tNear++;
                                    } // 비어있는 칸이라면
                                    else if (map[nx][ny] == 0) {
                                        tEmpty++;
                                    }
                                }
                            }
                            /*
                            문제에서 조건은
                            1. 좋아하는 학생이 많이 인접한 곳 선택
                            1번이 여러곳이라면 -> 2. 인접한 곳중 빈곳이 많은 곳 선택
                            2번이 여러곳이라면 -> 3. 행번호가 가장 작은곳
                            3번이 여러곳이라면 -> 4. 열번호가 가장 작은곳
                            이므로,
                             */
                            // 인접한곳이 많은 곳을 먼저 선택하고
                            if (tNear > near) {
                                near = tNear;
                                empty = tEmpty;
                                xx = x;
                                yy = y;
                            }// 인접한 곳이 여러곳이라면 빈곳이 많은 곳을 선택한다.
                            else if (tNear == near && tEmpty > empty) {
                                near = tNear;
                                empty = tEmpty;
                                xx = x;
                                yy = y;
                            }
                        }
                    }
                    //정해진 자리에 학생을 배치
                    map[xx][yy] = stu;
                }
        
                //점수를 계산하기
                for (int x = 1; x <= N; x++) {
                    for (int y = 1; y <= N; y++) {
                        int cnt = 0;
                        for (int k = 0; k < 4; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if (0<nx && nx<=N && 0<ny && ny<=N) {
                                if (check.get(map[x][y]).contains(map[nx][ny])) {
                                    cnt++;
                                }
                            }
                        }
                        // 인접한 학생 수 만큼 점수 +
                        ans += (int) Math.pow(10, cnt-1);
                    }
                }
                System.out.println(ans);
            }
        }

 

• 결과