[BOJ] 17837번 새로운 게임 2 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

AC까지 1시간 20분 소요되었다.

의식적으로 문제읽을 때 엄청 꼼꼼하게 한문장 한문장 읽으니 좋았다. 최대 10분까지 투자할 생각으로 한 문장도 놓치지 말자.

• N<=12, K<=10 조건으로 극악의 시간복잡도가 나올 것을 예상할 수 있었다.
• 어떤 자료구조로 접근할지 먼저 손으로 고민해본 후 코드에 들어가서 덜 어지러웠다.
• 상수 정의는 상단에 꼭 해두는게 항상 이로운 것 같다. 특히 상하좌우, dx,dy
• is_valid도 함수로 항상 빼는게 이롭다.
• 인덱스 0부터 시작하는 것과 1부터 시작하는 것의 변수명 차이를 확실하게 다르게 두자.
• 테스트 케이스 넣기전에 내 코드 쭉 훑어보는거 진짜 연습해야겠다,, 귀찮아서 안하게 되는데 의식적으로 꼭 하자.

from collections import defaultdict

# 상수 정의
RIGHT, LEFT, UP, DOWN = 1, 2, 3, 4
WHITE, RED, BLUE = 0, 1, 2
dx_dy = [None, (0, 1), (0, -1), (-1, 0), (1, 0)]


# 함수 정의
def is_valid(x, y):
    """범위안에 들어있고 파란색 아닌지 체크"""
    if 0 <= x < N and 0 <= y < N and maps[x][y] != BLUE:
        return True
    return False


def reverse_direction(dir):
    if dir == RIGHT: return LEFT
    elif dir == LEFT: return RIGHT
    elif dir == UP: return DOWN
    elif dir == DOWN: return UP


def move_horse(horse_num:int):
    """horse_num에 해당하는 이동을 수행"""
    #print(horse_num)
    #print(horse_location)

    # 말에 해당하는 좌표 찾기
    now_x, now_y = None, None
    for x_y, horse_nums in horse_location.items():
        if horse_num in horse_nums:
            now_x, now_y = x_y

    dx, dy = dx_dy[horse_direction[horse_num]]
    new_x, new_y = now_x + dx, now_y + dy

    if is_valid(new_x, new_y) and maps[new_x][new_y] == WHITE:  # 흰색
        # 슬라이싱해서 이동하는 좌표에 append & 기존꺼 제거
        idx = horse_location[(now_x, now_y)].index(horse_num)
        horse_location[(new_x, new_y)].extend(horse_location[(now_x, now_y)][idx:])
        horse_location[(now_x, now_y)] = horse_location[(now_x, now_y)][:idx]

    elif is_valid(new_x, new_y) and maps[new_x][new_y] == RED:  # 빨간색
        # 슬라이싱 후 뒤집이서 이동하는 좌표에 append & 기존꺼 제거
        idx = horse_location[(now_x, now_y)].index(horse_num)
        horse_location[(new_x, new_y)].extend(horse_location[(now_x, now_y)][idx:][::-1])
        horse_location[(now_x, now_y)] = horse_location[(now_x, now_y)][:idx]

    else:  # 외부 or 파란색
        # 방향 뒤집고 그쪽도 파&외부 아니면 move_horse 호출
        horse_direction[horse_num] = reverse_direction(horse_direction[horse_num])
        dx, dy = dx_dy[horse_direction[horse_num]]
        new_x, new_y = now_x + dx, now_y + dy
        if is_valid(new_x, new_y):
            move_horse(horse_num)

    if len(horse_location[(now_x,now_y)]) == 0:  # 비었을 때
        del horse_location[(now_x, now_y)]


# 메인
horse_direction = dict()
horse_location = defaultdict(list)

N, K = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]

for i in range(1, K+1):
    input_x, input_y, direction = map(int, input().split())
    x, y = input_x-1, input_y-1

    horse_direction[i] = direction
    horse_location[(x, y)].append(i)

turn_cnt = 1
while turn_cnt <= 1000:
    # 말 이동 & 4개 이상 쌓이면 종료
    for horse_num in range(1, K+1):
        move_horse(horse_num)  # 말 이동

        # 4개 이상 쌓였는 지 체크
        for horse_nums in horse_location.values():
            if len(horse_nums) >= 4:
                print(turn_cnt)
                exit()

    turn_cnt += 1

print(-1)