uang's blog

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

요즘은 시뮬레이션 문제 푸는게 재밌는 것 같다..

복잡한 알고리즘 고민없이 코딩할 수 있어서 그런가,,

마냥 구현만 하면 풀 수 있는 문제들이라 아무 생각없이 풀 수 있어 좋은 것 같다(생각없이 풀다보니 코드는 개판이 된다)

미세먼지 안녕! 문제는 1) 확산 2) 공기 순환을 구현하면 풀 수 있다.

확산에서 중요한 점은 확산 전 원본 배열을 기준으로 계산을 쭉 진행해야 하기 때문에, 새로운 배열이 필요하다.

나는 memcpy를 이용해 새로운 배열을 만들었고, O(n*2), n 이 1000 이하라 시간안에는 돌아가지만,

예전에 어떤 문제를 풀면서 memcpy가 상당히 느리다는 것을 알았다.. 직접 for문 돌린게 더 빨랐던 것 같기도

공기 순환은 rotate 라는 이름(함수 이름 짓기가 젤 어렵다)으로 구현했는데, 사실 실수가 많이 발생할 법한 구현이다.

left, right, up, down 으로 각각 쪼개서 구현해서, 시계방향은 down -> right -> up -> left 순서로 덮어써가고,
반시계방향은  up -> right -> down -> left 순서로 덮어써가면 실수를 줄일 수 있을 것 같다.

시뮬레이션 문제의 핵심은 구현 중 발생할 수 있는 실수를 최대한 줄이는게 핵심일 것 같다..

사실 좋은 코드는 실무에서 굉장히 중요하지만, 알고리즘을 풀면서 코드의 질이 크게 중요한 가 싶다 (변명 아님..)

소스코드

#include<stdio.h>
#include<string.h>
int arr[1111][1111], r,c,t;
int dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
 
void rotate(int y, int x, int y_dir){
  arr[y+y_dir][x] = 0;
 
  for(int i=y+y_dir; i != (y_dir == -1 ? 0 : r-1); i += y_dir){
    arr[i][x] = arr[i+y_dir][x];
  }
 
  int y_ = y_dir == -1 ? 0 : r-1;
  for(int i=0; i<c-1; i++){
    arr[y_][i] = arr[y_][i+1];
  }
 
  for(int i=y_; i != y; i-= y_dir){
    arr[i][c-1] = arr[i-y_dir][c-1];
  }
 
  for(int i=c-1; i-1>0; i--){
    arr[y][i] = arr[y][i-1];
    arr[y][i-1] = 0;
  }
}
 
void spread(){
  int new_arr[1111][1111] = {0};
  memcpy(new_arr, arr, sizeof(arr));
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      if(arr[i][j] >= 5){
        int cnt = 0;
        for(int d=0; d<4;d++){
          int ny = i+dy[d], nx = j+dx[d];
          if(ny>=0 && ny< r&& nx>=0 && nx< c && arr[ny][nx] != -1){
            cnt+=1;
            new_arr[ny][nx] += arr[i][j]/5;
          }
        }
        new_arr[i][j] -= arr[i][j]/5 * cnt;
      }
    }
  }
  memcpy(arr, new_arr, sizeof(arr));
}
int main(){
  int src_y = -1;
  scanf("%d%d%d", &r,&c,&t);
 
  for(int i=0;i<r;i++){
    for(int j=0; j<c; j++){
      scanf("%d", &arr[i][j]);
    }
    if(arr[i][0] == -1 && src_y == -1)
      src_y = i;
  }
 
  for(int i=0; i<t; i++){
    spread();
    rotate(src_y, 0, -1);
    rotate(src_y+1, 0, 1);
  }
  int ans= 0;
  for(int i=0;i<r;i++){
    for(int j=0; j<c;j++){
      ans += arr[i][j];
    }
  }
 
  printf("%d\n", ans+2);
  return 0;
}
 

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

위 문제는 시뮬레이션 문제로 자성을 가진 톱니바퀴의 극에 따라 k번 회전 시켰을 때,

톱니바퀴의 변화를 잘 구현해야하는 문제이다.

