[삼성기출/C++] 메두사와 전사들

삼성 공채 시즌이 다시 한 번 돌아왔습니다. 모두 화이팅입니다. 그럼 달려봐야겠죠.. 

알고리즘 분류

• 너비 우선 탐색 (BFS)
• 깊이 우선 탐색 (DFS)
• 기하 (Gemometry)
• 시뮬레이션

 

문제 설명

문제가 너무 길어서 사이트를 참고하자.

https://www.codetree.ai/ko/frequent-problems/problems/medusa-and-warriors/description?introductionSetId=&bookmarkId=

삼성 코딩테스트 기출 문제 설명: 메두사와 전사들 | 코드트리

 

문제 접근

삼성기출은, 일반적인 코딩 테스트의 "원리"가 통하지 않는다. 일반적인 코딩 테스트 및 알고리즘 대회에서는 다음 원리가 성립한다.

• 함수는 최대한 적게 사용한다. 아무리 많아도 3개를 넘지 않는다.
• 함수명, 변수명은 최대한 간결하게, 타자 치는 시간이 아깝다

하지만 이런 방식으로 삼성 기출을 푸는 것은 매우 어렵다. 구현의 난이도가 너무 복잡하고, 문제 여기저기에 "함정"들이 산적해있기 때문에, 일반적인 코딩 테스트라기보다는 "개발 테스트" 라고 보는 것이 적절하다. 따라서, 일반적인 클린 코드의 원칙을 도입해야 한다.

• 3중 for문 이상은 절대 사용하지 않고, 함수로 넘긴다.
• 함수 하나에서는 되도록 한 가지 일만 수행한다.
• 변수명과 함수명은 보면 어떤 역할인지 이해할 수 있도록 작성한다.
• 그 밖에도 코드를 최대한 가독성 있게 작성하고, 중요하거나 헷갈리는 로직은 주석을 작성한다.

문제를 보면 총 4가지의 단계로 나뉘는 것을 볼 수 있다.

1. 메두사의 이동
2. 메두사의 시선
3. 전사들의 이동
4. 전사들의 공격

여기에서 전사들이 공격하는 것은 전사들의 이동 직후에 이루어지므로 그냥 3,4단계는 합쳐서 생각하자.

1. 메두사의 이동

메두사는 road를 통해서만 이동할 수 있으므로, BFS를 통해 최단 거리를 구하면 된다. 그런데 굉장히 짜증나는 조건이 따라붙었다.

여러 최단 경로가 가능하다면 상, 하, 좌, 우의 우선순위를 따른다.. 즉 이런 내용이다. 만약 다음 그림에서 최단 경로 상 -> 상-> 우 -> 우 이다. 즉 Trace를 해야 한다.

OK. 그럼 시작점을 중심으로 BFS를 하고 상->하->좌->우 순으로 trace를 하면 되겠다! 라고 생각할 수도 있지만, 시작점 중심으로 BFS를 할 경우, 다음과 같은 결과가 생긴다. 

나머지 경로도 일일이 찾아보면서 distance가 4일때 끝 지점에 도달했는지!! 를 찾아야 한다. 따라서 이를 해결하기 위해서는, 반대로 "목적지" 중심으로 BFS를 짜야 한다.

이 경우에는 시작부분에서 "상" 또는 "우" 방향이 distance가 짧으므로(3) 나아갈 수 있고, 이 경로를 따라가면 목적지에 도달함이 보장되어 있다. 모든 길이 목적지에서 시작했으므로, 그 반대로 추적하면 당연히 목적지에 도달할 수 있기 때문이다. 따라서 다음과 같다 (1) 목적지를 중심으로 BFS 하고, (2) 상하좌우 순서의 우선순위로 탐색하면 된다.

bool is_out(int y, int x)
{
  return (y < 0 || y >= n || x < 0 || x >= n);
}

int calc_dist()
{
  memset(park_dist, -1, sizeof(park_dist));
  queue <pii> q;
  q.push({py, px});
  park_dist[py][px] = 0;

  while(q.size())
  {
    pii here = q.front(); q.pop();
    int y = here.first;
    int x = here.second;

    if (y == my && x == mx) return park_dist[y][x];
    for (int i = 0; i < 8; i += 2)
    {
      int ny = y + dy[i];
      int nx = x + dx[i];

      if (is_out(ny, nx) || road[ny][nx] == 1) continue;

      if (park_dist[ny][nx] == -1)
      {
        park_dist[ny][nx] = park_dist[y][x] + 1;
        q.push({ny, nx});
      }
    }
  }
  return -1;
}

