[C++] 백준 21610 : 마법사 상어와 비바라기

#include <iostream>
#include <vector>
#include <queue> // 구름 위치
#include <utility> //pair
using namespace std;

int N, M; // 맵 크기, 이동 수
int map[51][51]; // 맵
int di, si; // 이동 정보 - 방향, 거리

queue<pair<int, int>> q; // r, c

// 방향 : ←, ↖, ↑, ↗, →, ↘, ↓, ↙
int dx[9] = {99, -1, -1, 0, 1, 1, 1, 0, -1};
int dy[9] = {99, 0, -1, -1, -1, 0, 1, 1, 1};

int main(){
  scanf("%d %d", &N, &M); // 맵 크기, 구름 이동 수

  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      scanf("%d", &map[i][j]); // 맵 입력 받기
    }
  }
  
  // 처음 비바라기 구름 위치 넣기
  q.push({N, 1});
  q.push({N, 2});
  q.push({N-1, 1});
  q.push({N-1, 2});

  for(int i = 0; i < M; i++){ // while(M--) 가 더 편해보이는군
    bool visited[51][51] = {false}; // 구름 체크
    vector<pair<int, int>> v; // 구름 좌표

    scanf("%d %d", &di, &si); // 이동 정보 입력받기

    int size = q.size(); // 큐 크기

    for(int j = 0; j < size; j++){
      // 좌표 꺼내기
      int r = q.front().first;
      int c = q.front().second;

      // 3. 구름이 모두 사라진다.
      q.pop();

      //1. 모든 구름 이동
      for(int k = 0; k < si; k++){
        r += dy[di];
        c += dx[di];

        // 범위 넘어갈 때
        if(r < 1){
          r = N;
        }
        if(r > N){
          r = 1;
        }
        if(c < 1){
          c = N;
        }
        if(c > N){
          c = 1;
        }
      }
      
      //2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
      map[r][c]++;
      visited[r][c] = true; // 구름 있는 칸 체크
      v.push_back({r, c}); // 구름 좌표 재저장
    }

    //4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전
    for(int j = 0; j < size; j++){
      int r = v[j].first;
      int c = v[j].second;
      // 대각선 2, 4, 6, 8 방향
      for(int k = 2; k <= 9; k += 2){
        // 대각선 위치 체크
        int nr = r + dy[k];
        int nc = c + dx[k];
        
        // 범위 벗어나지 않고 대각선 방향 물이 있는 경우
        if(nr <= N && nc <= N && nr >= 1 && nc >= 1 && map[nr][nc]){
          map[r][c]++;
        }
      }
    }

    //5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름
    for(int j = 1; j <= N; j++){
      for(int k = 1; k <= N; k++){
        //구름이 있었던 칸 제외
        if(map[j][k] >= 2 && !visited[j][k]){
          // 구름 생성
          q.push({j, k});
          map[j][k] -= 2; //구름 생기면 물의 양 2만큼 감소
        } else {
        }
      }
    }
  }
  
  int cnt = 0;
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      if(map[i][j] > 0){
        cnt += map[i][j];
      }
    }
  }

  printf("%d", cnt);
  return 0;
}

나에게 남은 시간 수, 목, 금, 토... 과연 삼성 마스터가 될 수 있을까...ㅠㅠ 제발 이런 문제 나왔으면 좋겠다.

방향 헷갈리지 말기 우리가 생각하는 가로는 x가 아니라 y이고 (0, 0)이 좌측 상단이기 때문에 -와 +가 반대이다. print해서 좌표 찍어보기가 제일 정확하다.

2번째 풀이

#include <iostream>
#include <queue> // vector? queue? 구름 저장
#include <cstring> // memset

using namespace std;

int N, M;
int A[51][101];
bool visited[51][101] = {false};
int r, c; // r 행 c 열 - 너무 헷갈리게 문제에 써 둠
int d, s; // d 방향 s 칸

int ans = 0;

// ←, ↖, ↑, ↗, →, ↘, ↓, ↙
int dx[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dy[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};

struct INFO{
  int r; // 구름 좌표
  int c;
};

queue<INFO> q; // 비구름 저장

// 모든 구름이 di 방향으로 si칸 이동
void move(){
  memset(visited, false, sizeof(visited)); // 구름 초기화

  while(!q.empty()){
    int r = q.front().r;
    int c = q.front().c;
    q.pop(); // 구름이 모두 사라진다.

    // 구름 d방향으로 s만큼 이동
    for(int i = 0; i < s; i++){
      r += dy[d];
      c += dx[d];

      if(r < 1){
        r = N;
      }
      if(c < 1){
        c = N;
      }
      if(r > N){
        r = 1;
      }
      if(c > N){
        c = 1;
      }
    }

    // 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가
    A[r][c]++;
    visited[r][c] = true; // 구름 이동한 곳
  }

  // 물이 증가한 칸일 경우 - 물복사마법
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      if(visited[i][j]){
        // 대각선 방향으로 거리가 1인 칸 - 2, 4, 6, 8
        for(int k = 2; k <= 9; k+=2){
          int nny = i + dy[k];
          int nnx = j + dx[k];

          // 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다
          if(nnx < 1 || nny < 1 || nnx > N || nny > N){
            continue;
          }
          
          // 대각선에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가
          if(A[nny][nnx]){
            A[i][j]++; // cnt 변수 쓸 필요 없음 굳이?
          }
        }
      }
    }
  }

  // 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      if(A[i][j] >= 2 && !visited[i][j]){
        q.push({i, j});
        A[i][j] -= 2;
      }
    }
  }
}

int main(){
  scanf("%d %d", &N, &M);

  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      scanf("%d", &A[i][j]);
    }
  }

  // 비구름 생성 - Y, X
  q.push({N, 1});
  q.push({N, 2});
  q.push({N-1, 1});
  q.push({N-1, 2});

  for(int i = 0; i < M; i++){
    scanf("%d %d", &d, &s);
    move();
  }

  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      ans += A[i][j];
    }
  }

  printf("%d", ans);

  return 0;
}

다른 사람의 코드를 참고하지 않고 혼자 푼 문제.
(N, 1)에 기본적으로 생성하는 구름이

이 위치에 생성되기 때문에 통념적인 좌표와 달라서 너무 헷갈린다 (1, N)으로 봐야함. 아니면 x랑 y 바꿔서 생각하던가