톱니바퀴는 다음과 같이 반시계방향 / 시계방향으로 회전할 수 있다.

톱니바퀴의 수는 다음과 같이 4개로 고정돼 있다. 그리고 맞닿아 있는 극이 다를 경우 회전이 영향받는다. 즉, 만약 1 번 톱니바퀴가 반시계방향으로 회전하는 경우 2번째 톱니바퀴의 맞닿아 있는 극이 서로 다르므로, 2번 째 톱니바퀴는 반대방향인 시계방향으로 회전한다. 그리고 2번 톱니바퀴와 3번 톱니바퀴의 맞닿아 있는 극은 같기 때문에 2번이 회전할 때 3번 톱니바퀴는 회전하지 않는다.

그럼 문제는 이해했고, 회전을 어떻게 구현할까.

CPP 에는 rotate 라는 함수를 지원한다. 입력에서 8개의 정수로 N,S 극을 표현하기 때문에, 회전 시 rotate함수로 배열을 적절히 회전시킬 수 있다. 만약 rotate를 사용하지 않는다면, 각 톱니바퀴의 현재 left / right 의 극 index를 저장하는 방법이 있겠다. 

개인적으로 시뮬레이션 문제를 풀 때는 직관적인 것이 풀기 편해 rotate를 사용했다.

# rotate 사용법

#include <vector>
#include <iostream>
#include <algorithm>
 
auto print = [](auto const& remark, auto const& v) {
    std::cout << remark;
    for (int n: v)
        std::cout << n << ' ';
    std::cout << '\n';
};
 
int main()
{
    std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
 
    print("before sort:\t\t", v);
 
    // insertion sort
    for (auto i = v.begin(); i != v.end(); ++i) {
        std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
    }
 
    print("after sort:\t\t", v);
 
    // simple rotation to the left
    std::rotate(v.begin(), v.begin() + 1, v.end());
 
    print("simple rotate left:\t", v);
 
    // simple rotation to the right
    std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
 
    print("simple rotate right:\t", v);
}

Output :

before sort:            2 4 2 0 5 10 7 3 7 1 
after sort:             0 1 2 2 3 4 5 7 7 10 
simple rotate left:     1 2 2 3 4 5 7 7 10 0 
simple rotate right:    0 1 2 2 3 4 5 7 7 10

k 번 톱니바퀴를 회전 시키는데, 각 회전마다 왼쪽 / 오른쪽 회전이 전파돼야 한다. 

전파를 위해 propagate 함수를 정의 했다. propagate의 역할은 현재 회전한 톱니바퀴의 다음(왼쪽 / 오른쪽) 톱니바퀴의 회전여부를 검사하고, 만약 회전할 경우 그 다음 톱니바퀴로 전파한다.

소스코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define LEFT_T 6 // 왼쪽 톱니바퀴 index
#define RIGHT_T 2 // 오른쪽 톱니바퀴 index
using namespace std;
int k;
vector< vector<int> >t(4);
 
void left(vector<int>& v){
  rotate(v.begin(), v.begin()+1, v.end());
}
 
void right(vector<int>& v){
  rotate(v.rbegin(), v.rbegin()+1, v.rend());
}
 
void rotate(vector<int>& v, int t_dir){
  if(t_dir == 1) right(v);
  else left(v);
}
 
void propagate(int prev_idx, int t_dir, int prop_dir){
  // prev_idx : 회전을 전파한 톱니바퀴
  // t_dir : 이전 톱니바퀴가 회전한 방향
  // prop_dir : propagation의 방향
 
  int cur_t = prev_idx + prop_dir;
  if(cur_t < 0 || cur_t > 3) return;
 
  int prev_tl = t[prev_idx][LEFT_T], prev_tr = t[prev_idx][RIGHT_T];
  int cur_tl = t[cur_t][LEFT_T], cur_tr = t[cur_t][RIGHT_T];
 
  if(prop_dir == -1){ //left propagation
    if(cur_tr != prev_tl){
      propagate(cur_t, -t_dir, prop_dir);
    } else return;
  } else {
    if(prev_tr != cur_tl){ // right propagation
      propagate(cur_t, -t_dir, prop_dir);
    } else return;
  }
  rotate(t[cur_t], -t_dir);
}
 
