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

문제

문제를 간략하게 설명하자면 자리배정을 하는데 각 학생이 좋아하는 학생의 번호를 네 개 가지고 있고 입력 순서대로 자리를 배정한 뒤 학생의 만족도 총 합을 구하는 문제이다.
자리를 배정하는 규칙은 위에서 설명한 세 가지 규칙을 따른다.
인접하다는 규칙은 상하좌우로 맞닿아있는 것을 뜻한다.

풀이

우선 HashMap에 입력으로 받은 학생과 그 학생이 좋아하는 학생의 배열을 저장한다. (마지막 만족도 총 합을 구하기 위해)
그리고 입력받은 순서대로 조건에 부당하는지 찾는다.

첫 번째 조건은 좋아하는 학생과 몇 명 인접해있는지를 찾는 것이고
두 번째 조건은 인접한 자리에 빈 자리가 많아야하므로 모두 인접한 자리에 대해 조건이 걸려있다.
따라서 1,2 조건은 묶어서 진행한다. (하지만 1번 조건이 우선순위가 높으므로 아무리 2번 조건을 만족해도 1번을 이길 수 없도록 1번 점수를 10배 더 준다)

1. temp라는 임시 교실을 만들고 빈 자리를 차례로 순회한다.
2. 빈 자리에 인접한 자리를 찾는다.
3. 그 자리가 지금 입력으로 들어온 학생이 좋아하는 학생인지 아니면 빈자린지 확인한다.
4. 만약 좋아하는 학생이면 temp에서 그 자리에 10점을 더한다.
5. 빈 자리라면 그 자리에 1점을 더한다.
6. 순회가 끝나면 temp에서 점수가 가장 높은 곳에 입력으로 들어온 학생을 배치한다.

이것을 모든 학생에 대해 반복한 뒤 자리가 모두 채워지면
다시 교실을 순회하면서 만족도를 구한다.

코드

static int N, ans;
static HashMap<Integer, int[]> like = new HashMap(); // 좋아하는 학생의 배열을 담는 Map
static int[][] map; // 교실
static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

전역변수이다.

for (int i = 0; i < N*N; i++) {
    int[] cur = new int[4];
    int index = fr.nextInt();
    for (int j = 0; j < 4; j++) {
        cur[j] = fr.nextInt();
    }
    like.put(index, cur); // HashMap에 저장
    place(index, cur); // 자리배치 시작
}

입력에 받은 순서대로 map에 저장하고 자리배치를 시작한다.

// 1. 비어있는 칸 중 좋아하는 학생 번호가 몇 개 인접한지 (+10)
// 2. 비어있는 칸 중 인접한 빈 칸이 몇개인지 (+1)
int[][] temp = new int[N][N]; // 임시 교실
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        temp[i][j] = -1; // -1로 초기화
        if (map[i][j] > 0) continue;
        // 비어있는 칸중 인접한 좋아하는 학생번호와 빈 칸 개수 확인
        int score = 0; // 비어있는 칸의 점수
        for (int k = 0; k < 4; k++) {
            // 인접한 좌표
            int newR = i + dir[k][0];
            int newC = j + dir[k][1];
            if (newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
            for (int l = 0; l < 4; l++) {
                if (map[newR][newC] == cur[l]) {
                    score += 10; // 좋아하는 학생이면 10점 추가
                }
            }
            if (map[newR][newC] == 0) {
                score++; // 빈 자리면 1점 추가
            }
        }
        if (score > temp[i][j]) temp[i][j] = score; // 최대값으로 갱신
    }
}

score는 지금 확인할 빈자리에 대해 조건의 점수를 뜻한다.
2번의 조건이 아무리 높아도 4점이기 때문에 1번의 조건(10점)을 역전할 수는 없다.

빈 자리 한 곳에 대해 네 번의 인접한 자리(newR, newC)를 찾는다.
만약 교실을 벗어난다면 무시한다.
인접한 자리가 현재 배치중인 학생의 좋아하는 학생 중에 있는지 찾는다.
만약 있으면 score 변수에 10을 더한다.
인접한 자리가 만약 빈 자리라면 score 변수에 1을 더한다.
score 변수를 무조건 temp에 적용시키는 것이 아니라
temp보다 높아야 temp에 넣는다.