vector<pii> path;

bool trace(int y, int x) {
  if (y == py && x == px) return true;

  for (int i = 0; i < 4; i++)
  {
    int dir = dirs[i][1];
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    if (is_out(ny, nx) || park_dist[ny][nx] == -1) continue;
    if (park_dist[y][x] == park_dist[ny][nx] + 1)
    {
      path.push_back({ny, nx});
      if (trace(ny, nx)) return true;
      path.pop_back();
    }
  }
  
  return false;
}

 

2. 메두사의 시선

이 문제에서 가장 복잡한 부분이다. 너무 복잡해서, 문제에서 설명한 것으로 부족하고 문제에서 제시하는 그림과 함께 봐야 이해할 수 있다. 우선 상,하,좌,우 순으로 돌면서 전사를 가장 "많이 얼릴 수 있는" 순으로 탐색한다. 이때 전사가 없다고 하면, 탐색 범위는 다음과 같다.

 

그런데 만약 전사가 있다면, 8방향 중 "동일한 방향"에 대해서는 메두사의 시선이 닿질 않는다. 그림으로 보면,

위와 같다. 음... 그러면 메두사의 탐색 범위를 다음과 같이 정의할 수 있겠다.

// 북쪽이 0, 이후 시계방향으로 1,2, ... 7
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};

// (상, 하, 좌, 우) 에 대한 탐색방향
// ex 상(idx == 0) 일 경우 탐색방향은 
// (7, 0, 1) <- (북서, 북, 북동)
vector<vector<int>> dirs = {
  {7, 0, 1},
  {3, 4, 5},
  {7, 6, 5},
  {3, 2, 1}
};

이렇게 dirs는 idx가 0~3 = 상하좌우 이고, 각각의 idx에 대해서는 탐색하는 8방향 중 3가지가 담겼다. 예를 들어 동쪽으로 메두사가 시선을 돌리면, 동북, 동, 동남쪽을 볼 수 있는 것이다.

그러면 중요한 것은, 해당하는 전사가 메두사의 시선에서 "어느 방향"인지 탐색하는 것이다. 이를 위해, 기울기 개념을 도입했다. 기울기를 다음과 같이 정의하자. 전사 = (wy, wx) , 메두사 = (my, mx) 라고 하면,

이를 이용해 기울기를 계산하면 다음과 같다.

이러면 기울기는 다음과 같이 3가지 분류를 할 수 있다.

• 기울기가 양수인 경우 -> 사선 + 직선 형태로 볼 수 있음
• 기울기가 0이거나, 무한대인 경우 -> 직선 형태로만 볼 수 있음
• 기울기가 음수인 경우 -> 사선 + 직선 형태로 볼 수 있음

따라서 각각의 dirs의 vector에 대해 다음 순서로 정의하면, 기울기의 부호에 따라 탐색 범위를 라우팅 할 수 있다. 이 부분을 적절히 구현하는 것이 문제 풀이의 critical path라고 보인다. 그냥 무식하게 하드코딩할 수도 있고, 구현은 사람마다 다를 것이다. 어차피 4시간동안 한 문제만 잘풀면 되는거라..

// (상, 하, 좌, 우) 에 대한 탐색방향
// ex 상(idx == 0) 일 경우 탐색방향은 
// (7, 0, 1) <- (북서, 북, 북동)
vector<vector<int>> dirs = {
  {7, 0, 1}, // 기울기 -> (양수, 0또는 무한대, 음수)
  {3, 4, 5}, // 기울기 -> (양수, 0또는 무한대, 음수)
  {7, 6, 5}, // 기울기 -> (양수, 0또는 무한대, 음수)
  {3, 2, 1}  // 기울기 -> (양수, 0또는 무한대, 음수)
};

이를 이용해, 각각의 탐색범위(상, 하, 좌, 우)에 대하여 BFS를 진행하고, 만약 전사를 만나면 그 다음 범위에 대해서 BFS를 진행해서 시선이 "막히는"부분을 찾아줘야 한다.

