[C++] 백준 21608 : 상어 초등학교

#include <iostream>
#include <vector>
#include <algorithm> // sort

using namespace std;

// 학생 정보
struct STUDENT{
  int num; // 학생 번호
  int fav[4]; // 학생이 좋아하는 친구
};

struct POSITION{
  int x, y;
  int blanks;
  int friends;
};

int map[21][21]; // 자리
vector<STUDENT> st(401); // 학생 정보

int N;
int ans = 0;

// 인접 좌표
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

// 만족도 - 굳이 pow 쓰지말자
int score[5] = {0, 1, 10, 100, 1000};

int main(int argc, char** argv){
  scanf("%d", &N);

  for(int i = 1; i <= N * N; i++){
    scanf("%d", &st[i].num); // 학생 순서 입력받기
    for(int j = 0; j < 4; j++){
      scanf("%d", &st[i].fav[j]); // 좋아하는 학생 입력받기
    }
  }

  // 학생 앉히기
  for(int i = 1; i <= N * N; i++){
    STUDENT student = st[i];
    vector<POSITION> pos(5); // 총 주위 4칸 탐색

    int bmax = 0, fmax = 0;
    
    for(int j = 1; j <= N; j++){
      for(int k = 1; k <= N; k++){
        // 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정함
        // 비어있지 않으면 패스 - if문 너무 많이 써서 따로 빼려고 이렇게 작성
        if(map[j][k] != 0){
          continue;
        }

        int bcnt = 0, fcnt = 0;
        
        // 좌표 방향 설정 idx값은 이렇게 설정하는게 더 확인하기 쉽다.
        for(int dir = 0; dir < 4; dir++){
          int nx = j + dx[dir];
          int ny = k + dy[dir];

          // 보드 벗어나는 좌표
          if(nx < 1 || ny < 1 || nx > N || ny > N){
            continue;
          }

          // 빈 칸인 경우와 친구의 수를 한 번에 센다!
          // 빈 칸인 경우
          if(map[nx][ny] == 0){
            bcnt++;
          } else if(map[nx][ny] == student.fav[0] || map[nx][ny] == student.fav[1]
            || map[nx][ny] == student.fav[2] || map[nx][ny] == student.fav[3]){
            fcnt++;
          }
        }

        // 친구 많은 칸을 넣음
        if(fcnt > fmax){
          pos.clear(); // 벡터 초기화 - 친구 많으면 후보 요소 없음
          pos.push_back({j, k, fcnt, bcnt});
          // 후보칸의 요소 저장
          fmax = fcnt;
          bmax = bcnt;
          continue;
        } else if(fcnt == fmax){
          // 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
          if(bcnt >= bmax){
            pos.clear();
            pos.push_back({j, k, fcnt, bcnt});
            bmax = bcnt;
          } else {
            // 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
            pos.push_back({j, k, fcnt, bcnt});
          }
        }
      }

      // for(int i = 1; i <= N; i++){
      //   for(int j = 1; j <= N; j++){
      //     printf("%d", map[i][j]);
      //   }
      //   printf("\n");
      // }
      // printf("------\n");
    }
    // 학생 배치
    map[pos[0].x][pos[0].y] = student.num;
  }

  // 학생 만족도 총 합
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      int cnt = 0;
      // 상하좌우 탐색
      for(int dir = 0; dir < 4; dir++){
        int nx = i + dx[dir];
        int ny = j + dy[dir];

        if(nx < 1 || ny < 1 || nx > N || ny > N){
          continue;
        }

        for(int k = 0; k < st.size(); k++){
          if(st[k].num == map[i][j]){
            if(map[nx][ny] == st[k].fav[0] || map[nx][ny] == st[k].fav[1]
              || map[nx][ny] == st[k].fav[2] || map[nx][ny] == st[k].fav[3]){
              cnt++;
            }
          }
        }
      }
      ans += score[cnt];
    }
  }

  // for(int i = 1; i <= N; i++){
  //   for(int j = 1; j <= N; j++){
  //     printf("%d", map[i][j]);
  //   }
  //   printf("\n");
  // }

  printf("%d", ans);

  return 0;
}

와 구현 노가다 문제는 진짜 진짜 어렵다... 시간 정말 오래 걸린듯

오늘 배운 것

• 여러개의 구성 요소를 가질 때는 구조체를 쓰는 것이 편하다
• for문 중첩이 너무 많은 경우에는 아예 continue를 써서 예외 상황을 빼버리는 것이 좀 더 한 눈에 알아보기 편하다.
• 좌표 방향을 도는 for문의 idx 변수는 dir을 쓰는게 알아보기 쉽다.
• 벡터 초기화는 (벡터).clear();

주의사항

• pos에는 후보칸의 위치와 그에 따른 정보가 들어간다. 따라서 인접 친구가 더 많은 경우만 후보자로 정한다. clear를 사용하여 가장 강력한 후보를 제일 앞으로 보낸다.

• 하지만, 2번 조건은 다르다. 비어있는 칸이 많은 칸으로 자리를 정하고, 3번 조건에 따르면 행의 번호가 작은 칸 -> 열의 번호가 작은 칸이므로 부등호를 '>'가 아닌 '>='을 사용하여 해당 경우도 만족시키도록 한다. (for문을 사용해 작은 부분부터 순회하기 때문에 부등호로 해당 경우도 처리할 수 있다.) 이 때도 가장 강력한 후보자이므로 clear를 시켜 후보자를 제일 앞으로 보낸다.

• 하지만, 인접 친구도 없고 비어있는 칸도 없는 경우에는 그냥 넣어줘야한다. 때문에 마지막에 else문에 그 경우에도 예외처리를 해준다. 하지만 이 경우에는 pos.clear()를 해주면 안된다. 그러하면 예제에서 4를 배치시킬때
  000
  040
  000
  이 아닌
  000
  000
  004
  가 된다. 그 이유는 clear시켜서 마지막으로 위치가 표시되기 때문이다. clear를 시키지 않아야 제일 강력한 후보자를 지우지 않을 수 있다.

그래도 이번 문제로 골드 3을 찍었다... 하지만 실력은 골드 3이 아니지 짭골드다.