-
[SWEA] #1949 _ 등산로 조성Problem Solving/SWEA 2019. 10. 26. 01:32728x90
[등산로 조성] https://swexpertacademy.com/main/code/problem/problemDetail.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
top이라는 벡터에 제일 높은 봉우리의 좌표를 넣어둔다.
top에 있는 좌표에서 시작하여 solve 함수에서 dfs를 이용하여 최대 길이를 구한다.
한 번 깎은 곳의 좌표는 cut 벡터에 저장하고,
cut 벡터의 사이즈가 0일 경우에는 한 번도 깎지 않은 것으로 간주하여
깎아 갈 수 있는 최대 길이를 갱신하도록 구현하였다.
[ 소스 코드 ]
#include <cstdio> #include <vector> #include <algorithm> #define MAX 8 using namespace std; int dx[] = { 0, 0, -1, 1 }, dy[] = { -1, 1, 0, 0 }; int N, K, long_path, cut_depth; int map[MAX][MAX], chk[MAX][MAX]; vector<pair<int, int> >top, cut; void solve(int val, int y, int x); void initChk(); int main() { int T; scanf("%d", &T); for (int i = 1; i <= T; i++) { scanf("%d %d", &N, &K); for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { scanf("%d", &map[j][k]); if (top.size() > 0) { // setting top if (map[top.front().first][top.front().second] < map[j][k]) { top.clear(); top.push_back(make_pair(j, k)); } else if (map[top.front().first][top.front().second] == map[j][k]) top.push_back(make_pair(j, k)); } else top.push_back(make_pair(j, k)); } } long_path = 0; for (int j = 0; j < top.size(); j++) { solve(1, top[j].first, top[j].second); initChk(); } printf("#%d %d\n", i, long_path); top.clear(); } return 0; } void initChk() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) chk[i][j] = 0; } } void solve(int val, int y, int x) { int tmp_y, tmp_x; chk[y][x] = 1; long_path = max(long_path, val); for (int i = 0; i < 4; i++) { tmp_x = x + dx[i]; tmp_y = y + dy[i]; if (tmp_x < 0 || tmp_y < 0 || tmp_x >= N || tmp_y >= N) continue; if (chk[tmp_y][tmp_x]) continue; if (map[tmp_y][tmp_x] >= map[y][x]) { if (cut.size()) continue; else { if (map[tmp_y][tmp_x] - K >= map[y][x]) continue; else { cut.push_back(make_pair(tmp_y, tmp_x)); cut_depth = map[tmp_y][tmp_x] - map[y][x] + 1; map[tmp_y][tmp_x] -= cut_depth; } } } solve(val + 1, tmp_y, tmp_x); if (cut.size()) { if (cut.front().first == tmp_y && cut.front().second == tmp_x) { map[tmp_y][tmp_x] += cut_depth; cut.pop_back(); } } } chk[y][x] = 0; }
반응형'Problem Solving > SWEA' 카테고리의 다른 글
[SWEA] #1953 _ 탈주범 검거 (0) 2019.10.29 [SWEA] #1952 _ 수영장 (0) 2019.10.29 [SWEA] #1949 _ 등산로 조성 (0) 2019.10.26 [SWEA] #4014 _ 활주로 건설 (0) 2019.08.28 [SWEA] #2112 _ 보호 필름 (0) 2019.08.28 [SWEA] #1210 _ Ladder1 (0) 2019.08.28 TAG
댓글 0