int max_freeze_dir;
void medusa_look()
{
  memset(visited, 0, sizeof(visited));
  int max_freeze_cnt = 0;
  for (int i = 0; i < 4; i++)
  {
    vector<int> look_dir = dirs[i];
    queue<pii> q;
    int freeze_cnt = 0;
    q.push({my, mx});
    while(q.size())
    {
      pii here = q.front(); q.pop();
      int y = here.first;
      int x = here.second;
      for (int dir : look_dir)
      {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if (is_out(ny, nx) || visited[i][ny][nx]) continue;
        if (warrior_land[ny][nx])
        {
          freeze_cnt += warrior_land[ny][nx];
          visited[i][ny][nx] = 1;
          // 이중 BFS 구현
          queue<pii> warrior_q;
          vector<int> warrior_dir;
          // 2. 기울기가 0이거나 무한대
          if (ny == my || nx == mx)
          {
            warrior_dir.push_back(look_dir[1]);
          }
          else
          {
            // 1. 기울기가 양수
            if ( (double)(ny - my) / (double)(nx - mx) > 0)
            {
              warrior_dir.push_back(look_dir[0]);
              warrior_dir.push_back(look_dir[1]);
            }
            // 3. 기울기가 음수수
            else
            {
              warrior_dir.push_back(look_dir[1]);
              warrior_dir.push_back(look_dir[2]);
            }
          }
          warrior_q.push({ny, nx});
          while(warrior_q.size())
          { 
            pii here = warrior_q.front(); warrior_q.pop();
            int y = here.first;
            int x = here.second;
            for (int dir : warrior_dir)
            {
              int ny = y + dy[dir];
              int nx = x + dx[dir];
              if (is_out(ny, nx) || visited[i][ny][nx]) continue;
              // 시선이 "막힌" 부분은 100으로 assign
              visited[i][ny][nx] = 100;
              warrior_q.push({ny, nx});
            }
          }
        }
        else
        {
          q.push({ny, nx});
          // 시선이 "닿는" 부분은 1으로 assign
          visited[i][ny][nx] = 1;
        }
      }
    }

    // 최댓값 update
    if (max_freeze_cnt < freeze_cnt)
    {
      max_freeze_cnt = freeze_cnt;
      max_freeze_dir = i;
    }
  }

  // 실제로 얼리기
  for (Warrior& w : warrior_vec)
  {
    if (w.live == 0) continue;
    if (visited[max_freeze_dir][w.y][w.x] == 1)
    {
      w.freeze = 1;
      turn_info.warrior_freezed++;
    }
  }
}

보는 방향이 4개 이므로, 4개의 visited 배열에 BFS를 담고, 각각 탐색하면서 freeze_cnt를 담아준 후 최대값인 경우, 정말로 Freeze해주는 과정을 거친다. 시선이 닿는 부분은 1로, 막히는 부분은 100으로 assign 해서 구별함에 주의하자.

 

3. 전사의 이동 + 전사의 죽음

이 부분은 그나마 간단하다. 하지만 함정이 있는데, 첫 번째 이동과 두 번째 이동의 방향이 다르다는 것이며, 전사는 도로에 상관없이 이동할 수 있다는 것이다.

이 부분만 조심하면서 구현하면 된다.

int man_calc_dist(int y1, int x1, int y2, int x2)
{
  return abs(y1 - y2) + abs(x2 - x1);
}

vector<int> warrior_dir[2] = {
  {0, 4, 6, 2}, // 상 하 좌 우
  {6, 2, 0, 4} // 좌 우 상 하 
};

void warrior_move(int flag)
{
  // cout << "이동시작!!!" << endl;
  // cout << " 메두사는 " << " : " << my << " : " << mx << endl;
  for (Warrior& w : warrior_vec)
  {
    //cout << w.y << " : " << w.x << " : " << w.freeze << " :  " << w.live << endl;
    if (w.live == 0) {
      //cout << w.y << " : " << w.x << " 는 죽음" << endl;
      continue;
    }
    if (w.freeze == 1)
    {
      //cout << w.y << " : " << w.x << " 는 얼어있음" << endl;
      if(flag == 1) w.freeze = 0; 
      continue;
    }
    for (int i = 0; i < 4; i++)
    {
      int dir = warrior_dir[flag][i];
      int ny = w.y + dy[dir];
      int nx = w.x + dx[dir];
      if (is_out(ny, nx) || 
            visited[max_freeze_dir][ny][nx] == 1) continue;
      if (man_calc_dist(ny, nx, my, mx) + 1 
            == man_calc_dist(w.y, w.x, my, mx))
      {
        //cout << ny << " : " << nx << "로 이동.." << endl;
        warrior_land[w.y][w.x]--;
        w.y = ny;
        w.x = nx;
        turn_info.warrior_move_sum++;
        warrior_land[w.y][w.x]++;
        if (ny == my && nx == mx)
        {
          //cout << "장렬히 전사" << endl;
          w.live = 0;
          turn_info.warrior_attack_succeed++;
          warrior_land[w.y][w.x]--;
        }
        break;
      }
    }
  }
}

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void fastIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

