14890번 - 경사로

문제

 

14890번: 경사로 (acmicpc.net)

14890번: 경사로

풀이 1

조건들을 잘 검토하고, 이를 구현해야하는 문제이다. 구현 문제에서는 조건을 잘 정리할 필요가 있다는 점을 명심해야한다.

• 높이가 1보다 크게 차이나면 경사로를 놓을 수 없으므로, 지나갈 수 없다.
• 현재 탐색중인 곳을 기준으로, 높이가 이전보다 1만큼 크다면 이전에는 길이 l 만큼의 평평한 땅이 확보되어 있어야한다.
• 현재 탐색중인 곳을 기준으로, 높이가 이전보다 1만큼 작다면 이후로 길이 l 만큼의 평평한 땅이 확보되어야 한다.
• 한번 경사로를 놓은곳에는 다시 경사로를 놓을 수 없다.
• 보드의 범위를 벗어나는 곳에는 경사로를 놓을 수 없다.

위 조건을 그대로 구현하면 되지만, 막상 내 풀이는 문제를 조금 빗나간 방식으로 접근했다. '평평한 땅' 에 대해서 l 이상 땅이 확보 되어 있는지 확인하는 get_states 메서드와 states 를 순회하며 실제로 '지나갈 수 있는지' 확인하는 get_cnt 메서드를 이용해서 풀었다. 처음에는 한번 경사로를 놓으면 해당 '평평한 땅' 에는 다시 경사로를 놓을 수 없도록 로직을 짰는데, 이는 평평한 땅에 경사로를 여러개 놓을 수 있다는 사실을 간과한것이 원인이 됐다. 때문에 get_states 메서드가 아예 쓸모가 없는 메서드가 됐는데, 당연하게도 애초에 get_states는 땅에 경사로를 하나 놓는 순간 더이상 놓을 수 없다는 전제로 만든 메서드 였기 때문이다. get_cnt에서는 불필요하게 경사로를 더 놓을 수 있는지 검사한다.

 

import sys
input = sys.stdin.readline
n,l = map(int,input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))


def get_states(_board) -> list:
    states = []
    for row in _board:
        li = []
        for num in row:
            if not li or num != li[-1][0]:
                li.append([num,False,1]) if l > 1 else li.append([num,True,1])
            else:
                li[-1][2] += 1
                if li[-1][2] >= l:
                    li[-1][1] = True
        states.append(li)
    return states


def get_cnt(_states) -> int:
    result = 0
    for state in _states:
        if len(state) == 1:
            result += 1
            continue

        for i in range(1, len(state)):
            num, flag, length = state[i]
            if num > state[i - 1][0] + 1 or num < state[i - 1][0] - 1 or (
                    num == state[i - 1][0] + 1 and not state[i - 1][1]) or (num == state[i - 1][0] - 1 and not flag):
                break
            elif num == state[i - 1][0] + 1 and state[i - 1][1]:
                state[i-1][2] -= l
                if state[i-1][2] < 0:
                    break
            elif num == state[i - 1][0] - 1 and flag:
                state[i][2] -= l
                if state[i][2] < 0:
                    break
        else:
            result += 1
    return result


t_board = list(zip(*board))
states = get_states(board)
t_states = get_states(t_board)

print(get_cnt(states) + get_cnt(t_states))

 

위 코드는 따라서 다음과 같이 축약 가능하다. get_states는 각 땅의 높이와 길이 정보만 가져오며, get_cnt는 그 땅의 길이 정보에 기반해서 경사로를 놓을 수 있는지 판단한다. 조건을 잘 정리해두고 문제를 풀자!!!

import sys
input = sys.stdin.readline
n,l = map(int,input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))


def get_states(_board) -> list:
    _states = []
    for row in _board:
        li = []
        for num in row:
            if not li or num != li[-1][0]:
                li.append([num,1])
            else:
                li[-1][1] += 1
        _states.append(li)
    return _states


def get_cnt(_states) -> int:
    result = 0
    for state in _states:
        if len(state) == 1:
            result += 1
            continue
        for i in range(1, len(state)):
            num, length = state[i]
            if num > state[i-1][0] + 1 or num < state[i-1][0] - 1:
                break
            elif num == state[i-1][0] + 1:
                state[i-1][1] -= l
                if state[i-1][1] < 0:
                    break
            elif num == state[i-1][0] - 1:
                state[i][1] -= l
                if state[i][1] < 0:
                    break
        else:
            result += 1
    return result


t_board = list(zip(*board))
states = get_states(board)
t_states = get_states(t_board)

print(get_cnt(states) + get_cnt(t_states))

풀이 2

지나갈 수 있는길이 되는 경우는 두가지이다. 완전히 평평한 땅이거나 경사로를 놓아서 길을 연결할 수 있는 경우이다.

경사로끼리는 겹칠 수 없다는 점을 유의해야하는데, 경사로를 놓아봤자 길이 연결되지 않는 경우에는 L만큼 블럭이 확보되어 있다고 해도 비워둬야 한다.

따라서 경사로를 놓아가면서 해당 위치를 점유한다고 표시해야하고, 한 행에 대해서 경사로를 놓을 때에도 오르막 경사로일때와 내리막 경사로일때 서로 왼쪽 오른쪽으로 탐색범위가 다르다는 점도 주의해야한다.

감이 잘 안잡히는 구현문제에 대해서는 직접 예시를 손으로 구현해보며 코드 설계를 하도록 하자.

N,L = map(int,input().split())
board = []
for _ in range(N):
    board.append(list(map(int,input().split())))

occupied = [[0]*N for _ in range(N)]
answer = 0
for _ in range(2):
    for row in range(N):
        col,seq = 1,1
        flag = True
        visited = [0]*N
        while flag and col < N:
            now,prev = board[row][col],board[row][col-1]
            if abs(now-prev) > 1:
                flag = False
                break
            if now != prev:
                # 1 만큼 더 높을 때
                if now-prev == 1:
                    if seq < L:
                        flag = False
                        break
                    for i in range(col-L,col):
                        if visited[i] == 1:
                            flag = False
                            break
                        visited[i] = 1
                # 1 만큼 더 낮을 때
                elif now-prev == -1:
                    visited[col] = 1
                    for i in range(1,L):
                        if col+1 > N-1 or board[row][col+1] != board[row][col]:
                            flag = False
                            break
                        col += 1
                        visited[col] = 1
                seq = 1
            else:
                seq += 1
            col += 1
        # 완전히 평평한 길이거나, 경사로를 놓을 수 있는 경우
        if flag:
            answer += 1
            occupied[row] = visited
    # 전치
    board = list(map(list,zip(*board)))
    occupied = list(map(list,zip(*occupied)))

print(answer)