[모의 SW 역량테스트] 1949. 등산로 조성

[모의 SW 역량테스트] 등산로 조성

---

1. 이해하기

• 등산로를 만드는 규칙은 다음과 같다.
  1. 등산로는 가장 높은 봉우리에서 시작해야 한다.
  2. 등산로는 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
  3. 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K깊이만큼 지형을 깎는 공사를 할 수 있다.
• 가장 긴 등산로를 찾아 그 길이를 출력.
• 시뮬레이션 문제.

---

2. 구현하기

• 등산로의 가장 높은 봉우리를 구한다. 여러개가 있을 수 있기 때문에 배열로 구한다.

  • 이때, K만큼 깎는 공사를 한다고 하더라도 시작하는 위치는 바뀌지 않는다.

  vector<Point> get_max_hill() {
      vector<Point> ret;
      int max_value = 0;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              max_value = max(max_value,map[i][j]);
          }
      }
  
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              if(max_value == map[i][j]) ret.push_back({i,j});
          }
      }
      return ret;
  }

• 구한 가장 높은 봉우리를 바탕으로 가장 긴 등산로를 구한다.

  • 이전에 방문해도 다시 한번 체크를 해줘야 한다. 다음 번에 똑같은 곳을 방문하더라도 길이가 더 길어질 수 있기 때문에 길이를 비교해서 더 길면 갱신을 해줘야 한다.

  int bfs(int r, int c) {
      memset(dist,-1,sizeof(dist));
      queue<Point> q;
      q.push({r,c});
      dist[r][c] = 1;
      int ret = 0;
      while(!q.empty()) {
          int x = q.front().x, y = q.front().y; q.pop();
          ret = max(ret,dist[x][y]);
          for(int i = 0; i < 4; i++) {
              int nx = x+dx[i], ny = y+dy[i];
              if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
              if(map[nx][ny] >= map[x][y]) continue;
              if(dist[nx][ny] < dist[x][y]+1) {
                  q.push({nx,ny});
                  dist[nx][ny] = dist[x][y]+1;
              }
          }
      }
      return ret;
  }

• 맵 전체를 돌아보며 최대 K깊이 만큼의 공사를 실시한다.

  • 전체 맵에 대해서 K만큼의 깊이만 검사를 하면 fail이 발생할 수 있다. 0~K깊이를 모두 깎아봐야 한다.

  int simulate(vector<Point> st_hill) {
      int size = st_hill.size();
      int ret = 0;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              for(int h = 0; h <= K; h++) {
                  int ori_map = map[i][j];
                  map[i][j] -= h;
                  if(map[i][j] < 0) map[i][j] = 0;
                  for(int k = 0; k < size; k++) {
                      ret = max(ret,bfs(st_hill[k].x, st_hill[k].y));
                  }
                  map[i][j] = ori_map;
              }
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
struct Point{
    int x,y;
};
int map[8][8];
int dist[8][8];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N,K;

int bfs(int r, int c) {
    memset(dist,-1,sizeof(dist));
    queue<Point> q;
    q.push({r,c});
    dist[r][c] = 1;
    int ret = 0;
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        ret = max(ret,dist[x][y]);
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
            if(map[nx][ny] >= map[x][y]) continue;
            if(dist[nx][ny] < dist[x][y]+1) {
                q.push({nx,ny});
                dist[nx][ny] = dist[x][y]+1;
            }
        }
    }
    return ret;
}

int simulate(vector<Point> st_hill) {
    int size = st_hill.size();
    int ret = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            for(int h = 0; h <= K; h++) {
                int ori_map = map[i][j];
                map[i][j] -= h;
                if(map[i][j] < 0) map[i][j] = 0;
                for(int k = 0; k < size; k++) {
                    ret = max(ret,bfs(st_hill[k].x, st_hill[k].y));
                }
                map[i][j] = ori_map;
            }
        }
    }
    return ret;
}

void input() {
    cin >> N >> K;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}

vector<Point> get_max_hill() {
    vector<Point> ret;
    int max_value = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            max_value = max(max_value,map[i][j]);
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(max_value == map[i][j]) ret.push_back({i,j});
        }
    }
    return ret;
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        vector<Point> st_hill = get_max_hill();
        cout << "#" << t << ' ' << simulate(st_hill) << '\n';
    }
    return 0;
}