int main(){
  for(int i=0;i<4;i++){
    for(int j=0; j<8; j++){
      int m;
      scanf("%1d", &m);
      t[i].push_back(m);
    }
  }
  scanf("%d", &k);
  for(int i=0; i<k; i++){
    int cur_t, rot;
    scanf("%d%d", &cur_t, &rot);
    cur_t -= 1;
 
    // 왼쪽 전파
    propagate(cur_t, rot, -1);
    // 오픈쪽 전파
    propagate(cur_t, rot, 1);
 
    // 현재 톱니바퀴 회전
    rotate(t[cur_t], rot);
  }
 
  int ans = 0;
  for(int i=0;i<4;i++){
    ans += t[i][0] << i;
  }
  printf("%d\n",ans);
  return 0;
}
 

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

위 문제는 시뮬레이션 문제이며, 구현만 잘 하면 쉽게 풀 수 있다.

시뮬레이션 문제를 푸는 것에 있어 가장 중요한 점은 동작과정을 정확히 이해하고, 그대로 구현해야 한다는 점인 것 같다.

위 로봇 청소기 문제는 동작은 간단하지만 현재 바라보고 있는 방향이 가장 중요하다.

2번 째 행동이 a, b, c, d 4가지 경우가 있는데, 크게 a,b 와 c,d 로 묶을 수 있을 것 같다.

a,b 는 왼쪽 방향으로 돌아가며 순차적으로 탐색해나가는 과정의 조건이고, c,d는 4방향을 모두 탐색한 후의 행동이다.



시뮬레이션 문제에서 동작은 하나씩 모두 잘게 쪼개는 것이 중요하다. 이 문제에서는 현재 바라보는 방향이 가장 중요하므로, 

신경쓰도록 하자.

직접 동작을 쪼개보면 알겠지만, 로봇이 c 조건에 부합돼 후진해야 할 때 현재 바라보는 방향은 처음 진입한 방향의 오른쪽 방향이다. 로봇은 현재 바라보는 방향에서 왼쪽 방향을 탐색하기 때문에 4방향 모두 탐색하는 시점은 3번 회전한 뒤이다.

(처음 북쪽을 봤다면 : 서쪽탐색 후 왼쪽 회전 ->  남쪽 탐색 후 왼쪽 회전 -> 동쪽 탐색 후 왼쪽 회전 -> 북쪽 탐색하면 4방향 모두 탐색조건 부합하므로 현재 방향은 동쪽)

d 조건에 부합되는 순간 모든 탐색과정이 종료해야 한다.

소스코드

#include<stdio.h>
int n,m,src_y, src_x, src_d, arr[55][55];
int dy[4] = {-1,0,1,0}, dx[4] = {0, 1, 0, -1};
int visited[55][55], ans;
 
int turn_left(int d){
  return d-1 >= 0 ? d-1 : 3;
}
int solve(int y,int x, int d){
  visited[y][x] = 1; // num 1
 
  int clean = 0;
  for(int i = 0; i < 4; i++){ // num 2
    int left = turn_left(d);
    int ny = y + dy[left], nx = x + dx[left];
    if(!arr[ny][nx] && !visited[ny][nx] && ny >=0 && nx >=0 && nx < m && ny < n){
      d = left;
      if(solve(ny, nx, d) == -1) return -1;
      clean = 1;
    } else
      d = left;
  }
  if(!clean){
    int ny = y-dy[d], nx= x-dx[d];
    if(!arr[ny][nx] && ny >= 0 && nx >= 0 && nx < m && ny < n){
      if(solve(ny, nx, d) == -1) return -1;
    } else {
      return -1;
    }
  }
  return 0;
}
int main(){
  scanf("%d%d %d %d %d",&n,&m,&src_y, &src_x, &src_d);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      scanf("%d", &arr[i][j]);
    }
  }
 
  solve(src_y, src_x, src_d);
 
  for(int i=0; i < n; i++){
    for(int j=0; j < m; j++){
      ans += visited[i][j];
    }
  }
  printf("%d\n", ans);
  return 0;
}