[SWEA 4014] 활주로 건설

접근

먼저 가로와 세로를 탐색해서 활주로가 가능한지 알아보기 위해 각 열의 세로 정보들을 N행에 이어 붙였다. 이후 각 행마다 활주로 건설이 가능한지 검사를 한다. 

먼저 이전 인덱스의 값과 현재 인덱스의 값이 같을 때는 continue를 진행한다.

이전 인덱스와 현재 인덱스의 + 1 값이 같을 때는 내리막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다.

이전 인덱스의 - 1과 현재 인덱스의 값이 같을 때는 오르막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다.

 

경사로를 설치할 때는 범위를 벗어나거나 겹쳐서 사용하면 안되기 때문에 각 인덱스에 경사로 설치유무를 체크하고 맵을 벗어나는지 체크하여 경사로를 설치하도록 한다.

 

구현

- 경사로를 설치했는지 판단한는 visited 리스트를 선언하였다.

- 이후 x는 1부터 탐색을 진행하여 이전 값들과 비교한다.

- 이전 값과 같을 때는 x에 1을 증가시켜 continue하고

- 이전 값과 현재의 + 1이 같을 때는 내리막을 설치할 수 있는지 검사하여 설치할 수 있을 때는 visited에 True를 표시하고 x를 X만큼 증가시켜 다음으로 넘어간다.

- 이 과정에서 설치할 수 없다는 것은 활주로가 되지못하기 때문에 False를 반환한다.

- 오르막의 경우도 위와 마찬가지이다.

- 위의 세 가지 경우가 아닐 때는 모두 활주로를 만들지 못하기 때문에 False를 반환한다.

def solve(y):
    visited = [False] * N
    x = 1
    while x < N:
        if board[y][x - 1] == board[y][x]:
            x += 1
            continue
        if board[y][x - 1] == board[y][x] + 1:
            if is_possible(y, x, visited, 1):
                for i in range(X):
                    visited[x+i] = True
                x += X
            else:
                return False
        elif board[y][x - 1] == board[y][x] - 1:
            if is_possible(y, x-1, visited, 0):
                for i in range(1, X+1):
                    visited[x - i] = True
                x += 1
            else:
                return False
        else:
            return False
    return True

- 아래의 함수는 경사로를 설치할 수 있는지 판단하는 함수이다.

- flag가 0일 때는 오르막 경사로, 1일 때는 내리막 경사로를 설치할 수 있는지 판단한다.

- X범위 만큼 높이를 검사하여 모두 같을 때는 True를 반환하고

- 이미 경사로가 설치되어있거나 높이가 다를 때는 False를 반환하도록 한다.

def is_possible(y, x, visited, flag):
    height = board[y][x]
    # 내리막 경사로 설치 가능 판단
    if flag:
        for i in range(1, X):
            if not check_range(x+i):
                return False
            if visited[x+i] == False and board[y][x+i] == height:
                continue
            else:
                return False
        return True
    # 오르막 경사로 설치 가능 판단
    else:
        for i in range(1, X):
            if not check_range(x - i):
                return False
            if visited[x - i] == False and board[y][x-i] == height:
                continue
            else:
                return False
        return True

---

전체 코드

testCase = int(input())

def check_range(x):
    return (0 <= x < N)

def is_possible(y, x, visited, flag):
    height = board[y][x]
    # 내리막 경사로 설치 가능 판단
    if flag:
        for i in range(1, X):
            if not check_range(x+i):
                return False
            if visited[x+i] == False and board[y][x+i] == height:
                continue
            else:
                return False
        return True
    # 오르막 경사로 설치 가능 판단
    else:
        for i in range(1, X):
            if not check_range(x - i):
                return False
            if visited[x - i] == False and board[y][x-i] == height:
                continue
            else:
                return False
        return True

def solve(y):
    visited = [False] * N
    x = 1
    while x < N:
        if board[y][x - 1] == board[y][x]:
            x += 1
            continue
        if board[y][x - 1] == board[y][x] + 1:
            if is_possible(y, x, visited, 1):
                for i in range(X):
                    visited[x+i] = True
                x += X
            else:
                return False
        elif board[y][x - 1] == board[y][x] - 1:
            if is_possible(y, x-1, visited, 0):
                for i in range(1, X+1):
                    visited[x - i] = True
                x += 1
            else:
                return False
        else:
            return False
    return True

for tc in range(testCase):
    N, X = map(int, input().split())
    input_map = [list(map(int, input().split())) for _ in range(N)]
    board = [[0 for _ in range(N)] for _ in range(N*2)]

    for y in range(N):
        for x in range(N):
            board[y][x] = input_map[y][x]

    for x in range(N):
        for y in range(N):
            board[x+N][y] = input_map[y][x]


    answer = 0
    for idx in range(N*2):
        if solve(idx):
            answer += 1

    print("#{} {}".format(tc+1, answer))