[백준] 17780 - 새로운 게임 (Python)

요구사항에 맞게 구현하면 되는 문제

오랜만에 풀어서 그런지 꽤 어려웠다..

 

윷놀이 문제처럼 말을 이동하다가 다른 말을 만나면 쌓아야 하는데, 말을 쌓더라도 자신이 갖고있는 방향은 바뀌면 안된다.

 

class Unit:
    def __init__(self, number, row, col, direction):
        self.number = number
        self.row = row
        self.col = col
        self.direction = direction

    def check_next(self):
        if self.direction == RIGHT:
            return self.row, self.col + 1
        if self.direction == LEFT:
            return self.row, self.col - 1
        if self.direction == UP:
            return self.row - 1, self.col
        if self.direction == DOWN:
            return self.row + 1, self.col

    def change_direction(self):
        if self.direction == RIGHT:
            self.direction = LEFT
        elif self.direction == LEFT:
            self.direction = RIGHT
        elif self.direction == UP:
            self.direction = DOWN
        elif self.direction == DOWN:
            self.direction = UP

    def __str__(self):
        return str((self.number, self.row, self.col, self.direction))

 

먼저 말을 나타내는 Unit 클래스를 작성했다.

말을 쌓을 때는 이 Unit을 직접 쌓음으로서 자신들이 갖고 있는 방향이 유지되도록 하였다.

WHITE, RED, BLUE = 0, 1, 2
RIGHT, LEFT, UP, DOWN = 1, 2, 3, 4

N, K = map(int, input().split())
board_info = [[2 for _ in range(N+2)]] + [[2] + list(map(int, input().split())) + [2] for _ in range(N)] + [[2 for _ in range(N+2)]]
board = [[0 for _ in range(N+2)] for _ in range(N+2)]
unit_info = [[] for _ in range(K + 1)]
for i in range(1, K+1):
    row, col, direction = map(int, input().split())
    board[row][col] = i
    unit_info[i].append(Unit(i, row, col, direction))

 

보드판 타일색과 이동방향은 상수로 관리해준다.

보드판 바깥으로 나가는 것은 파란색으로 이동하는 것과 같다고 하였으니 보드판 주변을 파란색 타일로 둘러준다.

이렇게하면 1-index로 문제를 풀 수 있고, 이동할 때 범위를 벗어나는 걸 고려하지 않아도 되어서 좋다.

(다른 그래프 문제 풀 때도 애초에 이렇게 설정하고 풀어볼까..)

 

실제 말의 배치 현황을 나타내는 것은 board로, 각 보드의 타일색 정보는 board_info로 나눠 관리하였다.

unit_info 는 i번째 말 위에 어떤 말들이 쌓여있는지를 나타낸다.

처음에는 자신의 말 위에 자신에 대한 정보만 있도록 세팅하였다.

 

turn = 0
while turn <= 1000:
    turn += 1
    for unit_number in range(1, K+1):
        if unit_info[unit_number]:  # 현재 유닛이 움직일 수 있다면
            # 유닛이 보고있는 방향대로 이동
            now_unit: Unit = unit_info[unit_number][0]
            check_row, check_col = now_unit.check_next()

            if board_info[check_row][check_col] == WHITE:
                process_white(now_unit, check_row, check_col)

            elif board_info[check_row][check_col] == RED:
                process_red(now_unit, check_row, check_col)

            elif board_info[check_row][check_col] == BLUE:
                # 이동한 곳의 판이 파란색인 경우, 방향 바꾸고 파란색이 아니면 이동
                now_unit.change_direction()
                check_row, check_col = now_unit.check_next()
                if board_info[check_row][check_col] != BLUE:
                    if board_info[check_row][check_col] == WHITE:
                        process_white(now_unit, check_row, check_col)

                    elif board_info[check_row][check_col] == RED:
                        process_red(now_unit, check_row, check_col)

 

먼저 main 로직은 위와 같이 작성하였다.

현재 유닛이 다른 유닛 위에 올라가 있지 않다면, unit_info 의 자신 번호 데이터가 있다는 의미이다.

이때는 자신이 움직일 수 있다는 의미이므로, 이동하려는 방향의 타일색을 체크한다.

 

