14890. 경사로 문제 바로가기
※ 문제 풀 때 헷갈렸던 점!
행에서 경사로를 사용한 위치에 열일 때도 경사로를 사용해도 된다!
즉 행일 때 열일 때 경사로의 유무는 별개였다!
해결 방법
구현 과정
1. 행에서 갈 수 있는 길을 탐색한다.
rowCheck함수를 통해 각 행별로 row 리스트에 연속한 수가 몇 개 인지 저장한다.
각 row에 대해
roadCheck함수를 통해 길이 될 수 있는지 확인한다.row의 길이가 1이면 행의 전체가 모두 같은 높이기에 answer에 +1을 한다.
row의 길이가 1이 아니면 (row 리스트의 길이 - 1)만큼 for문을 통해 row[i]와 row[i + 1]을 비교한다.
이후 밑에 나와있는 3가지 조건을 모두 만족할 때 answer에 1을 더한다. 하나라도 만족하지 못하면 return을 통해 종료시킨다.
abs(row[i] - row[i + 1])이 1인 경우
낮은 칸과 높은 칸의 차이가 1인 경우이기에 길이 될 수 있다.
낮은 수의 칸의 개수가 L보다 크거나 같은 경우
경사로를 놓을 위치를 add 리스트에 추가한다.
경사로를 놓을 위치가 add 리스트에 없는 경우
경사로가 이미 놓아있는 경우 return한다. → 경사로를 놓은 곳에 경사로를 놓을 수 없기 때문이다.
2. 열에서 갈 수 있는 길을 /탐색한다.
colCheck함수를 통해 각 행별로 col리스트에 연속한 수가 몇 개 인지 저장한다.각 col에 대해
roadCheck함수를 통해 길이 될 수 있는지 확인한다.위에서 설명한
roadCheck함수의 동작 과정과 동일하다.col의 길이가 1이면 열의 전체가 모두 같은 높이기에 answer에 +1을 한다.
col의 길이가 1이 아니면 (col 리스트의 길이 - 1)만큼 for문을 통해 col[i]와 col[i + 1]을 비교한다.
이후 밑에 나와있는 3가지 조건을 모두 만족할 때 answer에 1을 더한다. 하나라도 만족하지 못하면 return을 통해 종료시킨다.
abs(col[i] - col[i + 1])이 1인 경우
낮은 칸과 높은 칸의 차이가 1인 경우이기에 길이 될 수 있다.
낮은 수의 칸의 개수가 L보다 크거나 같은 경우
경사로를 놓을 위치를 add 리스트에 추가한다.
경사로를 놓을 위치가 add 리스트에 없는 경우
경사로가 이미 놓아있는 경우 return한다. → 경사로를 놓은 곳에 경사로를 놓을 수 없기 때문이다.
구현한 코드
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
def roadCheck(road): # 길이 가능한지 탐색하는 함수
global answer, L
add = [] # 경사로를 추가할 위치를 저장할 리스트
if len(road) == 1: # 길이 가능한 경우
answer += 1
return
else:
idx = -1
for r in range(len(road) - 1):
idx += road[r][1]
# 낮은 칸과 높은 칸 차이가 1인 경우
if road[r][0] - road[r + 1][0] == 1:
if road[r + 1][1] >= L: # 낮은 칸에 L개의 경사로 놓을 수 있는 경우
for i in range(idx + 1, idx + 1 + L):
if i in add: # 경사로를 놓은 곳에 경사로를 놓는 경우 => 길 불가능
return
else:
add.append(i)
else:
return
# 낮은 칸과 높은 칸 차이가 1인 경우
elif road[r][0] - road[r + 1][0] == -1:
if road[r][1] >= L: # 낮은 칸에 L개의 경사로 놓을 수 있는 경우
for i in range(idx, idx - L, -1):
if i in add: # 경사로를 놓은 곳에 경사로를 놓는 경우 => 길 불가능
return
else:
add.append(i)
else:
return
else: # 길이 될 수 없는 경우
return
answer += 1
def rowCheck(N): # 행에 대한 정보를 저장하는 함수
# 각 행에 대해서 연속된 수(num)가 몇개(cnt)인지 정보를 저장한다.
for r in range(N):
cnt = 0 # 연속된 숫자의 개수를 세는 변수
num = -1 # board의 숫자를 저장하는 변수
row = [] # [num, cnt]에 대한 각 행의 정보를 저장할 이중 리스트
for c in range(N):
if num == -1:
num = board[r][c]
cnt = 1
elif num == board[r][c]: # 같은 수인 경우(연속된 같은 수)
cnt += 1
else: # 다른 수인 경우
row.append([num, cnt])
num = board[r][c]
cnt = 1
if num != -1:
row.append([num, cnt])
roadCheck(row) # 길이 가능한지 탐색하는 함수
def colCheck(N): # 열에 대한 정보를 저장하는 함수
# 각 열에 대해서 연속된 수(num)가 몇개(cnt)인지 정보를 저장한다.
for c in range(N):
cnt = 0 # 연속된 숫자의 개수를 세는 변수
num = -1 # board의 숫자를 저장하는 변수
col = [] # [num, cnt]에 대한 각 행의 정보를 저장할 이중 리스트
for r in range(N):
if num == -1:
num = board[r][c]
cnt = 1
elif num == board[r][c]: # 같은 수인 경우(연속된 같은 수)
cnt += 1
else: # 다른 수인 경우
col.append([num, cnt])
num = board[r][c]
cnt = 1
if num != -1:
col.append([num, cnt])
roadCheck(col) # 길이 가능한지 탐색하는 함수
N, L = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
answer = 0
# 행에서 가능한 길 찾기
rowCheck(N)
# 열에서 가능한 길 찾기
colCheck(N)
print(answer)