[ 삼성 SW역량 평가 14890 ] 경사로 (C++)

[ 난이도 ]

★★☆

 

[ 문제 링크 ]

https://www.acmicpc.net/problem/14890

 

[ 문제 풀이 ]

문제는 다음과 같다. N X N 크기의 맵에 각각의 칸에는 높이가 표시되어있다. N X N개 맵에 길은

다음 그림 1과 같이 2N개이다. 높이가 다른 길을 지나기 위해 우리는 L길이에 높이 1인 경사로를 설치하여야

한다.

그릠1

경사로는 다음과 같이 놓을 수 없다.

그림2

위의 예시를 정답이 되는 케이스로 보면 더 이해하기 쉬울 것이다.

그림3

이 문제는 특별한 알고리즘을 사용하기 보다는 단순히 경우에 따른 If와 For문을 적절히 사용하고 각 길에 경사로가 놓인 자리를 방문 처리하여 해결하였다.

 

[ 소스 코드 ]

// 헤더파일을 불러옵니다.
#include <iostream>
using namespace std;
 
// 맵의 최대 사이즈를 설정합니다
#define Max_Size 101
 
// Map: 지도, VIsit: 경사로 설치유무, N: 맵의크기, L: 경사로 길이, answer: 정답
int Map[Max_Size][Max_Size];
int Visit[Max_Size][Max_Size] = { 0 };
int N, L;
int answer = 0;
 
// 입력을 받아오는 함수
void Load_Input()
{
    cin >> N >> L;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            cin >> Map[i][j];
        }
    }
}
 
// 세로나 가로로 한번 탐색후 방문여부를 초기화 시켜줌
void Initialize_Visit()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            Visit[i][j] = 0;
        }
    }
}
 
