반응형

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

 

14890번: 경사로

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 길의 왼쪽부터 탐색하면서 경사로를 놓을 수 있는지 없는지 체크합니다.

 

2. 길의 오른쪽부터 탐색하면서 경사로를 놓을 수 있는지 없는지 체크합니다.

 

3. 위의 1, 2의 과정 중 하나라도 만족하지 않는다면 false를 반환하고, 둘 다 만족하면 true를 반환합니다.

 

4. true를 반환한 도로의 개수를 ans에 저장해 출력합니다.

 

[ 소스코드 ]

 

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
#include<iostream>
 
using namespace std;
 
int N, L;
int arr1[100][100];
int arr2[100][100];
 
bool check(int num, int arr[][100])    //길의 통과 여부 확인
{
    int visited[100] = { 0 };
    for (int i = 0; i < N - 1; i++) {
        if (arr[num][i] - arr[num][i + 1] == 1) {
            if (i >= N - L) return false;
            int temp = arr[num][i + 1];
            for (int j = 0; j < L; j++) {
                if (visited[i + 1 + j] == 1 || temp != arr[num][i + 1 + j]) return false;
                temp = arr[num][i + 1 + j];
                visited[i + 1 + j] = 1;
            }
        }
        else if (arr[num][i] - arr[num][i + 1] > 1) {
            return false;
        }
    }
 
    for (int i = N - 1; i >= 1; i--) {
        if (arr[num][i] - arr[num][i - 1] == 1) {
            if (i < L) return false;
            int temp = arr[num][i - 1];
            for (int j = 0; j < L; j++) {
                if (visited[i - 1 - j] == 1 || temp != arr[num][i - 1 - j]) return false;
                temp = arr[num][i - 1 - j];
                visited[i - 1 - j] = 1;
            }
        }
        else if (arr[num][i] - arr[num][i - 1] > 1) {
            return false;
        }
    }
 
    return true;
}
 
int main()
{
    scanf("%d %d", &N, &L);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int num;
            scanf("%d", &num);
            arr1[i][j] = num;
            arr2[j][i] = num;
 
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        if (check(i, arr1)) ans++;
        if (check(i, arr2)) ans++;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 15683번 - 감시 (C++)  (0) 2022.09.11
[ 백준 ] 15684번 - 사다리 조작 (C++)  (0) 2022.09.10
[ 백준 ] 14891번 - 톱니바퀴 (C++)  (0) 2022.09.08
[ 백준 ] 20055번 - 컨베이어 벨트 위의 로봇 (C++)  (0) 2022.09.07
[ 백준 ] 21608번 - 상어 초등학교 (C++)  (0) 2022.09.06

+ Recent posts

티스토리툴바