타일색이 하얀색, 빨간색일 때 처리하는 부분은 별도 함수로 분리하였다.

타일색이 파란색일 때, 한번 더 처리해야 하기 때문이다.

 

def process_white(now_unit, check_row, check_col):
    # 기존 말은 보드에서 지우기
    board[now_unit.row][now_unit.col] = 0
    if board[check_row][check_col] > 0:
        # 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 쌓기
        exist_unit = board[check_row][check_col]
        for unit in unit_info[unit_number]:
            unit_info[exist_unit].append(unit)
            unit.row = check_row
            unit.col = check_col
        unit_info[unit_number].clear()

        # 말이 4개 이상 쌓였다면 게임 종료
        if len(unit_info[exist_unit]) >= 4:
            print(turn)
            exit(0)
    else:
        # 이동한 곳에 말이 없는 경우, 쌓는 것 없이 이동만
        board[check_row][check_col] = now_unit.number
        for unit in unit_info[unit_number]:
            unit.row = check_row
            unit.col = check_col

 

먼저 하얀색을 처리할 때는 간단하다.

이동하려는 곳에 말이 있다면 현재 자신에게 쌓여있는 말들을 차례대로 순회하면서 이동하려는 말 위에 쌓아준다.

이때 말이 4개 이상 쌓였다면 그대로 턴을 출력하고 프로그램을 종료한다.

만약 이동하려는 곳에 말이 없다면 자신에게 쌓여있는 말 전체의 위치값을 바꿔주고 보드판에 반영하면 된다.

 

def process_red(now_unit, check_row, check_col):
    # 이동한 곳의 판이 빨간색인 경우
    board[now_unit.row][now_unit.col] = 0
    unit_number = now_unit.number
    # 이동한 곳에 말이 있는 경우, 기존 말의 배치를 뒤집고, 이동한 말 위에 추가
    if board[check_row][check_col] > 0:
        # 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 뒤집어서 쌓기
        exist_unit = board[check_row][check_col]
        while unit_info[unit_number]:
            popped_unit: Unit = unit_info[unit_number].pop()
            popped_unit.row = check_row
            popped_unit.col = check_col
            unit_info[exist_unit].append(popped_unit)

        # 말이 4개 이상 쌓였다면 게임 종료
        if len(unit_info[exist_unit]) >= 4:
            print(turn)
            exit(0)
    else:
        # 이동한 곳에 말이 없는 경우, 기존 말의 배치를 뒤집고 이동
        inverse_unit_number = unit_info[unit_number][-1].number
        if len(unit_info[unit_number]) > 1:
            while unit_info[unit_number]:
                popped_unit: Unit = unit_info[unit_number].pop()
                popped_unit.row = check_row
                popped_unit.col = check_col
                unit_info[inverse_unit_number].append(popped_unit)
        else:
            unit_info[unit_number][-1].row = check_row
            unit_info[unit_number][-1].col = check_col

        board[check_row][check_col] = inverse_unit_number

 

 

이동하려는 곳에 말이 있다면 자신의 말을 뒤에서부터 하나씩 빼면서 기존 말 위에 추가해준다.

이렇게하면 역순으로 쌓이게 된다.

 

이동하려는 곳에 말이 없다면 현재 쌓여있는 것을 반대로 뒤집어주고 위치만 이동한 곳으로 바꿔준다.

위 코드에서 뒤집으려는 말의 개수가 1개보다 큰지 체크하는 이유는 만약 뒤집으려는 말의 개수가 1개라면 반복문이 무한으로 돌기 때문이다.

 

정답 코드

class Unit:
    def __init__(self, number, row, col, direction):
        self.number = number
        self.row = row
        self.col = col
        self.direction = direction

    def check_next(self):
        if self.direction == RIGHT:
            return self.row, self.col + 1
        if self.direction == LEFT:
            return self.row, self.col - 1
        if self.direction == UP:
            return self.row - 1, self.col
        if self.direction == DOWN:
            return self.row + 1, self.col

    def change_direction(self):
        if self.direction == RIGHT:
            self.direction = LEFT
        elif self.direction == LEFT:
            self.direction = RIGHT
        elif self.direction == UP:
            self.direction = DOWN
        elif self.direction == DOWN:
            self.direction = UP

    def __str__(self):
        return str((self.number, self.row, self.col, self.direction))


