백준 14890 경사로 (Python)

문제

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

14503번: 로봇 청소기

나의 접근법

저는 row를 길을 세는 함수와 col의 길을 세는 함수를 다르게 작성하여 풀었습니다. 

그리고 다음과 같이 예외를 추가하며 길의 수를 세었습니다.

1. 높이 차이가 2 이상인 경우 제외

2. 높이가 증가하다가 감소하는 경우, 감소하다 증가하는 경우

3. 높이가 낮은 칸의 개수가 L 보다 큰 경우

 

저는 이렇게 3가지를 구분하여 문제를 풀려고 했고 다음과 같이 코드를 작성하였습니다.

 

제출 코드 (오답)

import sys
graph = []
N, L = map(int, sys.stdin.readline().split())
for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

def rowSol(L, result):
    for i in range(N):
        MIN = int(1e9)
        MAX = -1
        preNum = 0
        flag = 0  # 차이가 한번도 발생X
        continueFlag = False
        for j in range(N):
            # 행 검사
            num = graph[i][j]
            MIN = min(num, MIN)
            MAX = max(num, MAX)

            if abs(MIN - MAX) >= 2:
                continueFlag = True
                break
            if preNum != 0:  # 증가>감소 또는 감소>증가 경우 확인
                dif = num - preNum
                if flag == 0:
                    flag = dif
                elif flag * dif == -1:
                    continueFlag = True
                    break
            preNum = num

        if continueFlag:
            continue

        if MAX == MIN:  # 값이 계속 같은 경우
            result += 1
            print(i)
            continue

        minCnt = graph[i].count(MIN)

        if minCnt >= L:
            print(i)
            result += 1

    return result

def colSol(L, result):
    for i in range(N):
        MIN = int(1e9)
        MAX = -1
        preNum = 0
        flag = 0  # 차이가 한번도 발생X
        continueFlag = False
        for j in range(N):
            # 행 검사
            num = graph[j][i]
            MIN = min(num, MIN)
            MAX = max(num, MAX)
            if abs(MIN - MAX) >= 2:
                continueFlag = True
                break
            if preNum != 0:  # 증가>감소 또는 감소>증가 경우 확인
                dif = num - preNum
                if flag == 0:
                    flag = dif
                elif flag * dif == -1:
                    continueFlag = True
                    break
            preNum = num

        if continueFlag:
            continue

        if MAX == MIN:  # 값이 계속 같은 경우
            result += 1
            print(i)
            continue

        minCnt = 0
        for j in range(N):
            if graph[j][i] == MIN:
                minCnt += 1

        if minCnt >= L:
            print(i)
            result += 1

    return result

print(colSol(L, 0) + rowSol(L, 0))

위 코드의 경우 continueFlag 라는 변수를 두어 더 이상 진행할 필요가 없는 칸의 경우 다음 행으로 넘어가게 만들었습니다. 또한 이전 값과 현재 값의 차이가 -1 에서 +1 또는 -1에서 +1로 변하는 경우 continueFlag로 다음행을 넘어가게 만들었습니다.

하지만 여기서 제가 간과한 것이 있었습니다.

번호가 증가했다가 감소하다가 다시 증가하는 경우 낮은 칸의 개수가 L 이상이면 그 길은 통행이 가능한 길이었습니다. 즉 제가 고려한 2번이 반은 맞고 반은 틀리게 된 것이었습니다.

예시에서도 1해은 가능한 것을 확인하였습니다. 하지만 저는 이것을 간과하고 코드를 작성하여 오답이 출력되었습니다.

 

제 코드를 계속 작성하거나 처음부터 다시 작성하려고 했으나 시간을 너무 많이 뺏기는 것 같아서 구글링을 통해 깔끔한 정답을 보며 제 코드와의 차이점이 무엇인지 파악하려 했습니다.

 

정답 코드

import sys
def check_route(N, L, route):
    ramp = [0] * N  # 경사로를 세웠는지 확인하기 위한 리스트
    for i in range(N - 1):
        if route[i] != route[i + 1]:  # 높이 차이가 있는 경우
            if abs(route[i] - route[i + 1]) > 1:  # 높이 차이가 1이 아닌 경우
                return False
            else:  # 높이 차이가 1인 경우
                if route[i] - route[i + 1] == 1:  # 높은 칸에서 낮은 칸
                    if i + 1 + L > N: return False
                    check = route[i + 1]  # 경사로를 세울 수 있는 높이인지 확인용
                    for j in range(i + 1, i + 1 + L):
                        if ramp[j] or route[j] != check: return False
                        ramp[j] = 1
                elif route[i] - route[i + 1] == -1:  # 낮은 칸에서 높은 칸
                    if i - L < -1: return False
                    check = route[i]
                    for j in range(i, i - L, -1):
                        if ramp[j] or route[j] != check: return False
                        ramp[j] = 1
    return True

input = sys.stdin.readline
N, L = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]
cnt = 0  # 지나갈 수 있는 길의 수 기록
for r in MAP:  # 행 확인
    if check_route(N, L, r): cnt += 1
for c in range(N):  # 열 확인
    if check_route(N, L, [MAP[r][c] for r in range(N)]): cnt += 1

print(cnt)

위 코드를 처음 보자마자 이해가 잘 되었습니다. 제 기준에서는 구성이 너무 깔끔해서 이 코드를 보며 제 코드의 문제점을 파악할 수 있었고 위 코드를 분석하기로 했습니다.

먼저 저와 달리 높이차가 2이상인 경우 다음 행으로 넘어가는 것은 맞았지만 저는 현재 칸과 이전 칸의 변수를 따로 설정하여 코드의 복잡함이 증가하였습니다. 

또한 반복문에서 N-1 까지만 동작하게 하여 2칸씩 비교하는 방법을 택하였는데 저는 생각만 하고 이렇게 하면 코드가 더 지저분 해질 것 같다고 생각했는데 오히려 이것이 더 깔끔했습니다. 이러한 디테일은 배워야 할 것 같습니다.

 

for j in range(i + 1, i + 1 + L):
    if ramp[j] or route[j] != check: return False
    ramp[j] = 1

제가 배워야 할 부분은 다른 곳도 많았지만 이 부분을 배워야 할 것 같았습니다. 이런 방식을 생각하지 못했고

ramp라는 변수를 두어 0은 경사로를 세우고 1은 경사로를 안세우는 경우로 구분하였습니다. 저는 경사로를 세웠는지 파악하는 변수나 리스트를 만들지 않아서 계속 오답이 출력되었던 것 같습니다.

처음에는 어렵지 않은 줄 알고 단순하게 플로우 차트로 경우의 수만 체크하고 풀었던 것 같습니다. 디테일한 코드 작성이 아직까지 미흡한 것 같습니다.