[Python] 백준 17837번 문제 풀이 - 새로운 게임 2

문제 링크

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

문제 이해

이문제는 체스판 위에 말이 있는데 말 위에 다른 말을 쌓을 수 있고, 4개의 말이 쌓였을 때 게임이 종료되고 턴을 출력하는 문제입니다.

체스판 위에서 말이 이동할 수 있는 방향은 상하좌우 입니다.

• 1 : 오른쪽(→)
• 2: 왼쪽(←)
• 3: 위쪽(↑)
• 4: 아래쪽(↓)

턴이 진행되면 1번부터 k번째 말까지 순서대로 이동방향으로 이동합니다.

이 때 체스판의 색깔에 따라 이동하는 방법이 다릅니다.

1번말이 이동하는 것을 예시로 들겠습니다. 1번말의 상태는 1번위에 2번이 쌓여있는 상태입니다.

1번말이 이동하려는 칸이

• 흰칸이면 1번 위에 있는 말들이랑 다 같이 이동하는데, 원래 있던 말 위에 1,2번을 쌓습니다.
• 빨간칸이면 다 이동하고 쌓여있는 순서를 반대로 하여 원래 있던 말 위에 2,1번을 쌓습니다.
• 파란칸 및 체스판 밖을 나가는 경우 막혀있다고 표현할 것인데요, 막혀있는 경우 이동방향을 반대로 하여 이동합니다. 만약에 반대도 막혀있다면 이동방향을 유지하고 가만히 있습니다.
  • 2번 막혔을 때 만약에 1번의 이동방향이 → 였다면 ← 로 이동방향을 바꾸고 가만히 있으면 됩니다.

그리고 이동했을 때 쌓여있는 말이 4개라면 라운드를 종료하고 현재 라운드 수를 출력하고, 만약 1000라운드까지 4개가 쌓이지 않는다면 -1을 출력합니다.

아이디어

제가 세운 아이디어는 다음과 같습니다.

1. 말의 현황을 저장한 딕셔너리(말의 번호: (현재 행, 현재 열, 이동방향)), 체스판 좌표별 말의 현황을 저장한 딕셔너리((행, 열) : [1번말, 2번말]), 체스판 배열을 만듭니다.
2. 그리고 라운드수가 1000이 넘을때까지 반복하는 while문을 돌립니다.
3. while문 안에서 1~k번 말까지 이동하기 위한 for문을 돌립니다.
4. 이제 말이 이동하는데 다음 위치의 체스판이 어떤 색깔인지 확인하고 할 행동을 결정합니다.
   1. 만약 막혀있을 경우(밖으로 나가거나 파란색) 이동 방향을 반대로 바꾸고 이동 위치를 확인합니다.
      1. 만약에 한번 더 막힐 경우 그냥 가만히 둡니다.
      2. 한번 더 안막힐 경우 쌓인 말들의 리스트를 만듭니다.
   2. 만약 빨간색일 경우 리스트를 거꾸로 만듭니다.
   3. 만약 흰색일 경우 리스트를 이동시키고 말의 현황과 체스판위의 말의 현황을 업데이트 합니다.
5. 이동한 후에 쌓여있는 말이 4개 이상이라면 현재 라운드수를 출력하고 전체 반복문(while)을 탈출합니다.
6. 라운드수가 1000이 넘어 while문이 끝났을 때는 -1을 출력합니다.

시간복잡도

우선 while문은 최대 1000번 돌 수 있고 말의 개수의 최대는 10개이고, 내부에서는 딕셔너리를 통해 조회 하고 그 내부에 배열이 말의 개수인 최대 10개가 될 수 있으니

O(Nkk)로 10만정도 나올 거 같아 가능합니다.

코드 구현

이 아이디어를 코드로 구현하면 다음과 같습니다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

move_arr = [(), (0, 1), (0, -1), (-1, 0), (1, 0)]
chess_map = [list(map(int, input().split())) for _ in range(n)]

horse_dict = {}
chess_dict = {}