WHITE, RED, BLUE = 0, 1, 2
RIGHT, LEFT, UP, DOWN = 1, 2, 3, 4

N, K = map(int, input().split())
board_info = [[2 for _ in range(N+2)]] + [[2] + list(map(int, input().split())) + [2] for _ in range(N)] + [[2 for _ in range(N+2)]]
board = [[0 for _ in range(N+2)] for _ in range(N+2)]
unit_info = [[] for _ in range(K + 1)]
for i in range(1, K+1):
    row, col, direction = map(int, input().split())
    board[row][col] = i
    unit_info[i].append(Unit(i, row, col, direction))


def process_white(now_unit, check_row, check_col):
    # 기존 말은 보드에서 지우기
    board[now_unit.row][now_unit.col] = 0
    if board[check_row][check_col] > 0:
        # 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 쌓기
        exist_unit = board[check_row][check_col]
        for unit in unit_info[unit_number]:
            unit_info[exist_unit].append(unit)
            unit.row = check_row
            unit.col = check_col
        unit_info[unit_number].clear()

        # 말이 4개 이상 쌓였다면 게임 종료
        if len(unit_info[exist_unit]) >= 4:
            print(turn)
            exit(0)
    else:
        # 이동한 곳에 말이 없는 경우, 쌓는 것 없이 이동만
        board[check_row][check_col] = now_unit.number
        for unit in unit_info[unit_number]:
            unit.row = check_row
            unit.col = check_col


def process_red(now_unit, check_row, check_col):
    # 이동한 곳의 판이 빨간색인 경우
    board[now_unit.row][now_unit.col] = 0
    unit_number = now_unit.number
    # 이동한 곳에 말이 있는 경우, 기존 말의 배치를 뒤집고, 이동한 말 위에 추가
    if board[check_row][check_col] > 0:
        # 이동한 곳에 말이 이미 있는 경우, 이동하려는 유닛 위에 기존 말을 뒤집어서 쌓기
        exist_unit = board[check_row][check_col]
        while unit_info[unit_number]:
            popped_unit: Unit = unit_info[unit_number].pop()
            popped_unit.row = check_row
            popped_unit.col = check_col
            unit_info[exist_unit].append(popped_unit)

        # 말이 4개 이상 쌓였다면 게임 종료
        if len(unit_info[exist_unit]) >= 4:
            print(turn)
            exit(0)
    else:
        # 이동한 곳에 말이 없는 경우, 기존 말의 배치를 뒤집고 이동
        inverse_unit_number = unit_info[unit_number][-1].number
        if len(unit_info[unit_number]) > 1:
            while unit_info[unit_number]:
                popped_unit: Unit = unit_info[unit_number].pop()
                popped_unit.row = check_row
                popped_unit.col = check_col
                unit_info[inverse_unit_number].append(popped_unit)
        else:
            unit_info[unit_number][-1].row = check_row
            unit_info[unit_number][-1].col = check_col

        board[check_row][check_col] = inverse_unit_number


turn = 0
while turn <= 1000:
    turn += 1
    for unit_number in range(1, K+1):
        if unit_info[unit_number]:  # 현재 유닛이 움직일 수 있다면
            # 유닛이 보고있는 방향대로 이동
            now_unit: Unit = unit_info[unit_number][0]
            check_row, check_col = now_unit.check_next()

            if board_info[check_row][check_col] == WHITE:
                process_white(now_unit, check_row, check_col)

            elif board_info[check_row][check_col] == RED:
                process_red(now_unit, check_row, check_col)

            elif board_info[check_row][check_col] == BLUE:
                # 이동한 곳의 판이 파란색인 경우, 방향 바꾸고 파란색이 아니면 이동
                now_unit.change_direction()
                check_row, check_col = now_unit.check_next()
                if board_info[check_row][check_col] != BLUE:
                    if board_info[check_row][check_col] == WHITE:
                        process_white(now_unit, check_row, check_col)

                    elif board_info[check_row][check_col] == RED:
                        process_red(now_unit, check_row, check_col)

print(-1)