[python] BOJ 백준 14890: 경사로

1. 문제  

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

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

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

2. 입력   

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

3. 출력   

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

4. 해결방법   

삼성에서 자주 출제되는 구현문제이다. 다만 조건문과 반복문에서의 구현이 조금 까다롭기 때문에 시간이 걸리는 문제이다. 이 문제는 지나갈 수 있는 길을 가로와 세로로 모두 탐색해 주어야한다. 가로와 세로 탐색의 함수를 각각 따로만들어 줄 수도 있겠지만, 배열을 90도 회전한다면 체크함수를 하나만 만들어도 된다. 따라서 배열을 90도로 회전하는 함수와 지나갈수 있는 길인지를 체크하는 함수 2개를 구형하여 해결하였다. 

1) rotate 함수: 배열을 90도 회전하는 함수이다. 배열을 회전하는 형식은 여러 알고리즘 문제에서 자주 등장하므로 외워두는 것이 좋다. 90도를 회전한다면 x좌표는 기존의 y좌표에 대응되고 y좌표는 기존의 x좌표를 배열의 원래길이에서 뺀 값이 된다. 2차원 배열을 돌면서 값을 업데이트 해주면 된다. 

2) check 함수: 건널수 있는지 없는지를 체크하는 함수이다. 인접하고 있는 두 숫자를 비교하면서 모두 탐색해주면된다. 만약 숫자가 같다면 다음 차례를 바로 탐색하면 될 것이고, 숫자가 2이상 차이난다면 당연히 건널 수 없기때문에 바로 false를 반환해주면된다. 문제는 숫자가 1만 차이나는 경우이다. 이 경우에는 왼쪽이 더 높은지 오른쪽이 더 높은지에 따라 다르게 탐색을 해주어야한다. 만약 왼쪽이 높다면 오른쪽 방향으로 다리의 길이만큼 탐색을 해주어야하고, 오른쪽이 높다면 왼쪽방향으로 다리의 길이만큼 탐색을 해주어야한다. 탐색을 하면서 높이가 하나라도 달라지면 바로 false를 반환하고, 이미 다리가 놓아져 있으면 false를 반환하면된다. 이 두 조건에 해당이 안된다면 다리를 놓을 수 있다는 것이므로 bridge배열에서의 해당인덱스를 True로 설정해준다.   

 

5) 구현코드   

#배열 90도 회전하는 함수 
def rotate(arr): 
    n = len(arr) 
    ret = [[0] * n for _ in range(n)] 
    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = arr[i][j]
    return ret

#건널수 있는지 체크하는 함수 
def check(board):
    bridge = [False for i in range(n)] #다리를 놓은 곳 
    for i in range(n - 1): 
        if board[i] == board[i + 1]: #숫자 같은 경우
            continue #건너뛰기 

        if abs(board[i] - board[i + 1]) > 1: #2이상 차이나는경우
            return False #실패 

        if board[i] > board[i + 1]:#왼쪽이 더 높은경우
            temp = board[i + 1] 
            #다리를 놓는 부분 탐색 
            for j in range(i + 1, i + 1 + l): 
                if 0 <= j < n: 
                    if board[j] != temp: #높이 안맞으면 
                      return False
                    if bridge[j] == True: #이미 다리 있으면 
                      return False
                    bridge[j] = True #다리 없으면 다리 놓기 
                else: #배열 범위를 초과하는 경우 
                    return False #실패 

        else: #오른쪽이 더 높은경우 
            temp = board[i]
            for j in range(i, i - l, -1):
                if 0 <= j < n:
                    if board[j] != temp: 
                      return False
                    if bridge[j] == True: 
                      return False
                    bridge[j] = True
                else:
                    return False
    return True

n, l = map(int, input().split())
s = []
for i in range(n):
    s.append(list(map(int, input().split())))

cnt = 0 
#가로탐색
for i in s: 
    if check(i):
        cnt += 1
s=rotate(s) #90도회전 
#세로탐색 
for i in s:
    if check(i):
        cnt += 1
print(cnt)

 

⭐️난이도:  골드 3 ⭐️ 

https://www.acmicpc.net/problem/14890

14890번: 경사로