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

2018. 4. 5에 쓰여진 글입니다.

---

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE

SW Expert Academy

 

풀이방법

-DFS버전 풀이

최대 경로를 구할때 dfs_call이라는 함수 호출수를 써줌.

그래서 함수가 호출된수=최대경로가 될것이기때문에 이값의 최대값을 최대등산로경로로 저장해주면서 탐색함

 

-BFS버전 풀이

만약에 방문체크를 할때 bool visited배열을 준다면 틀림 (방문배열을 true/false, 또는 1,0으로 판단하는것)

왜냐면 밑에와 같이 있는 맵상태일때,

1 4

2 3

1 -> 4로 가는 루트는 2가지가 있음 

1번루트

1 → 4

 

2번루트

1      4

↓        ↑

2  →  3

 

당연히 1,2,3,4의 큐가 더 뒤에있을것임. 근데 1 4 로 갈때 이미 4를 방문체크를 해줬기때문에 틀리게됨.

그렇다고 방문체크를 안해주면 시간초과가 남. 어찌보면 당연한것.

그럼 어떻게 해야할까?

그건 바로 방문체크를 숫자로 주는것임. 나는 dp배열을 만들어서 일단 -1(NOT_VISITED)로 초기화해줌

그리고 돌면서 

NOT_VISITED상태이면 바로 현재이동횟수를 dp배열의 해당좌표에 저장해주고

어떤 숫자가있는상태 즉 방문된 상태이면 지금 내가 가는 새로운 경로가 더 길다면 내 값을 저장하고 큐에 넣어주고 아니면 걍 아무것도 안함.

이렇게 돌면 답이 나옴 .

 

시간은

DFS기준 0.01s가 나오고

BFS기준 0.02s가 나옴

등산로 조성 문제는 DFS를 이용하는게 더 편하고 좋아보임.

 

49개만 맞으시는 분들을 위한 추가 팁

solving talk에도 질문이 올라오고 있고, SWEA 등산로 문제에서 댓글로도 물어보는 사람들이 꽤 보여서 다시한번 제대로 정리.

답변달아주면서 블로그에도 정리.

이유는 가장 높은 봉우리부터 시작해야만 하기 때문입니다.

 

규칙의 순서를 잘 봅시다.

 

 ① 등산로는 가장 높은 봉우리에서 시작해야 한다.

 ② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다. 즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

 ③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

 

가장 높은 봉우리에서 시작해야한다고 합니다. 그리고 움직이다가 어느지점을 공사합니다. 이 순서로만 해야합니다.

무슨말인지 감이 오시나요?

지금 제 코드도 그렇고 일반적으로 짜신 코드들은 모든좌표를 탐색하면서 (0,0)부터 (n-1,n-1)까지 k만큼 깎아놓고 

가장높은 봉우리를 찾아서 경로를 체크합니다. 깎아놓고 나서 가장 높은 봉우리를 찾게되는경우가 문제가 됩니다.

만약에 가장 높은 봉우리를 파게 된다면요? 근데 그 봉우리가 한개라면요?

예시를 들면

 

1 1

1 2

 

라고 맵이 있다고 해봅시다.  또 1까지 팔수있다고 해봅시다

그럼 2가 가장 높은 봉우리일겁니다.

 

- 이때 문제대로 진행하면,

-> 시작은 무조건 2부터 시작해서 경로를 찾음. 움직이다가 k만큼 깎을수있음.

 

- 49개만맞는 코드대로 진행 

-> 1 1      0 1   1 0   1 1    1 1 

    1 2      1 2   1 1   0 2    1 1 

이런식으로 다 파놓겠죠?

그리고 가장 높은 봉우리를 찾겠죠.

그럼 빨간색으로 칠한 마지막 부분을 보면 

1 1

1 1

이 되어있죠?

이상태로 가장 높은 봉우리를 찾으면 1일 겁니다. 그리고 1을 시작점으로 경로를 찾게되고 이부분에서 틀리게 됩니다.

문제대로 진행한다면 2인 봉우리에서 시작해서 막히면 파게되기때문에 1인 봉우리에서는 시작할수도없고 

1 1 

1 1  

이라는 맵 조차 만들어질수가없습니다.

 

만약 49개만 맞는 파놓고 최대봉우리를 찾는 형식으로 코드가 구성되어있다면 해당 조건을 추가해서 풀어줘야합니다.

 

이 조건을 다르게 표현하면, 

