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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

 

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

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

 

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

 

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

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

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

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

 

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

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

 

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

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

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int arr[1111][1111], r,c,t;
  4. int dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
  5.  
  6. void rotate(int y, int x, int y_dir){
  7. arr[y+y_dir][x] = 0;
  8.  
  9. for(int i=y+y_dir; i != (y_dir == -1 ? 0 : r-1); i += y_dir){
  10. arr[i][x] = arr[i+y_dir][x];
  11. }
  12.  
  13. int y_ = y_dir == -1 ? 0 : r-1;
  14. for(int i=0; i<c-1; i++){
  15. arr[y_][i] = arr[y_][i+1];
  16. }
  17.  
  18. for(int i=y_; i != y; i-= y_dir){
  19. arr[i][c-1] = arr[i-y_dir][c-1];
  20. }
  21.  
  22. for(int i=c-1; i-1>0; i--){
  23. arr[y][i] = arr[y][i-1];
  24. arr[y][i-1] = 0;
  25. }
  26. }
  27.  
  28. void spread(){
  29. int new_arr[1111][1111] = {0};
  30. memcpy(new_arr, arr, sizeof(arr));
  31. for(int i=0; i<r; i++){
  32. for(int j=0; j<c; j++){
  33. if(arr[i][j] >= 5){
  34. int cnt = 0;
  35. for(int d=0; d<4;d++){
  36. int ny = i+dy[d], nx = j+dx[d];
  37. if(ny>=0 && ny< r&& nx>=0 && nx< c && arr[ny][nx] != -1){
  38. cnt+=1;
  39. new_arr[ny][nx] += arr[i][j]/5;
  40. }
  41. }
  42. new_arr[i][j] -= arr[i][j]/5 * cnt;
  43. }
  44. }
  45. }
  46. memcpy(arr, new_arr, sizeof(arr));
  47. }
  48. int main(){
  49. int src_y = -1;
  50. scanf("%d%d%d", &r,&c,&t);
  51.  
  52. for(int i=0;i<r;i++){
  53. for(int j=0; j<c; j++){
  54. scanf("%d", &arr[i][j]);
  55. }
  56. if(arr[i][0] == -1 && src_y == -1)
  57. src_y = i;
  58. }
  59.  
  60. for(int i=0; i<t; i++){
  61. spread();
  62. rotate(src_y, 0, -1);
  63. rotate(src_y+1, 0, 1);
  64. }
  65. int ans= 0;
  66. for(int i=0;i<r;i++){
  67. for(int j=0; j<c;j++){
  68. ans += arr[i][j];
  69. }
  70. }
  71.  
  72. printf("%d\n", ans+2);
  73. return 0;
  74. }
  75.  

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

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

 

14891번: 톱니바퀴

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터

www.acmicpc.net

 

