[코테 - py] 백준 14890번 경사로

오늘은 삼성 기출 문제인 경사로 문제를 풀어보았다.

 

단순 구현이지만 매우 복잡해서 함수로 분리해서 설계했다.

 

N, L = map(int, input().split())

graph = []

for i in range(N):
    data = list(map(int, input().split()))
    graph.append(data)

# 가능한 길
def solution(t, visi, a):
    for i in range(len(t)-1):
        if abs(t[i]-t[i+1]) == 1:
            """
            1. 오른쪽이 왼쪽보다 더 작을 때
            2. 왼쪽이 오른쪽보다 더 작을 때
            """
            if (t[i] > t[i+1]):
                cur = t[i+1]
                route = []
                for j in range(i+1,len(t)):
                    if len(route) == L:
                        for dr, dc in route:
                            if visi[dr][dc] is True:
                                return False
                            else:
                                visi[dr][dc] = True
                        break
                    elif t[j] == cur:
                        route.append((a, j))
                    else:
                        return False
                if len(route) < L:
                    return False
            elif (t[i] < t[i+1]):
                cur = t[i]
                route = []
                for j in range(i, -1, -1):
                    if len(route) == L:
                        for dr, dc in route:
                            if visi[dr][dc] is True:
                                return False
                            else:
                                visi[dr][dc] = True
                        break
                    elif t[j] == cur:
                        route.append((a, j))
                    else:
                        return False
                if len(route) < L:
                    return False

        elif abs(t[i]-t[i+1]) > 1:
            return False

    return True


def solve(gra):
    result = 0
    for i in range(N):
        visited = [[False for _ in range(N)] for _ in range(N)]
        temp = gra[i]
        if solution(temp, visited, i) is True:
            result += 1

    return result


final = 0

final += solve(graph)
t_g = list(map(list, zip(*graph)))
final += solve(t_g)


print(final)

 

 

여기서 배운 점은!

- 2차원 리스트에서 행과열을 바꿀 때 zip을 이용하면 간편하다. -> 근데 실행시간이 좀더 오래걸리는듯..!

graph = [[1, 2, 3, 4],[5, 6, 7, 8]]

temp_graph = list(map(list, zip(*graph)))

print(temp_graph) # [[1, 5], [2, 6], [3, 7], [4, 8]]

 

- 복잡한 구현문제는 함수를 나눠서 블럭처럼 구성하자!

<크게 설계> - <중간설계 > - <작게 설계> 순으로