백준|14890번|경사로

문제설명
크기가 N*N인 지도에서 다양한 높이의 칸들이 있을 때 경사로를 놓아서 완주할 수 있는 경로가 몇개인지를 출력하는 문제입니다.
경사로를 놓는 규칙
1. 경사로를 놓기 위해서는 같은 높이의 칸이 M개이어져있어야함
2. 경사로를 놓기 위해서는 두 칸의 높이의 차이가 1이어야함
3. 경사로를 놓는 칸은 두 칸중 낮은 칸임
4. 경사로가 놓여있는칸은 다른 경사로를 놓을 수 없음

작동 순서
1. 맵의 크기 N과 경사로를 놓기 위해 필요한 칸의 길이 M을 입력받습니다.
2. 맵의 구조를 입력받습니다.
3. 가로부터 시작하여 세로 방향으로 경로를 확인합니다.
4. 다음칸이 현재칸과 높이가 같은 경우 그대로 통과합니다.
5. 다음칸이 현재칸보다 높이가 1칸 낮은 경우 다음칸부터 이후 M개의 칸 까지를 확인하여 높이가 모두 같은 경우 그 경로에 경사로를 놓고 이동합니다.
6. 다음칸이 현재칸보다 높이가 1칸 높은 경우 현재칸부터 이전 M개의 칸까지를 확인하여 높이가 모두 같고 놓여있는 경사로가 없는 경우 경사로를 놓고 이동하고 경사로가 있는 경우 해당 경로 탐색을 종료합니다.
7. 다음칸이 현재칸보다 2칸 이상 높거나 낮은 경우 해당 경로 탐색을 종료합니다.
8. 모든 경로를 탐색한 뒤에 완주할 수 있는 경로의 개수를 출력합니다.

소스코드

import sys
N, M = map(int, sys.stdin.readline().split())
loadMap = []
count = 0
for i in range(N):
    loadMap.append(list(map(int, sys.stdin.readline().split())))
for i in range(N):
    runway = [0 for _ in range(N)]
    canThrough = True
    for j in range(N-1):
        if loadMap[i][j] == loadMap[i][j+1]:
            pass
        elif loadMap[i][j]-loadMap[i][j+1] == -1 and runway[j] == 0:
            n = 0
            while n <= M-1:
                if j - n < 0:
                    canThrough = False
                    break
                if loadMap[i][j] != loadMap[i][j - n] or runway[j - n] == 1:
                    canThrough = False
                    break
                if n == M-1:
                    n2 = 0
                    while n2 < M:
                        runway[j - n2] = 1
                        n2 += 1
                n += 1

        elif loadMap[i][j]-loadMap[i][j+1] == 1 and runway[j+1] == 0:
            n = 1
            while n <= M:
                if j + n >= N:
                    canThrough = False
                    break
                if loadMap[i][j + 1] != loadMap[i][j + n]:
                    canThrough = False
                    break
                if n == M:
                    n2 = 0
                    while n2 < M:
                        n2 += 1
                        runway[j + n2] = 1
                n += 1
        else:
            canThrough = False
            break
    if canThrough:
        count += 1

for i in range(N):
    runway = [0 for _ in range(N)]
    canThrough = True
    for j in range(N-1):
        if loadMap[j][i] == loadMap[j+1][i]:
            pass
        elif loadMap[j][i]-loadMap[j+1][i] == -1 and runway[j] == 0:
            n = 0
            while n <= M-1:
                if j - n < 0:
                    canThrough = False
                    break
                if loadMap[j][i] != loadMap[j-n][i] or runway[j - n] == 1:
                    canThrough = False
                    break
                if n == M-1:
                    n2 = 0
                    while n2 < M:
                        runway[j - n2] = 1
                        n2 += 1
                n += 1

        elif loadMap[j][i]-loadMap[j+1][i] == 1 and runway[j+1] == 0:
            n = 1
            while n <= M:
                if j + n >= N:
                    canThrough = False
                    break
                if loadMap[j+1][i] != loadMap[j+n][i]:
                    canThrough = False
                    break
                if n == M:
                    n2 = 0
                    while n2 < M:
                        n2 += 1
                        runway[j + n2] = 1
                n += 1
        else:
            canThrough = False
            break
    if canThrough:
        count += 1
print(count)

후기
요즘 삼성 기출문제 들을 풀어보고 있는데 복잡한 구현 문제가 많은 것 같습니다. 구현 능력을 기르는 것도 중요하고 좀 더 효율적인 알고리즘을 짜는 것도 중요한 것 같습니다. 계속해서 노력해야 할 것 같습니다.