// 3. 순회하면서 제일 적당한 곳 찾기
int max = -1;
int bestR = 0; int bestC = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (temp[i][j] > max) {
            max = temp[i][j];
            bestR = i;
            bestC = j;
        }
    }
}
// 적당한 곳이 아무곳도 없을 때
if (max == -1) {
    point:
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 0) {
                bestR = i;
                bestC = j;
                break point;
            }
        }
    }
}

3번 조건을 만족하기 위해 최대값을 찾을 때 같은 값은 무시한다.
만약 3번 조건도 만족하지 않은 학생이 있을 수 있기 때문에 그런 학생은 그냥 빈 자리에 배치시킨다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        int people = 0;
        for (int k = 0; k < 4; k++) {
            // 인접한 좌표
            int newR = i + dir[k][0];
            int newC = j + dir[k][1];
            if (newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
            for (int l = 0; l < 4; l++) {
                if (map[newR][newC] == score.get(map[i][j])[l]) {
                    people++;
                }
            }
        }
        if (people == 1) ans += 1;
        else if (people == 2) ans += 10;
        else if (people == 3) ans += 100;
        else if (people == 4) ans += 1000;
    }
}
System.out.println(ans);

총 만족도를 각각 구한다.
그리고 정답을 출력한다.

전체코드

package baekjoon._21608;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int N, ans;
    static HashMap<Integer, int[]> score = new HashMap(); // 좋은하는 학생의 배열을 담는 Map
    static int[][] map; // 교실
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        map = new int[N][N];
        for (int i = 0; i < N * N; i++) {
            int[] cur = new int[4];
            int index = fr.nextInt();
            for (int j = 0; j < 4; j++) {
                cur[j] = fr.nextInt();
            }
            score.put(index, cur);
            place(index, cur); // 자리배치 시작
        }
    }

    private static void place(int index, int[] cur) {
        // 1. 비어있는 칸 중 좋아하는 학생 번호가 몇 개 인접한지 (+10)
        // 2. 비어있는 칸 중 인접한 빈 칸이 몇개인지 (+1)
        int[][] temp = new int[N][N]; // 임시 교실
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                temp[i][j] = -1; // -1로 초기화
                if (map[i][j] > 0) continue;
                // 비어있는 칸중 인접한 좋아하는 학생번호와 빈 칸 개수 확인
                int score = 0; // 비어있는 칸의 점수
                for (int k = 0; k < 4; k++) {
                    // 인접한 좌표
                    int newR = i + dir[k][0];
                    int newC = j + dir[k][1];
                    if (newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
                    for (int l = 0; l < 4; l++) {
                        if (map[newR][newC] == cur[l]) {
                            score += 10; // 좋아하는 학생이면 10점 추가
                        }
                    }
                    if (map[newR][newC] == 0) {
                        score++; // 빈 자리면 1점 추가
                    }
                }
                if (score > temp[i][j]) temp[i][j] = score; // 최대값으로 갱신
            }
        }
// 3. 순회하면서 제일 적당한 곳 찾기
        int max = -1;
        int bestR = 0;
        int bestC = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (temp[i][j] > max) {
                    max = temp[i][j];
                    bestR = i;
                    bestC = j;
                }
            }
        }
// 적당한 곳이 아무곳도 없을 때
        if (max == -1) {
            point:
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == 0) {
                        bestR = i;
                        bestC = j;
                        break point;
                    }
                }
            }
        }
        map[bestR][bestC] = index;
    }

    public static void main(String[] args) {
        input();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int people = 0;
                for (int k = 0; k < 4; k++) {
                    // 인접한 좌표
                    int newR = i + dir[k][0];
                    int newC = j + dir[k][1];
                    if (newR < 0 || newC < 0 || newR >= N || newC >= N) continue;
                    for (int l = 0; l < 4; l++) {
                        if (map[newR][newC] == score.get(map[i][j])[l]) {
                            people++;
                        }
                    }
                }
                if (people == 1) ans += 1;
                else if (people == 2) ans += 10;
                else if (people == 3) ans += 100;
                else if (people == 4) ans += 1000;
            }
        }
        System.out.println(ans);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

시뮬레이션 문제는 무작정 코드를 작성하는게 아니라 처음 설계를 어떻게 하느냐에 따라 문제 풀이 시간이 결정되는 것 같다.