Ray`s Tech Lab

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

행 하나하나, 열 하나하나에 대해 지나갈 수 있는지 판단해주면 되는 문제. 단순히 구현만 해주면 된다.

내가 처음에 작성한 코드는 다음과 같다.

import sys
input = sys.stdin.readline


def is_all_same_height(heights):
    for i in range(len(heights) - 1):
        if heights[i] != heights[i + 1]:
            return False
    return True


def is_all_same_column(board, c):
    for r in range(len(board) - 1):
        if board[r][c] != board[r + 1][c]:
            return False
    return True


def solution(n, k, board):
    answer = 0

    for row in board:
        checked = [False for _ in range(n)]
        if is_all_same_height(row):
            answer += 1
        else:
            for c in range(n - 1):
                if row[c] == row[c + 1]:
                    continue
                if row[c] + 1 == row[c + 1]:
                    for nc in range(c, c - k, -1):
                        if nc < 0 or checked[nc] or row[nc] != row[c]:
                            break
                    else:
                        nc = c - k + 1
                        for i in range(nc, c + 1):
                            checked[i] = True
                        continue
                    break
                elif row[c] == row[c + 1] + 1:
                    for nc in range(c + 1, c + 1 + k):
                        if nc >= n or checked[nc] or row[nc] != row[c + 1]:
                            break
                    else:
                        nc = c + 1 + k
                        for i in range(c + 1, nc):
                            checked[i] = True
                        continue
                    break
                else:
                    break
            else:
                answer += 1

    for c in range(n):
        checked = [False for _ in range(n)]
        if is_all_same_column(board, c):
            answer += 1
        else:
            for r in range(n - 1):
                if board[r][c] == board[r + 1][c]:
                    continue
                if board[r][c] + 1 == board[r + 1][c]:
                    for nr in range(r, r - k, -1):
                        if nr < 0 or checked[nr] or board[nr][c] != board[r][c]:
                            break
                    else:
                        nr = r - k + 1
                        for i in range(nr, r + 1):
                            checked[i] = True
                        continue
                    break
                elif board[r][c] == board[r + 1][c] + 1:
                    for nr in range(r + 1, r + 1 + k):
                        if nr >= n or checked[nr] or board[nr][c] != board[r + 1][c]:
                            break
                    else:
                        nr = r + 1 + k
                        for i in range(r + 1, nr):
                            checked[i] = True
                        continue
                    break
                else:
                    break
            else:
                answer += 1
    return answer


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

print(solution(N, L, _board))

사실 나조차도 돌이켜보면 어떤 일을 하는지 참 알기 어려운 코드..우테코 프리코스 이후로 이런 더러운 코드 작성을 내면에서 혐오하곤 있긴 한데, 코테의 특성상 일단 구현하는게 먼저라고 생각해 더러운 걸 알면서 일단 저렇게 풀어봤다.

대충 저 코드의 핵심은 행과 열에 대해 지나갈 수 있는지를 판단하는 코드가 다르다는 것이다. 행에 접근할 때와 열에 접근할 때는 인덱싱 방법이 달라지기 때문에 구분해서 만들었다.

그러나 다른 사람들의 풀이를 보니, 좀 더 간단한 방법이 있었다. 바로 행과 열을 인덱싱 방법 이런 거 상관없이 똑같은 하나의 1차원 배열로 보는 것이다. 즉 열도 행처럼 보는 것! 파이썬의 for문을 이용하면

board = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]

column = [board[i][0] for i in range(4)]

이런 식으로 하나의 열을 1차원 리스트, 즉 하나의 행처럼 가져올 수 있다. 이렇게 하면 행과 열에 대한 판단을 할 때 각기 다른 코드를 만들 필요 없이 하나의 코드로 행과 열에 대한 판단을 내릴 수 있다.

import sys
input = sys.stdin.readline


def check_path(path, k):
    length = len(path)
    check = [0 for _ in range(length)]

    for i in range(length - 1):
        if abs(path[i] - path[i + 1]) > 1:
            return False
        if path[i] + 1 == path[i + 1]:
            for j in range(i, i - k, -1):
                if j < 0 or check[j] or path[j] != path[i]:
                    return False
                check[j] = 1
            continue
        if path[i] == path[i + 1] + 1:
            for j in range(i + 1, i + 1 + k):
                if j >= length or check[j] or path[j] != path[i + 1]:
                    return False
                check[j] = 1
    return True


def solution(n, k, board):
    answer = 0
	# 행에 대한 판단
    for row in board:
        if check_path(row, k):
            answer += 1
	# 열에 대한 판단
    for c in range(n):
        if check_path([board[i][c] for i in range(n)], k):
            answer += 1

    return answer


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

print(solution(N, L, _board))

구현..이라는 종목을 풀 때는, 이런 식으로 단순화해서 생각하는게 중요한 것 같다. 안 그러면 시간이 너무 오래 걸리는 듯..