중요 포인트:
1) 경사로를 만들 때, maps의 값을 직접 수정하지 않고 visited 리스트를 새로 생성하여 경사로 설치 유무를 따로 저장하기
2) 가로 길 확인 후 세로 길 확인 시 가로 길에 설치한 경사로가 영향을 주면 안됨 (visited 배열 두개 사용해서 해결)
3) 경사가 올라가는 경우와 내려가는 경우의 기준 인덱스가 다르므로 인덱스 오류에 특히 주의
maps = []
n, l = map(int, input().split())
for i in range(0, n):
line = list(map(int, input().split()))
maps.append(line)
cnt = 0 # 지나갈 수 있는 길 개수 카운팅할 변수
# 경사로 설치한 좌표에 True로 저장할 리스트
visited = [] # 가로 길 용
for i in range(0, n):
visited.append([False] * n)
visited_2 = [] # 세로 길 용
for i in range(0, n):
visited_2.append([False] * n)
# ------- 가로 길 확인
for i in range(0, n):
idx = 0
while idx <= n - 1:
# 길의 끝에 도달 시 cnt += 1
if idx == n - 1:
cnt += 1
break
# 높이가 같으면 지나가기
if maps[i][idx] == maps[i][idx + 1]:
idx += 1
# --- 경사가 올라가는 경우
# 높이가 1 커졌다면 - 현재 있는 낮은 칸의 수(경사아님) >= L 이어야 하고, 현재 낮은 칸의 높이가 같다면 경사로 놓고 지나가기
elif maps[i][idx] + 1 == maps[i][idx + 1]:
is_possible = True
# 경사로를 깔 길 확인 (0 ~ l - 1까지)
for j in range(0, l):
# 길을 벗어나면
if idx - j < 0:
is_possible = False
break
# 길이 평탄하지 않다면 (올라가는 경우는 idx 기준으로)
if maps[i][idx - j] != maps[i][idx]:
is_possible = False
break
# 이미 경사로 깔려있으면
if visited[i][idx - j] == True:
is_possible = False
break
# 경사로를 깔 수 있는 상태라면
if is_possible:
# 경사로 깔기
for j in range(0, l):
visited[i][idx - j] = True
# 다음 칸으로 이동
idx += 1
# 경사로 깔 수 없다면 다음 길로 넘어가기
else:
break
# ---- 경사가 내려가는 경우
# 높이가 1 작아졌다면 - 작아진 부분부터 있는 낮은 칸의 수(경사아님) >= L이어야 하고, 낮은 칸 높이가 모두 같다면 경사로 놓고 지나가기
elif maps[i][idx] - 1 == maps[i][idx + 1]:
is_possible = True
# 경사로를 깔 길 확인 (1 ~ l까지)
for j in range(1, l + 1):
# 길을 벗어나면
if idx + j >= n:
is_possible = False
break
# 길이 평탄하지 않다면 (내려가는 경우는 낮은 쪽을 기준으로 비교해야함 주의!!!)
if maps[i][idx + j] != maps[i][idx + 1]:
is_possible = False
break
# 이미 경사로 깔려있으면
if visited[i][idx + j] == True:
is_possible = False
break
# 경사로를 깔 수 있는 상태라면
if is_possible:
# 경사로 깔기
for j in range(1, l + 1):
visited[i][idx + j] = True
# 경사를 지나 다음 칸으로 이동
idx += l
# 경사로 깔 수 없다면 다음 길로 넘어가기
else:
break
# 아니면 break
else:
break
# -------- 세로 길 확인 (visited_2 사용)
for i in range(0, n):
idx = 0
while idx <= n - 1:
# 길의 끝에 도달 시 cnt += 1
if idx == n - 1:
cnt += 1
break
# 높이가 같으면 지나가기
if maps[idx][i] == maps[idx + 1][i]:
idx += 1
# ---- 경사가 올라가는 경우
# 높이가 1 커졌다면 - 현재 있는 낮은 칸의 수(경사아님) >= L 이어야 하고, 현재 낮은 칸의 높이가 같다면 경사로 놓고(좌표+0.5하기) 지나가기
elif maps[idx][i] + 1 == maps[idx + 1][i]:
is_possible = True
# 경사로를 깔 길 확인 (0 ~ l - 1까지)
for j in range(0, l):
# 길을 벗어나면
if idx - j < 0:
is_possible = False
break
# 길이 평탄하지 않다면 (올라가는 경우는 현재 idx 기준으로 비교)
if maps[idx - j][i] != maps[idx][i]:
is_possible = False
break
# 이미 경사로 깔려있으면
if visited_2[idx - j][i] == True:
is_possible = False
break
# 경사로를 깔 수 있는 상태라면
if is_possible:
# 경사로 깔기
for j in range(0, l):
visited_2[idx - j][i] = True
# 다음 칸으로 이동
idx += 1
# 경사로 깔 수 없다면 다음 길로 넘어가기
else:
break
# ---- 경사가 내려가는 경우
# 높이가 1 작아졌다면 - 작아진 부분부터 있는 낮은 칸의 수(경사아님) >= L이어야 하고, 낮은 칸 높이가 모두 같다면 경사로 놓고(좌표+0.5) 지나가기
elif maps[idx][i] - 1 == maps[idx + 1][i]:
is_possible = True
# 경사로를 깔 길 확인 (1 ~ l까지)
for j in range(1, l + 1):
# 길을 벗어나면
if idx + j >= n:
is_possible = False
break
# 길이 평탄하지 않다면 (내려가는 경우는 낮은 쪽을 기준으로 비교해야 함 주의!!!)
if maps[idx + j][i] != maps[idx + 1][i]:
is_possible = False
break
# 이미 경사로 깔려있으면
if visited_2[idx + j][i] == True:
is_possible = False
break
# 경사로를 깔 수 있는 상태라면
if is_possible:
# 경사로 깔기
for j in range(1, l + 1):
visited_2[idx + j][i] = True
# 다음 칸으로 이동
idx += l
# 경사로 깔 수 없다면 다음 길로 넘어가기
else:
break
# 아니면 break
else:
break
print(cnt)
