백준_경사로 문제
풀이 코드
삼성 SW 역량 테스트 기출 문제 중 하나이다.
애환이 담긴 문제... 머리로는 다 풀었다고 생각했는데 테스트 케이스가 하나씩 안맞아서 몇번을 다시 짰다.
못해도 두 문제는 풀고 싶었는데, 이걸로 한참을 잡고있다가 결국 오늘은 이거 한 문제밖에 못풀었다.
# 풀이
이동할 수 있는 길은 처음에서 끝으로 갈 수 있는 길이므로, 중간에 한번이라도 이동할 수 없으면 길이 아니다.
따라서 길이 아닌 가장 큰 조건인 한 칸당 높이가 1 이상이 차이나는 길은 바로 제외시켰다.
[n][0]번째 길(row)과 [0][n]번째 길(col)은 같은 인덱스값을 지닌다.
따라서 for문을 통해 한번에 가로 길과 세로 길을 체크해 총 길의 개수를 찾았다.
여기서 길이 맞는지 아닌지 확인하는 부분이 역시 제일 오래걸렸는데,
높이가 낮은 길에서 높은 길이 나오는 것은 이전에 같은 높이를 카운트해 체크하면 된다.
하지만 높이가 높은 길에서 낮은 길이 나오면 조금 복잡해졌다.
이 경우에도 비슷하게 같은 높이를 카운트해서 체크하면 되긴 하지만 이후 경사로가 겹치는 경우가 발생하기 때문이다.
이를 위해서 경사로가 설치된 자리는 배열을 통해 체크해두고, 설치된 적이 있으면 false를 반환하도록 하였다.
# 구현 절차
rowCheck와 colCheck의 처리 과정은 동일하나 고정 값이 달라 두 개의 함수를 작성하였다.
for문을 통해road[][i], column와road[i][], row길을 체크한다.- 다음 길의 높이가 같으면
nCnt값을 증가시킨다. - 다음 길과 현재 길의 높이 차가 1 이상이면 길이 아니므로
false를 반환한다. - 다음 길이 현재 길보다 높으면 그 다음 길에 경사로를 놓을 공간이 있는지 확인한다. (
nSlide) - 경사로를 놓을 공간이 있다면 경사로가 놓이는 공간에
slide[] = 1처리를 한다. - 경사로를 놓을 공간이 없다면
false를 반환한다. - 다음 길이 현재 길보다 낮으면 이전까지 같은 길을 센
nCnt로 경사로를 놓을 공간이 있는지 확인한다. - 경사로를 놓을 공간이 있다면
slide[]를 통해 이전에 경사로가 놓인 자리인지 확인한다. - 이전에 경사로가 놓인 자리라면
false를 반환한다. - 이전에 경사로가 놓인 적이 없다면 경사로가 놓이는 공간에
slide[] = 1처리를 한다. - 모든 길을 돌 때까지 1~10을 반복한다.
# 코드
import java.util.Scanner;
public class Main {
static int[][] road;
static int nLine;
static int nSlide;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
nLine = sc.nextInt();
nSlide = sc.nextInt();
road = new int[nLine][nLine];
for(int i = 0; i < nLine; i++) {
for(int j = 0; j < nLine; j++) {
road[i][j] = sc.nextInt();
}
}
System.out.println(roadCheck());
}
public static int roadCheck() {
int nAnswer = 0;
for(int i = 0; i < nLine; i++) {
if(rowCheck(i)) nAnswer++;
if(colCheck(i)) nAnswer++;
}
return nAnswer;
}
public static boolean rowCheck(int row) {
//동일한 높이를 카운트하는 변수
int nCnt = 1;
//경사로가 설치된 적이 있는지 확인하는 배열
int[] slide = new int[nLine];
for(int i = 0; i < nLine - 1; i++) {
int nCurrent = road[row][i];
int nNext = road[row][i+1];
if(nCurrent == nNext) nCnt++;
else if(Math.abs(nCurrent-nNext) > 1) return false;
else {
if(nCurrent > nNext) {
nCnt = 1;
int j = i + 2;
while(j != nLine) {
if(nNext == road[row][j]) nCnt++;
else break;
j++;
}
if(nCnt >= nSlide) {
for(int k = i + 1; k < i + 1 + nSlide; k++) {
if(k == nLine) break;
if(slide[k] == 1) return false;
else slide[k] = 1;
}
nCnt = 1;
}else return false;
}else {
if(slide[i] == 1) return false;
if(nCnt < nSlide) return false;
else {
for(int k = i - nSlide + 1; k <= i; k++) {
if(slide[k] == 1) return false;
else slide[k] = 1;
}
nCnt = 1;
}
}
}
}
return true;
}
public static boolean colCheck(int col) {
int nCnt = 1;
int[] slide = new int[nLine];
for(int i = 0; i < nLine - 1; i++) {
int nCurrent = road[i][col];
int nNext = road[i+1][col];
if(nCurrent == nNext) nCnt++;
else if(Math.abs(nCurrent-nNext) > 1) return false;
else {
if(nCurrent > nNext) {
nCnt = 1;
int j = i + 2;
while(j != nLine) {
if(nNext == road[j][col]) nCnt++;
else break;
j++;
}
if(nCnt >= nSlide) {
for(int k = i + 1; k < i + 1 + nSlide; k++) {
if(k == nLine) break;
if(slide[k] == 1) return false;
else slide[k] = 1;
}
nCnt = 1;
}else return false;
}else {
if(slide[i] == 1) return false;
if(nCnt < nSlide) return false;
else {
for(int k = i - nSlide + 1; k <= i; k++) {
if(slide[k] == 1) return false;
else slide[k] = 1;
}
nCnt = 1;
}
}
}
}
return true;
}
}
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
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