SWEA 4014 활주로 건설(with Python)

daeungdaeung·2021년 10월 6일
0
  • 너무 어렵게 푼 감이 없지 않아 많이 있습니다... ㅜ
def dfs(r, c, m, d):
    global check
    if c < 0 or c >= N:
        check = True
        return
    else:
        # 한칸 움직였는데 같은 위치라면 그냥 넘어가면 됨
        if brd[r][c] == brd[r][c-d]:
            dfs(r, c+d, m, d)
        # 1 작은 지형이라면 X 만큼 움직이면서 평평한지 확인해야지
        elif brd[r][c] == brd[r][c-d] - 1:
            # 왼쪽 오른쪽 한꺼번에 하려다 보니, for loop가 복잡해짐...
            # 손으로 직접 계산해보면 왜이렇게 설계 했는지 어렵지 않게 알수 있음
            for i in range(c+d, c+X*d, d):
                # X 만큼 가기전에 활주로가 끝난 경우
                if i < 0 or i >= N:
                    check = False
                    return
                # X 만큼 가기전에 지형이 변화한 경우
                if brd[r][c] != brd[r][i]:
                    check = False
                    return
                # 이미 사용한 위치인 경우
                if is_used[i] == 1:
                    check = False
                    return
            # 활주로 건설했으니 건설 위치 표시하기
            for i in range(c, c+X*d, d):
                is_used[i] = 1
            # X 만큼 건너뛰고, max 값은 1 줄이고 계속 진행하기
            dfs(r, c+X*d, m-1, d)
        # 1 높은 지형이라면 X 만큼 움직이면서 평평한지 확인하기
        elif brd[r][c] == brd[r][c-d] + 1:
            for i in range(c-d, c-X*d-d, -d):
                if is_used[i] == 1:
                    check = False
                    return
            else:
                for i in range(c-d, c-X*d-d, -d):
                    is_used[i] = 1
                dfs(r, c+d, m+1, d)
        # 같은 높이 이거나 1차이 지형이 아니라면 활주로 추가 건설 불가
        else:
            check = False
            return

T = int(input())
for tc in range(1, T+1):
    N, X = map(int, input().split())
    brd = [list(map(int, input().split())) for _ in range(N)]

    answer = 0

    for row in range(N):
        max_v = max(brd[row])
        max_col_idx = brd[row].index(max_v)
        # 활주로 건설에 사용된 위치인지 확인하기 위한 용도
        is_used = [0] * N
        # 왼쪽으로 순회하면서 활주로 체크
        check = False
        dfs(row, max_col_idx-1, max_v, -1)
        # 오른쪽으로 순회
        if check:
            dfs(row, max_col_idx+1, max_v, +1)

        if check:
            answer += 1

    # 세로 방향 체크해야하는데, 그냥 주어진 배열을 돌려서
    # 가로 방향으로 체크하자
    for r in range(N):
        for c in range(r+1, N):
            brd[r][c], brd[c][r] = brd[c][r], brd[r][c]

    for row in range(N):
        max_v = max(brd[row])
        max_col_idx = brd[row].index(max_v)
        # 활주로 건설에 사용된 위치인지 확인하기 위한 용도
        is_used = [0] * N
        # 왼쪽으로 순회하면서 활주로 체크
        check = False
        dfs(row, max_col_idx - 1, max_v, -1)
        # 오른쪽으로 순회
        if check:
            dfs(row, max_col_idx + 1, max_v, +1)

        if check:
            answer += 1

    print(f'#{tc} {answer}')
profile
개발자가 되고싶읍니다...

0개의 댓글