// 정답을 탐색 합니다.
void Find_Way()
{
    // 가로줄 부터 탐색합니다
    for (int i = 1; i <= N; ++i)
    {
        // cnt : 경사로를 놓을수 있고 길이 평탄할경우 마다 카운트
        int cnt = 0;
 
        // Check_Floor : 경사로를 놓을 수 있을만큼 평평한지 검사합니다.
        int Check_Floor = 0;
 
        // i번째 가로줄의 j번째 위치 부터 탐색
        for (int j = 1; j <= N - 1; ++j)
        {
            // Check_Floor는 칸이 바뀔떄마다 초기화 시켜줌
            Check_Floor = 0;
 
            //1.현재와 다음 칸의 크기가 같으면 Cnt++
            if (Map[i][j] == Map[i][j+1])
            {
                cnt++;
            }
 
            //2.오르막길을 만났을경우
            if (Map[i][j] == Map[i][j+1] - 1)
            {
                // L 길이의 경사로가 놓일만큼 평평한가.
                for (int k = j; k >= j + 1 - L; --k)
                {    // 칸의 숫자가 같고 방문기록이 없을경우 Check_Floor를 더해줌
                    if ((Map[i][k] == Map[i][j]) && Visit[i][k] == 0) Check_Floor++;
                }
                // Check_Floor가 길이 L과 같다면 경사로를 놓을 수 있으므로 Cnt ++ 해줌
                if (Check_Floor >= L)
                {
                    // 경사로가 놓인 자리는 모두 방문 처리함.
                    for (int r = j; r >= j + 1 - L; --r)
                    {
                        Visit[i][r] = 1;
                    }
                    cnt++;
                }
                else continue;
            }
            // 3.내리막길을 만났을경우
            if (Map[i][j] == Map[i][j+1] + 1)
            {
                // L 길이의 경사로가 놓일만큼 평평한가.
                for (int k = j + 1; k <= j + L; ++k)
                {    // 칸의 숫자가 같고 방문기록이 없을경우 Check_Floor를 더해줌
                    if ((Map[i][k] == Map[i][j+1]) && Visit[i][k] == 0) Check_Floor++;
                }
                // Check_Floor가 길이 L과 같다면 경사로를 놓을 수 있으므로 Cnt ++ 해줌
                if (Check_Floor >= L)
                {    
                    // 경사로가 놓인 자리는 모두 방문 처리함.
                    for (int r = j + 1; r <= j + L; ++r)
                    {
                        Visit[i][r] = 1;
                    }
                    cnt++;
                }
            }
            //4.너무 큰 내리막 길을 만났을 경우
            if (Map[i][j] - Map[i][j+1] >= 2)
            {
                continue;
            }
 
            //5.너무 큰 오르막 길을 만났을 경우
            if (Map[i][j+1] - Map[i][j] >= 2)
            {
                continue;
            }
 
            // 한 가로에서 cnt가 N-1이라면 평평하거나 길을 놓아 모두 지나간것이므로 정답처리함
            if (cnt == N - 1)
            {
                answer++;
            }
        }
    }
    // 세로 줄로 넘어가기 전에 방문 기록을 지워줌.
    Initialize_Visit();
 
    // 세로줄을 탐색합니다
    for (int j = 1; j <= N; ++j)
    {
        int cnt = 0;
        int Check_Floor = 0;
 
        // 세로칸 하나씩 탐색
        for (int i = 1; i <= N - 1; ++i)
        {
            // 1. 현재칸의 크기와 다음 칸의 크기가 같으면 Cnt++
            if (Map[i][j] == Map[i+1][j])
            {
                cnt++;
            }
            Check_Floor = 0;
            // 2. 오르막길을 만났을경우
            if (Map[i][j] == Map[i+1][j] - 1)
            {
                // L 길이의 경사로가 놓일만큼 평평한가.
                for (int k = i; k >= i + 1 - L; --k)
                {    // 평평하며 방문기록이 없을경우
                    if ((Map[k][j] == Map[i][j]) && Visit[k][j] == 0) Check_Floor++;
                }
                // Check_Floor가 길이 L과 같다면 경사로를 놓을 수 있으므로 Cnt ++ 해줌
                if (Check_Floor >= L)
                {
                    //
                    for (int r = i; r >= i + 1 - L; --r)
                    {    // 경사로가 놓인 자리는 모두 방문 처리함.
                        Visit[r][j] = 1;
                    }
                    cnt++;
                }
                else continue;
            }
            //3.내리막길을 만났을경우
            if (Map[i][j] == Map[i+1][j] + 1)
            {
                // L 길이의 경사로가 놓일만큼 평평한가.
                for (int k = i + 1; k <= i + L; ++k)
                {
                    if ((Map[k][j] == Map[i + 1][j]) && Visit[k][j] == 0) Check_Floor++;
                }
                // Check_Floor가 길이 L과 같다면 경사로를 놓을 수 있으므로 Cnt ++ 해줌
                if (Check_Floor >= L)
                {    
                    // 경사로가 놓인 자리는 모두 방문 처리함.
                    for (int r = i + 1; r <= i + L; ++r)
                    {
                        Visit[r][j] = 1;
                    }
                    cnt++;
                }
            }
            //4.너무 큰 내리막 길을 만났을 경우
            if (Map[i][j] - Map[i+1][j] >= 2)
            {
                continue;
            }
 
            //5.너무 큰 오르막 길을 만났을 경우
            if (Map[i+1][j] - Map[i][j] >= 2)
            {
                continue;
            }
 
            // 한 세로에서 cnt가 N - 1이라면 평평하거나 길을 놓아 모두 지나간것이므로 정답처리함
            if (cnt == N - 1)
            {
                answer++;
            }
        }
    }
}
 
int main()
{
    // 입력을 받아옵니다.
    Load_Input();
 
    // 길을 찾습니다.
    Find_Way();
 
    // 정답을 출력합니다.
    cout << answer;
 
    // 시스템을 정상종료 합니다.
    return 0;
}