경사로
문제 : https://www.acmicpc.net/problem/14890 (opens in a new tab)
내 풀이
풀이도 더럽고 풀었는데 기쁘지 않다... 푸는데 2시간 정도 걸린것 같다.
조건이 어떤식으로 걸리는지 몰라서 자꾸 조건을 걸고 풀고를 반복했는데 이게 단순한 구현능력의 문제인지 모르겠다.
N, L = map(int, input().split())
graph = []
for _ in range(N):
line = list(map(int, input().split()))
graph.append(line)
'''
바로 뒤 칸부터 들어와야함
'''
def check_column(v, d, visited) :
lc = 0
r, c = v
nc = c
if visited[nc] :
return False, visited
while -1 < nc < N :
visited[nc] = True
lc += 1
if lc == L :
return True, visited
nc += d
# 경사가 달라졌거나 이미 경사가 깔렸었으면
if -1 < nc < N :
if graph[r][nc] != graph[r][c] or visited[nc] :
return False, visited
else :
break
return False, visited
def check_row(v, d, visited) :
lc = 0
r, c = v
nr = r
if visited[nr] :
return False, visited
while -1 < nr < N :
visited[nr] = True
lc += 1
if lc == L :
return True, visited
nr += d
# 경사가 달라졌거나 이미 경사가 깔렸었으면
if -1 < nr < N :
if graph[nr][c] != graph[r][c] or visited[nr] :
return False, visited
else :
break
return False, visited
def main(graph):
cnt = 0
for r in range(N):
prev = 0
visited = [False for _ in range(N)]
for c in range(N):
if graph[r][c] == graph[r][prev] :
pass
elif graph[r][c] - 1 == graph[r][prev] : # 한 칸 올라간 경우
result, visited = check_column([r,c - 1], -1, visited)
if result :
prev = c
else :
break
elif graph[r][c] + 1 == graph[r][prev] : # 한 칸 내려간 경우
result, visited = check_column([r,c], 1, visited)
if result :
prev = c
else :
break
else :
break
# break 안당하고 마지막까지 왓으면 cnt 1 증가
if c == N - 1 :
cnt += 1
for c in range(N):
prev = 0
visited = [False for _ in range(N)]
for r in range(N):
if graph[r][c] == graph[prev][c] :
pass
elif graph[r][c] - 1 == graph[prev][c] : # 한 칸 올라간 경우
result, visited = check_row([r - 1,c], -1, visited)
if result :
prev = r
else :
break
elif graph[r][c] + 1 == graph[prev][c] : # 한 칸 내려간 경우
result, visited = check_row([r,c], 1, visited)
if result :
prev = r
else :
break
else :
break
# break 안당하고 마지막까지 왓으면 cnt 1 증가
if r == N - 1 :
cnt += 1
return cnt
print(main(graph))
다른 사람 풀이
import sys
N, L = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def check(line, L):
# 경사로 생기는 곳 체크
visited = [False for _ in range(N)]
# 자리 차례로 탐색
for i in range(0, N-1):
# 바로 다음 위치의 높이가 같으면 continue
if line[i] == line[i+1]:
continue
# 다음 위치의 높이 차이가 1 넘게 나면 False
elif abs(line[i]-line[i+1]) > 1:
return False
# 현재 높이가 다음 높이 보다 높으면 오른쪽 높이가 같은지 체크
elif line[i] > line[i+1]:
temp = line[i+1] # 다음 높이
for j in range(i+1, i+L+1):
# 경사 길이가 범위 안이면
if 0 <= j < N:
# 경사 놓을 위치의 높이가 하나라도 다르면
if temp != line[j]:
return False
# 높이는 다 같은데 이미 경사가 놓여진 곳이면
elif visited[j]:
return False
# 경사 놓기
visited[j] = True
# 경사 길이가 범위 벗어나면
else:
return False
# 다음 높이가 현재 높이 보다 높으면 왼쪽 높이가 같은지 체크
else:
temp = line[i]
for j in range(i, i-L, -1):
# 경사 길이가 범위 안이면
if 0 <= j < N:
# 경사 놓을 위치의 높이가 하나라도 다르면
if temp != line[j]:
return False
# 높이는 다 같은데 이미 경사가 놓여진 곳이면
elif visited[j]:
return False
# 경사 놓기
visited[j] = True
# 경사 길이가 범위 벗어나면
else:
return False
return True
answer = 0
# 가로 길 체크
for i in board:
if check(i, L):
answer += 1
# 세로 길을 체크하기 위해 변환해서 넣어줌
for i in range(N):
temp = []
for j in range(N):
temp.append(board[j][i])
if check(temp, L):
answer += 1
print(answer)