[삼성 기출] 백준 23290번 마법사 상어와 복제 풀이

| |
백준 온라인 저지 23290번 - 마법사 상어와 복제 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다.

격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.

  1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
  2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
  3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
  4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
  5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다. 격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.


입력

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향은 8 이하의 자연수로 표현하고, 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 마지막 줄에는 sx, sy가 주어지며, 상어가 (sx, sy)에 있음을 의미한다.

격자 위에 있는 물고기의 수가 항상 1,000,000 이하인 입력만 주어진다.


출력

S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.


제한

  • 1 ≤ M ≤ 10
  • 1 ≤ S ≤ 100
  • 1 ≤ fx, fy, sx, sy ≤ 4
  • 1 ≤ d ≤ 8
  • 두 물고기 또는 물고기와 상어가 같은 칸에 있을 수도 있다.


노트

상어의 이동 방법 중 사전 순으로 가장 앞서는 방법을 찾으려면 먼저, 방향을 정수로 변환해야 한다. 상은 1, 좌는 2, 하는 3, 우는 4로 변환한다. 변환을 모두 마쳤으면, 수를 이어 붙여 정수로 하나 만든다. 두 방법 A와 B가 있고, 각각을 정수로 변환한 값을 a와 b라고 하자. a < b를 만족하면 A가 B보다 사전 순으로 앞선 것이다.

예를 들어, [상, 하, 좌]를 정수로 변환하면 132가 되고, [하, 우, 하]를 변환하면 343이 된다. 132 < 343이기 때문에, [상, 하, 좌]가 [하, 우, 하]보다 사전 순으로 앞선다.

총 43 = 64가지 방법을 사전 순으로 나열해보면 [상, 상, 상], [상, 상, 좌], [상, 상, 하], [상, 상, 우], [상, 좌, 상], [상, 좌, 좌], [상, 좌, 하], [상, 좌, 우], [상, 하, 상], …, [우, 하, 하], [우, 하, 우], [우, 우, 상], [우, 우, 좌], [우, 우, 하], [우, 우, 우] 이다.


풀이

약간의 완전 탐색이 가미된 구현 및 시뮬레이션 문제이다. 이 문제의 핵심은 문제를 정말 꼼꼼히 읽고 주어진 조건을 완벽히 파악하는 것이다. 필자는 본 문제에서 상당한 삽질을 했고 놓쳤던 부분은 다음과 같이 3가지이다.

물고기와 냄새를 같은 배열에 저장하려 했다

문제에서 물고기가 사라지고 그 자리에 물고기의 냄새가 남는다는 문구를 보고 물고기와 냄새를 같은 구조체로 두고 단지 물고기인지 냄새인지 구분하는 값을 넣어주려 했다. 하지만 문제를 푸는 도중에 하나의 좌표에서 물고기와 냄새를 구분하고 제거해야 하는 작업이 빈번했다. 따라서 이러한 구현 방식은 최적화에 굉장히 불리했고 구현도 까다로웠다.

물고기만 저장하는 배열과 냄새를 따로 두어야 구현적인 면과 성능적인 면에서 이득을 볼 수 있다. 물고기 배열의 경우에는 물고기의 방향을 나타내는 정수를 넣고, 냄새의 경우에는 남은 지속 시간을 정수로 넣어주고 매 턴마다 1씩 감소시켜주면 된다. 이처럼 두 배열 모두 정수형 벡터로 표현이 가능하다.

이미 방문했던 칸을 다시 방문하는 경우가 상어의 최적 경로일 수 있다

상어의 최적 이동 경로를 구하는 과정에서 논리적 오류가 있었다. 이미 물고기를 먹어치운 칸이라고 하더라도 더 이상 먹을 물고기가 없어 사전 순으로 가장 앞서는 경로로 움직이기 위해 어쩔 수 없이 다시 방문하는 경우가 있다. 그리고 이렇게 같은 칸을 두 번째 방문할 시에는 이미 물고기를 먹어치운 상태이므로 물고기의 개수는 카운트하면 안된다. 따라서 이미 방문할 칸을 다시 방문할 수는 있으나, 각 칸마다의 방문 여부 또한 저장해두고 이에 대한 처리를 해주어야 한다.

