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

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

이미 푼 문제임에도 불구하고 처음에 아무 것도 안 떠올라서 당황했지만…
다 짜고 보니 더 효율적인 코드가 됨.
– 최대 높이인 곳들을 list에 삽입
– DFS로 짬. 각 함수에서 visited map을 만들고 처음 최대 높이인 곳을 visited로 처리. (이후 DFS 함수에서는 방문할 수 있는 경우만 실행되니 visited는 항상 1로 처리)
이후, 왼쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 오른쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 위쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 아래쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
(각 경우, 더 이상 진행이 안 되면 이후 진행이 불가능하므로, 현재까지의 거리를 업데이트함)

#include <iostream>
#include <cstdlib>

using namespace std;

void process (int row, int column, int **map, int size, int k);
void process_(int length, int row, int column, int** map, int** visited, int size, int k, bool constructed);

int maxLength = 1;

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    //freopen("input.txt", "r", stdin);
    int T = 0;
    cin >> T;

    int** map = (int**) malloc (8 * sizeof(int*));
    for (int i = 0; i < 8; i++) {
        map[i] = (int*) malloc (8 * sizeof(int));
    }

    for (int test_case = 1; test_case <= T; test_case++) {
        cout << "#" << test_case << ' ';

        maxLength = 0;

        int numN = 0, numK = 0;
        cin >> numN >> numK; // N: map size, k: construction depth limit

        int maxValue = 0, maxRow[5] = {0}, maxColumn[5] = {0}, maxIdx = -1;

        for (int r = 0; r < numN; r++) {
            for (int c = 0; c < numN; c++) {
                cin >> map[r];
                if (maxValue < map[r]) {
                    maxValue = map[r];
                    maxIdx = 0;
                    maxRow[maxIdx] = r;
                    maxColumn[maxIdx] = c;
                }
                else if (maxValue == map[r]) {
                    maxIdx++;
                    maxRow[maxIdx] = r;
                    maxColumn[maxIdx] = c;
                }
            }
        }

        for (int i = 0; i < maxIdx + 1; i++) {
            process(maxRow[i], maxColumn[i], map, numN, numK);
        }

        cout << maxLength << '\n';
    }
	
	return 0;
}

void process (int row, int column, int **map, int size, int k) {
    // visited map
    int **visited = (int**) malloc (size * sizeof(int*));
    for (int i = 0; i < size; i++) 
        visited[i] = (int*) malloc (size * sizeof(int));
    
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            visited[i][j] = 0;

    visited[row][column] = 1;        

    bool constructed = false;

    // left direction
    if (column > 0 && map[row][column] > map[row][column - 1]) 
        process_(2, row, column - 1, map, visited, size, k, constructed);
    else if (constructed == false && column > 0 && map[row][column] > map[row][column - 1] - k) {
        int backup = map[row][column - 1];
        map[row][column - 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row, column - 1, map, visited, size, k, true);
        map[row][column - 1] = backup;
    }

    // right direction
    if (column < size - 1 && map[row][column] > map[row][column + 1])
        process_(2, row, column + 1, map, visited, size, k, constructed);
    else if (constructed == false && column < size - 1 && map[row][column] > map[row][column + 1] - k) {
        int backup = map[row][column + 1];
        map[row][column + 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row, column + 1, map, visited, size, k, true);
        map[row][column + 1] = backup;
    }

    // up direction
    if (row > 0 && map[row][column] > map[row - 1][column])
        process_(2, row - 1, column, map, visited, size, k, constructed);
    else if (constructed == false && row > 0 && map[row][column] > map[row - 1][column] - k) {
        int backup = map[row - 1][column];
        map[row - 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row - 1, column, map, visited, size, k, true);
        map[row - 1][column] = backup;
    }

    // down direction
    if (row < size - 1 && map[row][column] > map[row + 1][column])
        process_(2, row + 1, column, map, visited, size, k, constructed);
    else if (constructed == false && row < size - 1 && map[row][column] > map[row + 1][column] - k) {
        int backup = map[row + 1][column];
        map[row + 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row + 1, column, map, visited, size, k, true);
        map[row + 1][column] = backup;
    }
}

void process_(int length, int row, int column, int** map, int** visited, int size, int k, bool constructed) {
    int **newVisited = (int**) malloc (size * sizeof(int*));
    for (int i = 0; i < size; i++) 
        newVisited[i] = (int*) malloc (size * sizeof(int));
    
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            newVisited[i][j] = visited[i][j];

    newVisited[row][column] = 1;
    
    if (column > 0 && newVisited[row][column - 1] == 0 && map[row][column] > map[row][column - 1])
        process_(length + 1, row, column - 1, map, newVisited, size, k, constructed);
    else if (constructed == false && column > 0 && newVisited[row][column - 1] == 0 && map[row][column] > map[row][column - 1] - k) {
        int backup = map[row][column - 1];
        map[row][column - 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row, column - 1, map, newVisited, size, k, true);
        map[row][column - 1] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (column < size - 1 && newVisited[row][column + 1] == 0 && map[row][column] > map[row][column + 1])
        process_(length + 1, row, column + 1, map, newVisited, size, k, constructed);
    else if (constructed == false && column < size - 1 && newVisited[row][column + 1] == 0 && map[row][column] > map[row][column + 1] - k) {
        int backup = map[row][column + 1];
        map[row][column + 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row, column + 1, map, newVisited, size, k, true);
        map[row][column + 1] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (row > 0 && newVisited[row - 1][column] == 0 && map[row][column] > map[row - 1][column])
        process_(length + 1, row - 1, column, map, newVisited, size, k, constructed);
    else if (constructed == false && row > 0 && newVisited[row - 1][column] == 0 && map[row][column] > map[row - 1][column] - k) {
        int backup = map[row - 1][column];
        map[row - 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row - 1, column, map, newVisited, size, k, true);
        map[row - 1][column] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (row < size - 1 && newVisited[row + 1][column] == 0 && map[row][column] > map[row + 1][column])
        process_(length + 1, row + 1, column, map, newVisited, size, k, constructed);
    else if (constructed == false && row < size - 1 && newVisited[row + 1][column] == 0 && map[row][column] > map[row + 1][column] - k) {
        int backup = map[row + 1][column];
        map[row + 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row + 1, column, map, newVisited, size, k, true);
        map[row + 1][column] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.