초기에 주어진 등산로 맵에서 가장 높은 곳의 좌표에서만 시작할수 있으며, '가장 높은 봉우리가 1개 일때 그 가장 높은 봉우리는 공사를 진행할수없다.' 

또는

'가장 높은 봉우리가 2번째로 높은 봉우리가 되도록 공사를 진행할수없다.'

라는 조건으로 해석해야합니다.

 

무슨 말이냐면, 즉 만약 맵이 이렇게 있다고 해봅시다

3 5 4

5 9 2

1 4 8

그럼 이때 9가 제일 높은 봉우리가 되겠죠? 

근데 9인 위치를 공사한다고 해봅시다.

9를 깎아서 8이되었습니다. 그럼 무슨 일이 벌어질까요?

3 5 4 

5 8 2

1 4 8

 

이 되겠죠. 그럼 8이 이제 새로운 최대 높은 봉우리가 되겠죠. 그리고 8부터 경로를 찾을겁니다.

근데 이 경로로 등산로를 만들게되면 틀리게 됩니다. 초기에 있던 가장 높은 봉우리(9)가 아니여서요.

 

사실 이걸 알게된건 처음에 코드를 짤때 가장높은 봉우리와 2번째로 높은 봉우리까지 전부 체크해서 짜줬습니다.

만약 2번째 봉우리랑같아지면 가장 높은 봉우리도 여러개가 되고, 만약 가장높은 봉우리가 2번째로 높은 봉우리보다 낮아졌을때는 2번째로 높은 봉우리를 시작점으로 탐색하게 했습니다.

저는 이게 이 문제의 함정인줄알았거든요. 근데 아니더라고요. 문제를 제가 잘못본거더라고요.. 

조건에서 순서대로 행해야한다는 말이없어서 조금 애매한 부분이기는 합니다만.. 이유는 대체로 이것때문일 확률이 높습니다. 

 

SWEA Solving Talk 질문에서 답글달아주고나서 수정하여 올림. (원문 링크)

https://www.swexpertacademy.com/main/talk/solvingTalk/boardCommuView.do?commuId=AWKuhQO6_WUDFAUV&searchCondition=COMMU_DETAIL-COMMU_TITLE-NICK_NAME_TAG&searchKeyword=&pageIndex=1&pageSize=10&orderBy=DATE_DESC

SW Expert Academy

답변 달아주고나니까 열심히 답변달기도했고 ㅋㅋ 이거 내 블로그에도 업데이트해야겠다 싶어서 후다닥 업데이트..

 

소스코드

-DFS코드

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
 
using namespace std;
 
int map[8][8];
bool visited[8][8];
int K;
int N;
int Answer;
int max_height;
int dfs_call;
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
vector < pair < int, int > > v;        //최대 봉우리 좌표 저장
 
void Init_map()        //맵초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            map[i][j] = 0;
}
 
void Init_visited()        //방문초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            visited[i][j] = false;
}
 
void solve(int cur_x, int cur_y)
{
    dfs_call++;        //함수호출카운트 증가
    if (!visited[cur_x][cur_y]) {
        visited[cur_x][cur_y] = true;        //방문표시
        Answer = max(dfs_call, Answer);        //함수호출수와 정답비교해서 큰값 정답에 저장
        for (int i = 0; i < 4; i++) {
            int new_x = cur_x + dx[i];
            int new_y = cur_y + dy[i];
            if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < N        //범위안에있고
                && !visited[new_x][new_y]                            //방문을안했고
                && map[new_x][new_y] < map[cur_x][cur_y]) {            //지금좌표보다 작다면 (경로를 만들수있다면)
                solve(new_x, new_y);        //들어갑시더
            }
 
        }
        visited[cur_x][cur_y] = false;        //방문원상복귀시켜줌
    }
    dfs_call--;        //함수호출카운트 감소
}
 
