0514_백준 14890번/경사로_파이썬

"가로 세로 모두 확인해야 함, zip으로 전치행렬 활용"

새로 써본 것은 ziiiiiiip!

[풀이 과정]

- 특별한 알고리즘 없이 주어진 조건을 빠짐없이 고려하여 푸는 문제

 

- 가로행, 세로열 두번 탐색해야 해서 -> zip 함수 활용

  zip(*iterable)은 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수

 

- 내가 고려한 조건들은 아래와 같다.

① 경사로를 놓는 방법을 크게 '높은 곳에서 낮은 곳으로 향하는 것', '낮은 곳에서 높은 곳으로 향하는 것' 두 가지로 나눔. 그리고 경사 높이 차이를 비교 -> 1차이가 나는지 확인

② 범위를 벗어나지 않게 인덱스 위치 확인

③ 경사로를 놓았는지 확인해주기 위해 visit 배열 활용

 

- 한 행, 한 열씩 돌아가며 길이 되는지 확인하는데 이때 한줄을 모두 넘어가면 'check = 1' 곧, 길이 된다는 것을 의미(cnt += 1) 'check = 0'은 길X

 

[코드 구현]

def search(arr):
    global cnt
    for i in range(N):
        j = 0
        check = 1
        while j < N - 1:
            if arr[i][j] == arr[i][j+1]:
                j += 1
                continue
                
            # 높은 곳에서 낮은 곳으로 향하는 경사로
            elif arr[i][j] - arr[i][j+1] == 1:
                if arr[i][j+1:j+1+L].count(arr[i][j+1]) == L:
                    visit[i][j+1:j+1+L] = [1]*L
                    j = j+L
                    continue
                else:
                    check = 0
                    break
            # 낮은 곳에서 높은 곳으로 향하는 경사로
            elif arr[i][j] - arr[i][j+1] == -1:
                if arr[i][j+1-L:j+1].count(arr[i][j])==L and True not in visit[i][j+1-L:j+1]:
                    visit[i][j+1-L:j+1] = [1]*L
                    j += 1
                    continue
                else:
                    check = 0
                    break
            else:
                check = 0
                break

        if check == 1:
            cnt += 1

N, L = map(int, input().split())
arr_garo = [list(map(int, input().split())) for _ in range(N)]
arr_sero = list(map(list, list(zip(*arr_garo))))
cnt = 0
visit = [[0]*N for _ in range(N)]
search(arr_garo)
visit = [[0]*N for _ in range(N)]
search(arr_sero)
print(cnt)

[문제 출처]

백준 14890번 경사로 https://www.acmicpc.net/problem/14890

14890번: 경사로

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.