본문 바로가기

카테고리 없음

백준 14890번 경사로

문제 링크

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

알고리즘 분류

 

시뮬레이션

 

풀이

 

문제의 조건에 맞게 경사로를 설치해주는 시뮬레이션 문제입니다.

고려해야할 조건은 다음과 같습니다.

 

1. 경사로를 설치하는 곳의 낮은칸과 높은칸의 높이차는 1이어야 합니다.

2. L개의 블록이 연속되어야 합니다.

3. 경사로가 이미 설치된 곳은 경사로를 설치 할 수 없습니다.

 

이러한 조건을 행과 열을 검사하는 함수를 따로 만들어서 문제를 해결했습니다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
 
using namespace std;
 
int n, l,ans;
int map[101][101];
bool check[101][101];
 
void checky(int cur) // 행 검사
{
    for (int i = 0; i < n - 1; i++)
    {
        if (map[cur][i] != map[cur][i + 1]) // 높이가 다르면 경사로 건설
        {
            if (map[cur][i] > map[cur][i + 1]) // 현재 블록보다 높이가 낮을 경우
            {
                if (map[cur][i] - map[cur][i + 1== 1// 높이 차이가 1일 경우
                {
                    for (int j = i + 1; j < i + 1 + l; j++)
                    {
                        if (map[cur][i + 1== map[cur][j] && !check[cur][j]) // 경사로가 없고 높이가 같아야함
                        {
                            check[cur][j] = true// 경사로 설치
                        }
                        else
                            return;
                    }
                }
                else
                    return;+
            }
            else // 현재 블록 보다 높이가 높을 경우
            {
                if (map[cur][i + 1- map[cur][i] == 1// 높이 차이가 1일 경우
                {
                    for (int j = i; j > i - l; j--)
                    {
                        if (map[cur][i] == map[cur][j] && !check[cur][j]) // 경사로가 없고 높이가 같아야함
                        {
                            check[cur][j] = true// 경사로 설치
                        }
                        else
                            return;
                    }
                }
                else
                    return;
            }
        }
    }
 
    ans++;
}
 
void checkx(int cur) // 열검사
{
    for (int i = 0; i < n - 1; i++)
    {
        if (map[i][cur] != map[i+1][cur])
        {
            if (map[i][cur] > map[i+1][cur])
            {
                if (map[i][cur] - map[i+1][cur] == 1)
                {
                    for (int j = i + 1; j < i + 1 + l; j++)
                    {
                        if (map[i+1][cur] == map[j][cur] && !check[j][cur])
                        {
                            check[j][cur] = true;
                        }
                        else
                            return;
                    }
                }
                else
                    return;
            }
            else
            {
                if (map[i+1][cur] - map[i][cur] == 1)
                {
                    for (int j = i; j > i - l; j--)
                    {
                        if (map[i][cur] == map[j][cur] && !check[j][cur])
                        {
                            check[j][cur] = true;
                        }
                        else
                            return;
                    }
                }
                else
                    return;
            }
        }
    }
    
    ans++;
}
int function()
{
    freopen("input.txt""r", stdin);
    setbuf(stdout, NULL);
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> l;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }
 
    ans = 0;
    for (int i = 0; i < n; i++)
    {
        checky(i);
    }
    memset(check, 0sizeof(check));
    for (int i = 0; i < n; i++)
    {
        checkx(i);
    }
 
    printf("%d\n", ans);
    
 
    return 0;
}