int main()
{
    //freopen("sample_input.txt", "r", stdin);
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        //초기화
        Answer = -987654321;
        max_height = -987654321;
        cin >> N >> K;
        Init_map();
        Init_visited();
        v.clear();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
                max_height = max(map[i][j], max_height);        //입력받으면서 최대 봉우리 높이 저장
            }
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (map[i][j] == max_height)        //최대 봉우리이면
                    v.push_back(make_pair(i, j));    //해당좌표 벡터에 넣어주기
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int k = 0; k <= K; k++) {        //0~k까지 파보기
                    map[i][j] -= k;    //k만큼 파고
                    for (int m = 0; m < v.size(); m++) {        //최대봉우리좌표전부 돌려줌
                        if (!(v[m].first == i&&v[m].second == j)) {    //만약 판곳이 최대봉우리라면 
                                                                       //최대봉우리가 아니게될꺼니까 패스하고 
                                                                       //아니라면 경로탐색
                            Init_visited();        //방문초기화
                            dfs_call = 0;        //함수호출수초기화
                            int cur_x = v[m].first;    //최대봉우리좌표넣기
                            int cur_y = v[m].second;//최대봉우리좌표넣기
                            solve(cur_x, cur_y);    //solve함수 호출(최대경로탐색)
                        }
                    }
                    map[i][j] += k;    // 원상복귀
                }
        cout << "#" << test_case << " " << Answer << endl;
    }
 
    return 0;
}

 

-BFS코드

#include <iostream>
#include <algorithm>        //min max 위한 헤더
#include <vector>            //vector 위한 헤더
#include <queue>            //queue 위한 헤더
 
using namespace std;
 
enum { NOT_VISITED = -1, VISITED = 1 };
 
int N, K;
int map[8][8];
int dp[8][8];
int Answer;
vector < pair < int, int > > v;                        //최대 봉우리 좌표 저장 벡터
queue < pair < pair < int, int >, int  > > q;        //좌표, 등산로길이
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int max_height;        //최대봉우리높이
 
void Init_map()        //맵초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            map[i][j] = 0;
}
 
void Init_dp()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            dp[i][j] = NOT_VISITED;
}
 
int max_length(int x, int y)
{
    Init_dp();                                //dp배열 초기화
    q.push(make_pair(make_pair(x, y), 1));    //큐에 현재좌표와 현재 등산로 길이(1) 넣기
    dp[x][y] = VISITED;                        //지금 dp배열 값을 -1(VISITED)로 초기화
    int length = 1;                            //현재길이는 1로 저장
    while (!q.empty()) {                    //큐 빌때까지 돌리자
        int cur_x = q.front().first.first;    //현재좌표저장
        int cur_y = q.front().first.second;
        int cur_cnt = q.front().second;        //현재등산경로 저장
        q.pop();                            //큐빼주고
        length = max(length, cur_cnt);        //최대길이 체크
        for (int i = 0; i < 4; i++) {        //상하좌우돌리기
            int new_x = cur_x + dx[i];        //새로운 좌표 넣어주기
            int new_y = cur_y + dy[i];
            if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < N &&    //방문안했고
                dp[cur_x][cur_y] + 1 > dp[new_x][new_y] &&            //현재경로가 더길고
                map[cur_x][cur_y]>map[new_x][new_y]) {                //등산로 조성이 가능하면
                dp[new_x][new_y] = dp[cur_x][cur_y] + 1;            //현재 등산로길이를 넣어주고
                q.push(make_pair(make_pair(new_x, new_y), cur_cnt + 1));    //큐에 다음좌표 넣기
            }
        }
    }
    return length;    //구한 최대 등산로 길이 리턴
}
 
void solve()
{
    for (int i = 0; i < v.size(); i++) {        //최대 봉우리 다돌리기
        int cur_x = v[i].first;
        int cur_y = v[i].second;
        //최대 봉우리에서 시작해야되는데 깎은 좌표가 최대봉우리이면 최대봉우리가 아니게 되기때문에
        if (map[cur_x][cur_y] == max_height)                //같은경우에만
            Answer = max(max_length(cur_x, cur_y), Answer);    //최대 봉우리에서 등산로 조성해주기
    }
}
 
int main()
{
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        Answer = 0;                    //정답초기화
        max_height = -987654321;    //최대높이 초기화
        cin >> N >> K;                //입력받기
        Init_map();                    //맵초기화
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
                max_height = max(max_height, map[i][j]);//최대 봉우리 높이 찾기
            }
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (map[i][j] == max_height)
                    v.push_back(make_pair(i, j));        //최대봉우리 저장
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int k = 0; k <= K; k++) {    //모든 좌표를 0~K만큼 깎아준다
                    map[i][j] -= k;            //깎아주고
                    solve();                //solve함수호출(최대등산로구해주기)
                    map[i][j] += k;            //복원
                }
        cout << "#" << test_case << " " << Answer << endl;    //정답출력
    }
 
 
    return 0;
}