위 문제는 시뮬레이션 문제로 자성을 가진 톱니바퀴의 극에 따라 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의 역할은 현재 회전한 톱니바퀴의 다음(왼쪽 / 오른쪽) 톱니바퀴의 회전여부를 검사하고, 만약 회전할 경우 그 다음 톱니바퀴로 전파한다.

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #define LEFT_T 6 // 왼쪽 톱니바퀴 index
  6. #define RIGHT_T 2 // 오른쪽 톱니바퀴 index
  7. using namespace std;
  8. int k;
  9. vector< vector<int> >t(4);
  10.  
  11. void left(vector<int>& v){
  12. rotate(v.begin(), v.begin()+1, v.end());
  13. }
  14.  
  15. void right(vector<int>& v){
  16. rotate(v.rbegin(), v.rbegin()+1, v.rend());
  17. }
  18.  
  19. void rotate(vector<int>& v, int t_dir){
  20. if(t_dir == 1) right(v);
  21. else left(v);
  22. }
  23.  
  24. void propagate(int prev_idx, int t_dir, int prop_dir){
  25. // prev_idx : 회전을 전파한 톱니바퀴
  26. // t_dir : 이전 톱니바퀴가 회전한 방향
  27. // prop_dir : propagation의 방향
  28.  
  29. int cur_t = prev_idx + prop_dir;
  30. if(cur_t < 0 || cur_t > 3) return;
  31.  
  32. int prev_tl = t[prev_idx][LEFT_T], prev_tr = t[prev_idx][RIGHT_T];
  33. int cur_tl = t[cur_t][LEFT_T], cur_tr = t[cur_t][RIGHT_T];
  34.  
  35. if(prop_dir == -1){ //left propagation
  36. if(cur_tr != prev_tl){
  37. propagate(cur_t, -t_dir, prop_dir);
  38. } else return;
  39. } else {
  40. if(prev_tr != cur_tl){ // right propagation
  41. propagate(cur_t, -t_dir, prop_dir);
  42. } else return;
  43. }
  44. rotate(t[cur_t], -t_dir);
  45. }
  46.  
  47. int main(){
  48. for(int i=0;i<4;i++){
  49. for(int j=0; j<8; j++){
  50. int m;
  51. scanf("%1d", &m);
  52. t[i].push_back(m);
  53. }
  54. }
  55. scanf("%d", &k);
  56. for(int i=0; i<k; i++){
  57. int cur_t, rot;
  58. scanf("%d%d", &cur_t, &rot);
  59. cur_t -= 1;
  60.  
  61. // 왼쪽 전파
  62. propagate(cur_t, rot, -1);
  63. // 오픈쪽 전파
  64. propagate(cur_t, rot, 1);
  65.  
  66. // 현재 톱니바퀴 회전
  67. rotate(t[cur_t], rot);
  68. }
  69.  
  70. int ans = 0;
  71. for(int i=0;i<4;i++){
  72. ans += t[i][0] << i;
  73. }
  74. printf("%d\n",ans);
  75. return 0;
  76. }
  77.  

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

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

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

 

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

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

 

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

 

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

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



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

신경쓰도록 하자.

 

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

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

 

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

 

소스코드

 

  1. #include<stdio.h>
  2. int n,m,src_y, src_x, src_d, arr[55][55];
  3. int dy[4] = {-1,0,1,0}, dx[4] = {0, 1, 0, -1};
  4. int visited[55][55], ans;
  5.  
  6. int turn_left(int d){
  7. return d-1 >= 0 ? d-1 : 3;
  8. }
  9. int solve(int y,int x, int d){
  10. visited[y][x] = 1; // num 1
  11.  
  12. int clean = 0;
  13. for(int i = 0; i < 4; i++){ // num 2
  14. int left = turn_left(d);
  15. int ny = y + dy[left], nx = x + dx[left];
  16. if(!arr[ny][nx] && !visited[ny][nx] && ny >=0 && nx >=0 && nx < m && ny < n){
  17. d = left;
  18. if(solve(ny, nx, d) == -1) return -1;
  19. clean = 1;
  20. } else
  21. d = left;
  22. }
  23. if(!clean){
  24. int ny = y-dy[d], nx= x-dx[d];
  25. if(!arr[ny][nx] && ny >= 0 && nx >= 0 && nx < m && ny < n){
  26. if(solve(ny, nx, d) == -1) return -1;
  27. } else {
  28. return -1;
  29. }
  30. }
  31. return 0;
  32. }
  33. int main(){
  34. scanf("%d%d %d %d %d",&n,&m,&src_y, &src_x, &src_d);
  35. for(int i=0;i<n;i++){
  36. for(int j=0;j<m;j++){
  37. scanf("%d", &arr[i][j]);
  38. }
  39. }
  40.  
  41. solve(src_y, src_x, src_d);
  42.  
  43. for(int i=0; i < n; i++){
  44. for(int j=0; j < m; j++){
  45. ans += visited[i][j];
  46. }
  47. }
  48. printf("%d\n", ans);
  49. return 0;
  50. }

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

+ Recent posts