Easy is Perfect

[백준] 14890번 C/C++ 풀이 _ 경사로

  • melonicedlatte
  • Mar 25, 2018


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

경사로 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초512 MB92744234047.486%

문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 

다음과 같은 N=6인 경우 지도를 살펴보자.

이 때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

  • 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
  • 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
  • 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

  • 경사로를 놓은 곳에 또 경사로를 놓는 경우
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
  • 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
  • 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 초록색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

예제 입력 

6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

예제 출력 

3

예제 입력 2 

6 2
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

예제 출력 2 

7

예제 입력 3 

6 3
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

예제 출력 3 

3

예제 입력 4 

6 1
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

예제 출력 4 

11

힌트

예제 2의 경우 아래와 같은 초록색 길을 지나갈 수 있다.

예제 3의  경우에는 아래와 같은 초록색 길이 지나갈 수 있는 길이다.

마지막으로, 예제 4의 경우에는 아래와 같은 초록색 길이 지나갈 수 있는 길이다.

출처























































































문제 해설 

문제 자체가 어려운 알고리즘이나 시간 복잡도를 생각해야 하는 문제가 아니라 그냥 구현이 어려운 문제 같다. 
구현을 하는데 코드가 너무 길게 나왔다. 

중간에 짜잘한 오류도 많고.... 풀었지만 시간이 너무 많이 걸려 실제 시험에 나왔으면 그냥 틀렸다고 보면 된다. 


먼저 가로를 검사하고 세로를 따로 검사하면 되는 방식이다. 
내 풀이는 추천할 만한 풀이는 아닌 것 같다.
먼저 내 풀이는 for문 안에 다 넣으려고 해서 너무 복잡하다. 
반드시 메소드로 분리하자. 

또, 다른 풀이들은 로우와 컬럼을 계산하는 부분을 따로 둔 것이 아니라 행렬의 트랜스포즈를 썼다.

컬럼의 트랜스포즈는 로우이기 때문이다. 

그 이외에 핵심은 경사로를 왼쪽(위쪽) 기준으로 놓을지 오른쪽(아래쪽) 기준으로 놓는다는 것이다.(차이가 1 만큼 날 때) 


그 이외의 설명은 주석으로 첨부한다. 

https://www.acmicpc.net/source/7070871

이 풀이가 굉장히 간단하게 짠 풀이인데, 참고해보면 좋다고 생각한다. 



교훈

- 가로 세로가 있을 때, 인덱스를 설정할 때 변수로 앞에서 선언해서 바뀌더라도 하나만 바뀌게 하자. 
- 가로 세로를 하나의 함수로 만들어서 처리하자. 
- 가로를 만들어 놓은 게 있으면, 동일한 배열을 생성하여 T (트랜젝션)을 해서 사용했으면 동일했을 것이다. 
- 최대한 함수로 빼서 flag 를 사용하지 말자. (for문이 계속 겹치면서 헷갈림)



이전에는 이렇게 풀었지만 다시는 이렇게 풀지 않을 것 같다.....
짧은 소스코드도 함께 참고해보자... 

아래와 같이 짜야 된다는 교훈을 얻었습니다. ..


숏코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
int main() {
    int n, l, ans = 0, i, j, c;
    short a[200][100];
    scanf("%d %d", &n, &l);
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            scanf("%hd", &a[i][j]);
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            a[i + n][j] = a[j][i];
    for (i=0; i<n * 2; i++) {
        c = 1;
        for (j=0; j<n - 1; j++) {
            if (a[i][j] == a[i][j + 1]) c++;
            else if (a[i][j] + 1 == a[i][j + 1] && c >= l) c = 1;
            else if (a[i][j] - 1 == a[i][j + 1] && c >= 0) c = -l + 1;
            else break;
        }
        if (j == n - 1 && c >= 0) ans++;
    }
    printf("%d", ans);
    return 0;
}
cs



이전에 짰던 소스코드

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
 
int N, L;
int arr[100][100];
//  (가로는 3축이 0 세로는 1)
int isUsed[100][100][2];
int answer = 0; 
 