for i in range(n):
    for j in range(n):
        chess_dict[(i,j)] = []

for i in range(1, k+1):
    row, col, direction = map(int, input().split())
    horse_dict[i] = (row-1, col-1, direction)
    chess_dict[(row-1, col-1)].append(i)

round_cnt = 0
is_result = False

while round_cnt <= 1000:
    round_cnt += 1

    for i in range(1, k+1):
        row, col, direction = horse_dict[i]

        next_row, next_col = row + move_arr[direction][0], col + move_arr[direction][1]

        # 나가거나 파란색일 때
        if not (0<=next_row<n and 0<=next_col<n) or chess_map[next_row][next_col] == 2:
            # 반대방향으로 업데이트
            if direction % 2 == 0:
                direction -= 1
            else:
                direction += 1

            # 이동방향 업데이트
            horse_dict[i] = (row, col, direction)

            # 다음 위치 업데이트
            next_row, next_col = row + move_arr[direction][0], col + move_arr[direction][1]

            # 한번더 나가거나 파란색일 때
            if not (0 <= next_row < n and 0 <= next_col < n) or chess_map[next_row][next_col] == 2:
                continue # 위치 고정
        
        # 위에 쌓인 말 이동 준비
        index = chess_dict[(row, col)].index(i) # 현재 말의 인덱스 뽑기
        moving_stack = chess_dict[(row, col)][index:] # 위레 쌓인 말의 리스트 저장
        chess_dict[(row, col)] = chess_dict[(row, col)][:index] # 기존 체스판 좌표에서 이동시킬 말 제거

        # 이동방향이 빨간색일 때
        if chess_map[next_row][next_col] == 1:
            moving_stack.reverse() # 말 쌓인거 거꾸로

        # 이동 및 위치 최신화
        for x in moving_stack:
            chess_dict[(next_row, next_col)].append(x)
            horse_dict[x] = (next_row, next_col, horse_dict[x][2])

        # 이동했을 때 4개가 쌓였으면 종료
        if len(chess_dict[(next_row, next_col)]) >= 4:
            is_result = True
            break
    
    # 4개가 쌓였을 경우 출력하고 종료
    if is_result:
        print(round_cnt)
        break

# 라운드수가 1000이 넘었을때는 -1 출력
if round_cnt > 1000:
    print(-1)

 

 

새로 배우게 된 것

우선 파이썬 딕셔너리에서 (a,b) 이런 튜플을 키로 만들 수 있다는 것을 알게 되었습니다.

파이썬 딕셔너리는 해시 테이블이라서, 키는 해시 가능해야합니다.

근데 (a,b)는 왜 키로 쓸 수 있을까요?

튜플은 변하지 않는 값이고, 내부의 원소 a,b도 int기 때문에 해시가 가능합니다.

해시가 가능한데 변하지 않는 값이니 키로 사용할 수 있는 것입니다.

해시가 불가능한 것은 list, dict, set, byte array 등등 가변한 값이 있습니다.

가능한 값들은 int, float, bool, str, tuple(내부 요소가 해시 가능) 등이 있습니다.

 

 

부족함을 깨닫게 된 것

이번 문제에서 아이디어는 그렇게 어렵지 않게 떠올릴 수 있었지만 이 아이디어를 코드로 어떻게 구현해야할지에 대한 부분이 아직 많이 부족한 듯 합니다.

이걸 푸는데 이틀이 걸렸습니다. 아이디어를 코드로 구현하면 코드가 간결하지 않고 길어지게 되고 긴 코드에서 디버깅 하는게 복잡했습니다. 코드가 중복되는 것도 많고 하나를 고치다보면 다른 부분에서 문제가 터지고 그래서 아예 아이디어부터 다시 코드 구현법을 생각해서 구현했더니 해결할 수 있었습니다.

문제를 꾸준하게 풀며 아이디어를 최대한 간결하게 코드로 구현할 수 있는 역량을 갖추어야 겠다는 생각을 하게 되었습니다.