ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #1949 _ 등산로 조성
    Problem Solving/SWEA 2019. 10. 26. 01:32

    [등산로 조성] 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] #4014 _ 활주로 건설  (0) 2019.08.28
    [SWEA] #2112 _ 보호 필름  (0) 2019.08.28
    [SWEA] #1210 _ Ladder1  (0) 2019.08.28

    댓글

@Jo Grini's Blog