typedef struct _Warrior
{
  int y, x, freeze, live;
}Warrior;

vector<Warrior> warrior_vec;
int park_dist[54][54]; // medusa에서 park까지의 최단거리
int visited[4][54][54];

// 북쪽이 0, 이후 시계방향으로 1,2, ... 7
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};

// (상, 하, 좌, 우) 에 대한 탐색방향
// ex 상(idx == 0) 일 경우 탐색방향은 
// (7, 0, 1) <- (북서, 북, 북동)
vector<vector<int>> dirs = {
  {7, 0, 1}, // 기울기 -> (양수, 0또는 무한대, 음수)
  {3, 4, 5}, // 기울기 -> (양수, 0또는 무한대, 음수)
  {7, 6, 5}, // 기울기 -> (양수, 0또는 무한대, 음수)
  {3, 2, 1}  // 기울기 -> (양수, 0또는 무한대, 음수)
};

int n,m;
int my, mx, py, px; // medusa, park
int road[54][54];
int warrior_land[54][54];

typedef struct _Info
{
  int warrior_move_sum;
  int warrior_freezed;
  int warrior_attack_succeed;
} Info;

Info turn_info;

bool is_out(int y, int x)
{
  return (y < 0 || y >= n || x < 0 || x >= n);
}

int calc_dist()
{
  memset(park_dist, -1, sizeof(park_dist));
  queue <pii> q;
  q.push({py, px});
  park_dist[py][px] = 0;

  while(q.size())
  {
    pii here = q.front(); q.pop();
    int y = here.first;
    int x = here.second;

    if (y == my && x == mx) return park_dist[y][x];
    for (int i = 0; i < 8; i += 2)
    {
      int ny = y + dy[i];
      int nx = x + dx[i];

      if (is_out(ny, nx) || road[ny][nx] == 1) continue;

      if (park_dist[ny][nx] == -1)
      {
        park_dist[ny][nx] = park_dist[y][x] + 1;
        q.push({ny, nx});
      }
    }
  }
  return -1;
}

vector<pii> path;

bool trace(int y, int x) {
  if (y == py && x == px) return true;

  for (int i = 0; i < 4; i++)
  {
    int dir = dirs[i][1];
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    if (is_out(ny, nx) || park_dist[ny][nx] == -1) continue;
    if (park_dist[y][x] == park_dist[ny][nx] + 1)
    {
      path.push_back({ny, nx});
      if (trace(ny, nx)) return true;
      path.pop_back();
    }
  }
  
  return false;
}

void medusa_move(int turn)
{
  tie(my, mx) = path[turn];
  for (Warrior& w : warrior_vec)
  {
    if (w.live == 0) continue;
    if (w.y == my && w.x == mx)
    {
      w.live = 0;
      warrior_land[w.y][w.x] -= 1;
    }
  }
  return;
}

int max_freeze_dir;
void medusa_look()
{
  memset(visited, 0, sizeof(visited));
  int max_freeze_cnt = 0;
  for (int i = 0; i < 4; i++)
  {
    vector<int> look_dir = dirs[i];
    queue<pii> q;
    int freeze_cnt = 0;
    q.push({my, mx});
    while(q.size())
    {
      pii here = q.front(); q.pop();
      int y = here.first;
      int x = here.second;
      for (int dir : look_dir)
      {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if (is_out(ny, nx) || visited[i][ny][nx]) continue;
        if (warrior_land[ny][nx])
        {
          freeze_cnt += warrior_land[ny][nx];
          visited[i][ny][nx] = 1;
          queue<pii> warrior_q;
          vector<int> warrior_dir;
          if (ny == my || nx == mx)
          {
            warrior_dir.push_back(look_dir[1]);
          }
          else
          {
            if ( (double)(ny - my) / (double)(nx - mx) > 0)
            {
              warrior_dir.push_back(look_dir[0]);
              warrior_dir.push_back(look_dir[1]);
            }
            else
            {
              warrior_dir.push_back(look_dir[1]);
              warrior_dir.push_back(look_dir[2]);
            }
          }
          warrior_q.push({ny, nx});
          while(warrior_q.size())
          { 
            pii here = warrior_q.front(); warrior_q.pop();
            int y = here.first;
            int x = here.second;
            for (int dir : warrior_dir)
            {
              int ny = y + dy[dir];
              int nx = x + dx[dir];
              if (is_out(ny, nx) || visited[i][ny][nx]) continue;
              visited[i][ny][nx] = 100;
              warrior_q.push({ny, nx});
            }
          }
        }
        else
        {
          q.push({ny, nx});
          visited[i][ny][nx] = 1;
        }
      }
    }

    if (max_freeze_cnt < freeze_cnt)
    {
      max_freeze_cnt = freeze_cnt;
      max_freeze_dir = i;
    }
  }

  for (Warrior& w : warrior_vec)
  {
    if (w.live == 0) continue;
    if (visited[max_freeze_dir][w.y][w.x] == 1)
    {
      w.freeze = 1;
      turn_info.warrior_freezed++;
    }
  }
}

