문제
https://www.acmicpc.net/problem/14890
TC
n행에 대해 각각 n번 검사를 하고, n열에 대해 각각 n번 검사하므로 시간 복잡도는
O(N^2)
Idea
입력을 받고, 각각 행과 열의 처음을 기준으로, 끝까지 진행을 해가며 문제에 주어진 조건이 맞는지에 대한 검사를 실행하면 된다.
검사해야 될 조건은 4가지가 있다.
1) 문제에서 낮은 칸과 높은 칸의 높이 차이가 1이어야 한다는 조건이 있기 때문에
바로 앞 위치의 높이와 현재 높이의 차이가 1 이상이면 더 따질 것도 없이 False를 리턴하면 된다.
2) 현재 위치와 이전 위치를 비교해서 현 위치 < 이전 위치 라면 오른쪽을 기준으로 경사로를 놓을 수 있는 지 파악하면 되고, 현 위치 > 이전 위치 라면 왼쪽을 기준으로 경사로를 놓을 수 있는 지 파악하면 된다. 여기서 조심할 부분이 있는데 왼쪽을 기준으로 탐색할 때 시작 인덱스는 현 위치의 인덱스 -1 부터이다.
3) 경사로의 길이인 l만큼 반복문을 돌리면서 범위를 벗어나거나, 이미 경사로를 놓은 곳이거나, 칸의 높이가 다르다면 False를 리턴한다.
4) 3번 조건에 해당하지 않고 높이가 동일하다면 경사로를 놓으면 된다.
code (Python)
def pos(now):
for j in range(1, n):
# 낮은 칸과 높은 칸의 높이 차이는 1이하여야 한다.
if abs(now[j] - now[j-1]) > 1:
return False
# 현 위지 보다 이전 위치의 높이가 더 높은 경우
# 오른쪽을 기준으로 경사로 놓을 수 있는 지 파악
if now[j] < now[j-1]:
for k in range(l):
# 범위를 벗어나거나 or 이미 놓은 곳이거나 or 칸의 높이가 다르다면
if j+k >= n or used[j+k] or now[j] != now[j+k]:
return False
# 높이가 동일하다면 경사로 놓기
if now[j] == now[j+k]:
used[j+k] = True
# 현 위치가 이전 위치보다 높이가 더 높은 경우
# 왼쪽을 기준으로 경사로 놓을 수 있는 지 파악
elif now[j] > now[j-1]:
for k in range(l):
# 범위를 벗어나거나 or 이미 놓은 곳이거나 or 칸의 높이가 다르다면
if j-1-k < 0 or used[j-1-k] or now[j-1] != now[j-1-k]:
return False
if now[j-1] == now[j-1-k]:
used[j-1-k] = True
return True
# n=격자의 크기, l=경사로의 길이
n, l = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
# 지나갈 수 있는 길의 개수
result = 0
# 지나갈 수 있는 가로의 개수 구하기
for i in range(n):
used = [False for _ in range(n)]
if pos(graph[i]):
result += 1
# 지나갈 수 있는 세로의 개수 구하기
for i in range(n):
used = [False for _ in range(n)]
if pos([graph[j][i] for j in range(n)]):
result += 1
print(result)self code review
뭔가 문제도 그렇고, 세세한 조건들이 많아서 처음에는 헉...어떻게 풀지? 이랬다.
그런데 가로, 세로 나눠서 하나하나 조건대로 로직을 작성하니 그냥 시뮬레이션 문제로 생각보다
어렵지 않던 문제였다.
조금 나이스!한 코드라고 생각하는 부분은, 세로 개수 구할 때 pos함수를 호출하며 list comprehension을 사용한 부분과 pos함수 부분은 개인적으로 깔끔하게 잘 작성했다고 생각한다.
