[Python] 백준 1063번 문제 풀이 - 킹

문제 링크

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

문제 이해

이 문제는 체스판에서 킹을 이리저리 움직이다가 마지막에 킹의 위치와 돌의 위치를 구하는 문제입니다.

킹은 상하좌우, 대각선으로 전부 이동할 수 있습니다.

그리고 킹이 움직이는 자리에 돌이 있다면 돌도 킹이 움직였던 방향으로 움직입니다.

킹이 오른쪽으로 한칸 움직였다면 돌도 오른쪽으로 한칸 움직입니다.

한번 움직였을 때, 킹이나 돌 중 하나가 체스판을 벗어날 경우 해당 움직임을 건너뜁니다.

아이디어

그래서 떠올린 아이디어는 다음과 같습니다.

1. 킹의 좌표와 돌의 좌표를 숫자로 저장한다.
2. 킹이 먼저 이동할 위치를 확인하고, 그 자리에 돌이 있으면 돌까지 이동할 위치를 확인한다.
3. 위치 확인 시 둘중 하나라도 체스판 밖이라면 건너뛴다.
4. 확인한 위치로 킹과 돌을 이동시킨다.

시간복잡도

이동 커맨드에 있는 것 한번만 순회하고 내부에서 비교 연산만 하기 때문에 O(N)이고 N은 50이라 가능합니다.

코드 구현

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

import sys
input = sys.stdin.readline

# A = 1로 매핑하기 위해 맨 앞에 공백 추가
str_table = " ABCDEFGH"
move_table = {
    "R": [1, 0], "L": [-1, 0], "B": [0, -1], "T": [0, 1],
    "RT": [1, 1], "LT": [-1, 1], "RB": [1, -1], "LB": [-1, -1]
}

# 체스판 범위 (1~8)를 벗어나는지 확인하는 함수
def is_valid(x, y):
    return 1 <= x <= 8 and 1 <= y <= 8

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

moves = []
# 이동 커맨드 저장
for _ in range(n):
    moves.append(input().rstrip())

# 알파벳과 숫자를 분리하고 정수형으로 변환
king = [str_table.find(k[0]), int(k[1])]
rock = [str_table.find(r[0]), int(r[1])]

for move in moves:
    # 어느쪽으로 이동할지
    dx, dy = move_table[move]
    # king이 이동할 위치 확인
    king_temp_x, king_temp_y = king[0] + dx, king[1] + dy

    if not is_valid(king_temp_x, king_temp_y): # 킹이 판을 벗어났으면
        continue # 건너뛰기

    if king_temp_x == rock[0] and king_temp_y == rock[1]: # 킹이 이동한 위치에 돌이 있다면
        rock_temp_x, rock_temp_y = rock[0] + dx, rock[1] + dy # rock이 이동할 위치 확인

        if not is_valid(rock_temp_x, rock_temp_y): # 돌이 판을 벗어났으면
            continue # 건너뛰기
        else:
            rock = [rock_temp_x, rock_temp_y] # 돌의 위치 이동
    king = [king_temp_x, king_temp_y] # 킹의 위치 이동

print(str_table[king[0]] + str(king[1]))
print(str_table[rock[0]] + str(rock[1]))

 

 

새로 배웠던 점

제출 후 다른 사람이 작성했던 시간이 더 적게 걸리는 코드를 봤는데, 가독성은 제 코드가 좀 더 좋은 것 같았지만 문자 변환할 때

ord(”문자”) 를 통해 문자를 유니코드 숫자로 변환하였고

chr(”숫자”) 를 통해 숫자를 유니코드 문자로 변환할 수 있다는 것을 배울 수 있었습니다.