그리고 사전 순으로 가장 앞서는 경로를 찾는 가장 단순한 방법은, 문제에서 제시해준 사전 순인 [상, 좌, 하, 우] 순으로 경로를 탐색해주는 것이다. 이렇게 하면 먼저 탐색한 경로일 수록 사전 순으로도 앞서는 경로이므로, 추가적인 사전 순 비교없이 경로를 갱신할 수 있다. 필자는 본 사전 순 조건을 상좌하우가 아닌 상하좌우로 잘못 읽어서 삽질을 거듭해야 했다. 구현 문제는 정말 문제를 꼼꼼히 읽는 것이 반이다.

그리고 필자가 또 실수했던 부분은 상어가 방문한 모든 칸에 대하여 냄새를 남기게 한 것이다. 얼핏보면 문제가 없는 것처럼 보이지만 냄새는 물고기가 있었던 칸에 대해서만 생긴다. 따라서 이에 대한 조건문도 붙여줘야 한다.

또 물고기가 있었던 칸에 대하여 냄새를 발생시킬 때, 지속 시간을 2가 아닌 3으로 초기화해주어야 한다. 바로 다음 과정에서 모든 칸에 대한 냄새의 지속 시간을 1 감소시키기 때문이다. 이는 구현에 따라 차이가 있겠지만, 아마 본 방법이 가장 직관적일 것이다.


문제 자체가 신경써야할 조건과 구현량이 많으므로 조금만 집중을 놓치면 필자처럼 삽질의 굴레에 빠질 수 있다. 따라서 문제를 처음 읽을 때 정확하고 꼼꼼히 파악하고, 이를 코드를 써내려가는 내내 계속 염두해야한다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int M,S;
int sy,sx;
int dy[] = {0,-1,-1,-1,0,1,1,1};
int dx[] = {-1,-1,0,1,1,1,0,-1};
int rdy[] = {-1,0,1,0};
int rdx[] = {0,-1,0,1};

vector<int> board[4][4];
vector<int> copied[4][4];
int smell[4][4];

int routeCnt=-1;
string routeLog;
bool visited[4][4];

bool inRange(int y, int x) {
    return 0<=y && y<4 && 0<=x && x<4;
}

void findRoutes(int y, int x, string log, int cnt) {
    if(log.length() == 3) {
        if(cnt > routeCnt) {
            routeCnt = cnt;
            routeLog = log;
        }
        return;
    }
    for(int i=0;i<4;i++) {
        int ny = y+rdy[i];
        int nx = x+rdx[i];
        if(!inRange(ny,nx)) continue;
        if(visited[ny][nx]) findRoutes(ny,nx,log+to_string(i),cnt);
        else {
            visited[ny][nx] = true;
            findRoutes(ny,nx,log+to_string(i),cnt+board[ny][nx].size());
            visited[ny][nx] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>M>>S;
    while(M--) {
        int y,x,d;
        cin>>y>>x>>d;
        board[y-1][x-1].push_back(d-1);
    }
    cin>>sy>>sx; sy--; sx--;

    while(S--) {
        // copy board
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++){
                copied[i][j]=board[i][j];
                board[i][j].clear();
            }
        
        // move fishes
        for(int i=0;i<4;i++) {
            for(int j=0;j<4;j++) {
                for(int f:copied[i][j]) {
                    int d = f;
                    int ny = i+dy[d];
                    int nx = j+dx[d];
                    while(!inRange(ny,nx) || smell[ny][nx] > 0 || ny==sy&&nx==sx) {
                        d--;
                        if(d==-1) d=7;
                        if(d==f) break;
                        ny = i+dy[d];
                        nx = j+dx[d];
                    }
                    if(inRange(ny,nx) && smell[ny][nx] <= 0 && (ny!=sy||nx!=sx))
                        board[ny][nx].push_back(d);
                    else
                        board[i][j].push_back(f);
                }
            }
        }

        // find optimal route of shark
        routeCnt = -1;
        memset(visited,0,sizeof(visited));
        findRoutes(sy,sx,"",0);

        // move shark through optimal route
        for(char c:routeLog) {
            int d = c-'0';
            
            sy+=rdy[d]; sx+=rdx[d];
            
            if(!board[sy][sx].empty()) {
                board[sy][sx].clear();
                smell[sy][sx] = 3;
            }
            
        }

        // remove smell which left for 2 times
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                smell[i][j]--;

        // copy fishes
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                for(int& f:copied[i][j])
                    board[i][j].push_back(f);
    }

    // count answer (number of fishes)
    int ans = 0;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            ans += board[i][j].size();
    
    cout<<ans;

    return 0;
}
0%