int man_calc_dist(int y1, int x1, int y2, int x2)
{
  return abs(y1 - y2) + abs(x2 - x1);
}

vector<int> warrior_dir[2] = {
  {0, 4, 6, 2}, // 상 하 좌 우
  {6, 2, 0, 4} // 좌 우 상 하 
};

void warrior_move(int flag)
{
  // cout << "이동시작!!!" << endl;
  // cout << " 메두사는 " << " : " << my << " : " << mx << endl;
  for (Warrior& w : warrior_vec)
  {
    //cout << w.y << " : " << w.x << " : " << w.freeze << " :  " << w.live << endl;
    if (w.live == 0) {
      //cout << w.y << " : " << w.x << " 는 죽음" << endl;
      continue;
    }
    if (w.freeze == 1)
    {
      //cout << w.y << " : " << w.x << " 는 얼어있음" << endl;
      if(flag == 1) w.freeze = 0; 
      continue;
    }
    for (int i = 0; i < 4; i++)
    {
      int dir = warrior_dir[flag][i];
      int ny = w.y + dy[dir];
      int nx = w.x + dx[dir];
      if (is_out(ny, nx) || 
            visited[max_freeze_dir][ny][nx] == 1) continue;
      if (man_calc_dist(ny, nx, my, mx) + 1 
            == man_calc_dist(w.y, w.x, my, mx))
      {
        //cout << ny << " : " << nx << "로 이동.." << endl;
        warrior_land[w.y][w.x]--;
        w.y = ny;
        w.x = nx;
        turn_info.warrior_move_sum++;
        warrior_land[w.y][w.x]++;
        if (ny == my && nx == mx)
        {
          //cout << "장렬히 전사" << endl;
          w.live = 0;
          turn_info.warrior_attack_succeed++;
          warrior_land[w.y][w.x]--;
        }
        break;
      }
    }
  }
}

int main()
{
  fastIO();
  cin >> n >> m;
  cin >> my >> mx >> py >> px;
  for (int i = 0; i < m; i++)
  {
    int y, x;
    cin >> y >> x;
    warrior_vec.push_back({y, x, 0, 1});
    warrior_land[y][x]++;
  }
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> road[i][j];
    }
  }


  int a = calc_dist();
  if (a == -1)
  {
    cout << -1 << endl;
    exit(0);
  }

  trace(my, mx);

  int turn = 0;

  while (1)
  {
    turn_info = {0, 0, 0};
    medusa_move(turn); // 전사가 공격못하고 죽음
    //cout << my << " : " << mx << endl;
    if (my == py && mx == px)
    {
      cout << 0 << endl; return 0;
    }
    medusa_look(); // 전사를 얼림
    warrior_move(0); // 전사가 첫 번째 이동: 공격 후 죽음
    warrior_move(1); // 전사의 두 번째 이동: 공격 후 죽음
    cout << turn_info.warrior_move_sum << " " 
         << turn_info.warrior_freezed << " "
         << turn_info.warrior_attack_succeed << endl;
    turn++;
  }
}

 

아주 어려운 도전이었다. 문제에서 상당 시간 헤맸는데, 한 가지 배운 점이 있다. 바로 기울기를 계산할 때는 int가 아니라 double을 사용해야 한다는 점이다! 기울기가 0.xx이면 0으로 int 변환되어서 잘못 탐지가 되었었다..