문제 풀이

단순 구현문제다.
학생의 번호를 기록할 students 배열,
학생 i가 j를 좋아하는지를 기록하기 위한 2차원배열 like,
학생이 어디 배치되었는지 기록하는 2차원배열 map 등을 이용하여 풀이한다.

규칙을 보면 아래와 같이 배치를 하라고 되어있는데 말 그대로 배치하면된다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

이 말을 잘 생각해보면 결국 우리가 평소에 일반적으로 사용하는 이중 for문으로 왼쪽위부터 오른쪽 아래까지 진행하면서 적절한 곳에 배치하라는 것인데, 좋아하는 학생 수, 빈자리 수 등의 조건이 우세하면 같은 조건중에서도 먼저 방문한 곳을 선택하라는 뜻이란걸 알 수 있다.

배치를 하는 코드는 아래와 같다.

 for (int j=0;j<n;j++) // map의 행
            {
                for(int k=0;k<n;k++) //map의 열, 왼쪽 위부터 오른쪽 아래까지 진행
                {
                    int like_cnt = 0;
                    int empty_cnt = 0;
                    if(map[j][k] != 0) // 이미 채워져 있으면 패스
                        continue;
                    for(int m=0;m<4;m++) // 4방향 탐색
                    {
                        int ny = j + dy[m];
                        int nx = k + dx[m];
                        for(int l=1;l<=n*n;l++) // 모든 학생에 대하여
                        {
                            if(nx>=0 && ny>=0 && nx< n && ny< n && map[ny][nx] == l && like[cur_std][l]) // 좋아하는 학생이 있으면 따봉
                                like_cnt++;
                        }
                        if(nx>=0 && ny>=0 && nx< n && ny< n && map[ny][nx] == 0) //비었는지 확인
                            empty_cnt++;
                    }
                    if (like_cnt == max_like && empty_cnt > max_empty) { // 좋아하는 학생수가 같으면 빈 공간이 더 많은 곳을 선택한다.
                        y= j;
                        x= k;
                        max_empty =empty_cnt;
                    }
                    else if (like_cnt > max_like)
                    {
                      y= j;
                      x= k;
                      max_like = like_cnt;
                      max_empty = empty_cnt;
                    }
                }
            }
            map[y][x] = cur_std;
        }

이제 만족도를 계산하면 되는데 문제에 나와있는대로 계산 해주면 된다.

문제 링크

boj/21608

소스코드

PS/21608.java

import java.io.*;
import java.util.StringTokenizer;
import java.util.Vector;


public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int []dx = {1,0,0,-1};
    static int []dy= {0,1,-1,0};
    public static void main(String[] args) throws IOException {
      int n = Integer.parseInt(br.readLine());
      int []students = new int[n*n];
      boolean [][]like = new boolean[n*n+1][n*n+1];
      int [][] map = new int[n][n];
      for(int i=0;i<n*n;i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int s = Integer.parseInt(st.nextToken());
          students[i] = s;
          while(st.hasMoreTokens()) {
              int a = Integer.parseInt(st.nextToken());
              like[s][a] = true;
          }
      }
      map[1][1] = students[0];
        for(int i=1;i<n*n;i++) {
            int cur_std = students[i];
            int max_like = -1;
            int max_empty = -1;
            int x=0,y=0;
            for (int j=0;j<n;j++)
            {
                for(int k=0;k<n;k++)
                {
                    int like_cnt = 0;
                    int empty_cnt = 0;
                    if(map[j][k] != 0)
                        continue;
                    for(int m=0;m<4;m++)
                    {
                        int ny = j + dy[m];
                        int nx = k + dx[m];
                        for(int l=1;l<=n*n;l++)
                        {
                            if(nx>=0 && ny>=0 && nx< n && ny< n && map[ny][nx] == l && like[cur_std][l])
                                like_cnt++;
                        }
                        if(nx>=0 && ny>=0 && nx< n && ny< n && map[ny][nx] == 0)
                            empty_cnt++;
                    }
                    if (like_cnt == max_like && empty_cnt > max_empty) {
                        y= j;
                        x= k;
                        max_empty =empty_cnt;
                    }
                    else if (like_cnt > max_like)
                    {
                      y= j;
                      x= k;
                      max_like = like_cnt;
                      max_empty = empty_cnt;
                    }
                }
            }
            map[y][x] = cur_std;
        }
        int answer = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                int cur_std = map[i][j];
                int good = 0;
                for(int l=0;l<4;l++) {
                    int nx = j + dx[l];
                    int ny = i + dy[l];
                    for (int k = 1; k <= n * n; k++) {
                        if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[ny][nx] == k && like[cur_std][k]) {
                            if (good == 0)
                                good = 1;
                            else
                                good *= 10;
                        }
                    }
                }
                answer += good;
            }
        }
        System.out.println(answer);
    }
}