백준 14890 경사로 (Python)

크기가 N * N 인 지도에서 각 행과 열마다 길을 놓을 수 있을 때 조건에 맞게 만들 수 있는 길의 개수를 구하는 문제입니다.

길이 완성되는 조건은 다음과 같습니다.

• 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같아야 합니다.
• 높이가 차이나는 길은 경사로를 놓아서 길을 만들 수 있습니다. (경사로의 높이는 항상 1입니다.)
• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야합니다.
• 낮은 칸과 높은 칸의 높이 차이는 무조건 1이어야 합니다.
• 경사로를 놓을 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 합니다.

경사로를 놓을 수 있는 경우

경사로를 놓을 수 없는 조건은 다음과 같습니다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

경사로를 놓을 수 없는 경우

 

풀이

이러한 문제를 풀 때 저와 같은 경우 행과 열 중 한 부분에 대해서 해결을 한 뒤, 행과 열만 바꾸어서 다른 쪽에 대입해서 문제를 풀고 있습니다. 이번 문제 또한 행에 대해 조건을 대입해본 뒤, 이를 열에 대입하여 문제를 해결하였습니다.

 

0. 필요한 변수

board # 문제에서 주어진 지도
current # 현재 칸의 높이를 저장합니다.
t # 값이 증가하는 인덱스를 뜻합니다. 
length #  현재 경사로를 놓을 수 있는 길이
lowLength # 현재 높이보다 낮은 구간에서 경사로를 놓을 수 있는 구간의 길이를 저장합니다.

 

1. 두 칸의 높이가 2이상 차이나는 경우

경사로의 높이는 1이므로 두 칸의 높이가 2인 길은 경사로를 놓을 수 없으므로 지나갈 수 없는 길입니다.

 

2. 두 칸의 높이가 같을 경우

두 칸의 높이가 같다면 지나갈 수 있는 길이므로, 경사로를 놓을 수 있는 길이를 +1 해주고 t를 1 증가시켜줍니다.

 

3. 현재 칸보다 높이가 1 높은 칸일 경우

두 칸의 높이가 1차이난다면 경사로를 놓아 길을 지나갈 수 있습니다.

현재까지 측정한 경사로를 놓을 수 있는 길이(length)가 문제에서 주어진 경사로 길이(L) 보다 작다면 경사로를 놓을 수 없으므로 지나갈 수 없는 길입니다.

length가 L보다 크거나 같다면 경사로를 놓아 지나갈 수 있는 길입니다. current= board[i][t], length = 1로 초기화, t를 +1 해줍니다.

 

4. 현재 칸보다 높이가 1 낮은 칸일 경우

제가 푼 방식에서 이 파트가 하이라이트라고 생각합니다. 높이가 1 높은 칸을 마주할 경우 현재까지 length길이를 비교해 지나갈 수 있는 길인지 확인하면 되지만, 현재 칸보다 높이가 1 낮은 칸일 경우 경사로를 놓을 수 있는 길이를 이 후에 측정을 해서 확인해야 되기 때문입니다.

 

저와 같은 경우 current를 현재 칸의 높이로 바꾼 뒤, lowLength 변수를 활용하여 현재 칸의 높이와 같은 높이를 가진 연속된 칸의 개수를 구해주었습니다.

 

만약 lowLength가 L보다 작다면 경사로를 놓을 수 없는 길이므로 지나갈 수 없으므로 함수를 종료해줍니다.

만약 lowLength가 L보다 크거나 같고 t==N까지 도달했다면 현재 높이가 끝까지 이어진다는 뜻이므로 지나갈 수 있는 길입니다.

만약 위의 경우에 모두 만족하지 않는다면, 현재까지는 지나갈 수 있는 길이며, 아직 길을 더 확인해보아야 된다는 뜻입니다. 그러므로 현재 경사로를 놓을 수 있는 길이(length)를 lowLength-L로 두고 위의 조건들을 다시 확인해주어야 합니다.

 

 

다음은 행에 대해서만 위의 조건들로 코드를 작성해본 것입니다.

def doRow(i, j):
    global answer
    current = board[i][j]
    t = j+1
    length = 1
    while t < N:
        if abs(board[i][t]-current) > 1:
            return
        elif board[i][t] == current:
            length += 1
            t += 1
        elif board[i][t] > current:
            if length < L:
                return

            current = board[i][t]
            length = 1
            t += 1
        else:
            current = board[i][t]
            lowLength = 0
            while t < N and board[i][t] == current:
                lowLength += 1
                t += 1

            if lowLength < L:
                return

            if t == N:
                break

            length = lowLength-L

    answer += 1

 

다음은 열에 대한 코드입니다.

def doColumn(i, j):
    global answer
    current = board[j][i]
    t = j+1
    length = 1
    while t < N:
        if abs(board[t][i]-current) > 1:
            return
        elif board[t][i] == current:
            length += 1
            t += 1
        elif board[t][i] > current:
            if length < L:
                return

            current = board[t][i]
            length = 1
            t += 1
        else:
            current = board[t][i]
            lowLength = 0
            while t < N and board[t][i] == current:
                lowLength += 1
                t += 1

            if lowLength < L:
                return

            if t == N:
                break

            length = lowLength-L

    answer += 1

 

확인을 해보면 두 메서드가 행과 열 자리만 바뀌고 모두 동일한 형태임을 알 수 있습니다.

이와 같은 문제에서 한 쪽에 대한 풀이를 정확히 진행하고 이를 대입해 풀 수 있다는 것을 염두해두고 푸시면 좋을 것 같습니다.

 

 

 

 

 

백준 14890번 경사로

14890번: 경사로