[코테준비] 6. 백준- 경사로(14890) python "삼성 SW 역량 테스트 기출 문제"

경사로

• 링크:https://www.acmicpc.net/problem/14890
• 난이도:골드 3
• 분류: 구현
• 직접 푼 여부: X (요즘 시간이 없어서 그냥 문제를 보고, 바로 풀이를 본다. 대신 코드를 쓸 때는 내 스타일대로, 바꾸고 주석을 많이 쓴다.)
• 언어: 파이썬

풀이 노트

• [1] 우선, 길을 가로/세로만 갈 수 있으니 각각을 따로 확인하면 된다.
  • 여기서 세로 길을 확인할 때 필요한 "열"만 list를 가져오는 방법은 다른 곳에서도 많이 쓸 것 같으니 몰랐다면, 메모해 두자.

for i in range(n):
	column = [array[j][i] for j in range(n)]

• [2] 각 길을 확인하며 못 가는 경우를 생각해 보자
  • 1. 높이차이가 1 이상이면, 바로 탈락
  • 2. 경사로를 설치할 때,
    • (1) 범위를 벗어나거나 (2) 이미 경사로를 설치했거나 (3) 설치하고자 한 곳과 그전 것과 비교해서 높이가 다르면 탈락

사실 코드에 주석을 많이 달아놔서 그것을 보고 이해하는 게 더 쉬울 수도 있다! 

코드

#참고: https://unie2.tistory.com/m/977
import sys
input = sys.stdin.readline

# input 받기
n, l = map(int, input().split())
mapp = [list(map(int, input().split())) for _ in range(n)]

# 갈 수 있는 길인지 check
def check(line):
    # line: 현재보고 있는 길 1자
    global l
    for i in range(1,n): # 1~n-1 (앞에꺼랑 비교하려고 0뺌)
        if abs(line[i]-line[i-1]) > 1:
            #차이가 1보다 크면 못감
            return False
        
        if line[i] < line[i-1]:
            # 현재가 이전보다 낮으면, 오른쪽 살펴봐야함
            for k in range(l):
                if i+k >=n or used[i+k] or line[i] != line[i+k]:
                    # (1)범위를 벗어나거나 (2)이미 경사로를 설치했거나 (3)높이가 다르면 못감
                    return False
                if line[i] == line[i+k]:
                    # 높이가 같으면 방문처리. 결국 설치를 못하는 경우라면, 위에서 loop을 돌며 위에서 걸려서 false
                    used[i+k] = True
        elif line[i]> line[i-1]:
            #현재가 전보다 높으면, 왼쪽을 봐야함 (현재는 높으니까 경사막 설치 X. 전거랑 그 전것 비교해야함)
            for k in range(l):
                if i-k-1 <0 or used[i-k-1] or line[i-1] !=line[i-k-1]:
                    return False
                if line[i-1] == line[i-k-1]:
                    used[i-k-1]= True
                    
    return True #다 통과했으면, 길 갈 수 있음

#문제 풀기
result =0
# 가로확인
for i in range(n):
    used = [False for _ in range(n)]
    if check(mapp[i]):
        result+=1

    
#세로확인
for i in range(n):
    used = [False for _ in range(n)]
    if check([mapp[j][i] for j in range(n)]): # 열만 뽑아내는 법!
        result +=1
        
print(result)