int main() {
    // 정보 입력 
    cin >> N >> L;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &arr[i][j]);
 
    int LNum = 0; 
    int i, j; int isSlide, isOver;
 
 
    // 로우 확인
    for (i = 0; i < N; i++) {
        int before_num = arr[i][0];
        isOver = 0;
        for (j = 1; j < N; j++) {
            if (isOver) break;
            // 이전 숫자와 같으면 continue
            if (before_num == arr[i][j]) continue;
 
            // 이전 숫자와 2이상 차이나면 break;
            else if (abs(before_num - arr[i][j]) >= 2) { 
                isOver = 1;
                break;
            }
 
            // 1 차이나면 앞 뒤를 구분하고 L 만큼 있는지 확인
            // 뒤에가 1만큼 더 크면 앞을 살핀다. 
            else if (before_num == arr[i][j] - 1) { 
                isSlide = 1;
                // L 만큼 살펴본다. 
                for (int t = 0; (t < L) && (isSlide); t++) {
                    // 인덱스를 벗어나거나 사용한 인덱스이면 종료 
                    if ((j - (t+1) < 0) || (isUsed[i][j - (t + 1)][0])) {
                        isSlide = 0;
                        isOver = 1;
                        break;
                    }
                    // 비교하는 숫자와 다르면 답이 아님 
                    if (arr[i][j - (t + 1)] != before_num) {
                        isSlide = 0;
                        isOver = 1;
                        break;
                    }
                    // 경사로로 사용 (가로는 3축이 0 세로는 1)
                    isUsed[i][j - (t + 1)][0] = 1;
                }
            }
            // 앞이 1만큼 더 크면 뒤를 살핀다. 
            else {
                // j 한칸 증가
                isSlide = 1;
                // L 만큼 살펴본다. 
                for (int t = 0; (t < L) && (isSlide) ; t++) {
                    // 인덱스를 벗어나거나 사용한 인덱스이면 종료 
                    if ((j + t == N)|| (isUsed[i][j + t][0])) {
                        isSlide = 0;
                        isOver = 1;
                        break;
                    } 
                    // 비교하는 숫자와 차이가 1만 나야됨 
                    if (arr[i][j + t] != before_num-1) { 
                        isSlide = 0;
                        isOver = 1;
                        break;
                    }
                    // 경사로로 사용 (가로는 3축이 0 세로는 1)
                    isUsed[i][j + t][0] = 1 ;
                }
                if (isSlide && !isOver ) j += (L-1);
            }
 
            if (isSlide) {
                before_num = arr[i][j]; 
            }
 
        }
        if (!isOver)
            answer++;
    }
 
 
 
 
    // 컬럼 확인
    for (j = 0; j < N; j++) {
        int before_num = arr[0][j];
        isOver = 0;
        for (i = 1; i < N; i++) {
            if (isOver) break;
            // 이전 숫자와 같으면 continue
            if (before_num == arr[i][j]) continue;
 
            // 이전 숫자와 2이상 차이나면 break;
            else if (abs(before_num - arr[i][j]) >= 2) {
                isOver = 1;
                break;
            }
 
            // 1 차이나면 앞 뒤를 구분하고 L 만큼 있는지 확인
            // 뒤에가 1만큼 더 크면 앞을 살핀다. 
            else if (before_num == arr[i][j] - 1) {
                isSlide = 1;
                // L 만큼 살펴본다. 
                for (int t = 0; (t < L) && (isSlide); t++) {
                    // 인덱스를 벗어나거나 사용한 인덱스이면 종료 
                    if ((i - (t + 1) < 0) || (isUsed[i - (t + 1)][j][1])) {
                        isSlide = 0;
                        isOver = 1;
                        break;
                    }
                    // 비교하는 숫자와 다르면 답이 아님 
                    if (arr[i - (t + 1)][j] != before_num) {
                        isSlide = 0;
                        isOver = 1;
                        break;
                    }
                    // 경사로로 사용 (가로는 3축이 0 세로는 1)
                    isUsed[i - (t + 1)][j][1] = 1;
                }
            }
            // 앞이 1만큼 더 크면 뒤를 살핀다. 
            else {
                // j 한칸 증가
                isSlide = 1;
                // L 만큼 살펴본다. 
                for (int t = 0; (t < L) && (isSlide); t++) {
                    // 인덱스를 벗어나거나 사용한 인덱스이면 종료 
                    if ((i + t == N) || (isUsed[i + t][j][1])) {
                        isSlide = 0;
                        isOver = 1;
                        break;
                    }
                    // 비교하는 숫자와 차이가 1만 나야됨 
                    if (arr[i + t][j] != before_num - 1) {
                        isSlide = 0;
                        isOver = 1;
                        break;
                    }
                    // 경사로로 사용 (가로는 3축이 0 세로는 1)
                    isUsed[i + t][j][1] = 1;
                }
                if (isSlide && !isOver) i += (L - 1);
            }
 
            if (isSlide) {
                before_num = arr[i][j];
            }
 
        }
        if (!isOver)
            answer++;
    }
 
    cout << answer;
 
 
    return 0;
}
cs



Search