[SWEA] 활주로 건설

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

같은 높이의 구간이 X만큼 연속되어 있는지 찾아내는 문제이다.
단순하게 구간을 계산하면서 넘어갔는데 높이가 바뀌는 경우에 count를 1로 초기화할지
0으로 초기화할지 잘 생각해야하는 문제였다.

풀이

T = int(input())

for test_case in range(1, T+1):
    N, X = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    answer = 0

    # 가로 방향 탐색
    for y in range(N):
        if check_road(y, 0):
            answer += 1

    # 세로 방향 탐색
    for x in range(N):
        if check_road(x, 1):
            answer += 1


    print(f"#{test_case} {answer}")

 

기본적인 코드의 형태는 가로 방향으로 탐색하고 세로 방향으로 탐색하는 것으로 구현하였다.
check_road를 이용하여 활주로를 건설할 수 있는지 체크하는데 앞에 인자는 선택하는 줄이고
뒤에 인자는 가로, 세로를 설정하기 위해 줬다.

 

def check_road(y, c):
    if c == 0:
        count = 1
        pre = board[y][0]
        i = 1
        while i < N:
            if pre == board[y][i]:
                count += 1
            elif pre + 1 == board[y][i]:
                if count < X:
                    return False
                count = 1
                pre += 1
            elif pre - 1 == board[y][i]:
                for j in range(X):
                    if (i + j) == N or board[y][i + j] != pre - 1:
                        return False
                i += X-1
                pre = pre - 1
                count = 0
            else:
                return False
            i += 1

        return True

가로방향 y축으로 탐색하는 함수이다.
처음 y, 0의 좌표를 pre 초기값으로 설정하고 경사로의 높이는 항상 1이기 때문에 2 이상의 높이 차가 나는 경우는 고려할 필요가 없다.

i가 1부터 N - 1까지 반복하면서 아래 3가지 경우를 확인했다.
현재 좌표가 pre와 같은 경우
count를 증가시킨다. 

현재 좌표보다 pre가 1칸 큰 경우
연속된 구간이 끝나고 높이가 증가하는 구간이 왔을 때 지금까지 count의 숫자가 X보다 크거나 같으면 경사로를 건설할 수 있다. 활주로가 건설되었으면 새로운 높이를 pre로 설정해주고 count는 1로 만들어준다.
건설하지 못하면 활주로가 끊어진 것이기 때문에 False를 반환한다.

현재 좌표보다 pre가 1칸 작은 경우
1칸 작은 경우가 복잡한데 작아진 지점부터 경사로의 가로 길이인 X만큼 확인하면서 동일한 구간이 연속되어 나오는지 확인한다.
연속된 구간이 나온다면 경사로를 건설할 수 있는 것이기 때문에 새로운 높이를 pre로 설정하고 count는 0으로 변경한다. 0으로 변경하는 이유는 마지막에 검사한 구간까지 활주로를 건설했기 때문에 0으로 시작해야한다.
그 후 i값을 검사한 구간까지 이동시키고 다음 구간부터 다시 반복해서 검사한다.
i에 + X가 아닌 X - 1을 하는 이유는 while의 마지막 부분에 index를 1 증가시키는 부분이 들어있기 때문에 
-1까지 증가시켰다.
연속된 구간이 X개 나오지 않거나 범위 밖으로 벗어나면 건설할 수 없는 것이기 때문에 False를 반환한다.

 

X축에 대해서는 좌표만 변경되고 동일하게 작동한다.

 

전체 코드

def check_road(y, c):
    if c == 0:
        count = 1
        pre = board[y][0]
        i = 1
        while i < N:
            if pre == board[y][i]:
                count += 1
            elif pre + 1 == board[y][i]:
                if count < X:
                    return False
                count = 1
                pre += 1
            elif pre - 1 == board[y][i]:
                for j in range(X):
                    if (i + j) == N or board[y][i + j] != pre - 1:
                        return False
                i += X-1
                pre = pre - 1
                count = 0
            else:
                return False
            i += 1

        return True
    else:
        count = 1
        pre = board[0][y]
        i = 1
        while i < N:
            if pre == board[i][y]:
                count += 1
            elif pre + 1 == board[i][y]:
                if count < X:
                    return False
                count = 1
                pre += 1
            elif pre - 1 == board[i][y]:
                for j in range(X):
                    if (i + j) == N or board[i + j][y] != pre - 1:
                        return False
                i += X - 1
                pre -= 1
                count = 0
            else:
                return False
            i += 1

        return True




T = int(input())

for test_case in range(1, T+1):
    N, X = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    answer = 0

    # 가로 방향 탐색
    for y in range(N):
        if check_road(y, 0):
            answer += 1

    # 세로 방향 탐색
    for x in range(N):
        if check_road(x, 1):
            answer += 1


    print(f"#{test_case} {answer}")

체크하는 부분에 대한 설계가 완벽하지 못해서 예제 코드를 디버깅하면서 직접 문제점을 찾아봤다.
설계 단계에서 조금 더 자세하게 설계하는 습관을 가지는 것이 좋을 것 같다.

또 경사로를 건설할 수 있는지 체크하는 함수를 더 깔끔하게 구현하는 방법이 없는지 찾아봐야겠다.