[백준] 1063번 : 킹 (🥈실버 4) (Python)

문제 바로 가기

1063번: 킹

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2022-03-11

place = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

dxs = [0, 1, 1, 1, 0, -1, -1, -1]
dys = [1, 1, 0, -1, -1, -1, 0, 1]

king, stone, n = tuple(input().split())
n = int(n)

king_x = place.index(king[0]) + 1
king_y = int(king[1])

stone_x = place.index(stone[0]) + 1
stone_y = int(stone[1])

mapper = {
    'T' : 0,
    'RT' : 1,
    'R' : 2,
    'RB' : 3,
    'B' : 4,
    'LB' : 5,
    'L' : 6,
    'LT' : 7
}

def in_range(x, y):
    return x >= 1 and x <= 8 and y >= 1 and y <= 8

def move(dir_num):
    global king_x, king_y, stone_x, stone_y

    king_nx = king_x + dxs[dir_num]
    king_ny = king_y + dys[dir_num]

    if in_range(king_nx, king_ny):
        king_x = king_nx
        king_y = king_ny
    else:
        return

    if king_x == stone_x and king_y == stone_y:
        stone_nx = stone_x + dxs[dir_num]
        stone_ny = stone_y + dys[dir_num]

        if not in_range(stone_nx, stone_ny):
            king_x = king_x - dxs[dir_num]
            king_y = king_y - dys[dir_num]
        else:
            stone_x = stone_nx
            stone_y = stone_ny


for _ in range(n):
    direction = input()
    dir_num = mapper[direction]
    move(dir_num)

# 출력
king_x = place[king_x - 1]
print(king_x + str(king_y))

stone_x = place[stone_x - 1]
print(stone_x + str(stone_y))

 

풀이 로직

• 2차원 평면에서 한 칸씩 이동하는 상황의 문제에 유용한 dx-dy 테크닉을 활용하여 문제를 해결하였다.
• 우선, 말의 위치를 모두 숫자로 나타내고, 킹의 움직임 정보에 따른 다음 킹의 위치를 계산한다.
  • 이 때 각 정보에 따라 킹이 어떻게 움직여야 하는지는 mapper 딕셔너리와 dxs, dys 리스트로 표현하었다.

 

• 그리고, 그렇게 계산한 킹의 다음 예상 좌표가 체스판을 벗어나진 않았는지, 혹은 돌이 그 위치에 존재하는지의 경우를 각각 따져, 킹과 돌의 다음 위치를 확정한다. (move() 함수로 구현)
  • 킹의 다음 예상 좌표가 체스판을 벗어나면, move() 함수를 반환하여 해당 이동을 건너뛴다.
  • 만일 체스판을 벗어나지 않았다면, 돌이 킹의 다음 예상 좌표에 존재하는 지를 확인한다.
  • 물론, 돌도 킹과 함께 이동해야 하는 경우, 체스판을 벗어나는지를 또 따져봐야 한다. (벗어나면 킹의 이동도 취소해야 한다.)

 

• 이 과정을 n번 반복하면, 최종 킹과 돌의 위치를 구할 수 있다.

 

문제 접근 과정 및 느낀점

• 백준에서 처음으로 dx-dy 테크닉을 써서 푼 문제였는데, 꽤 따져야 부분이 많아 까다로웠다.
• 방향만 8개로 증가했을 뿐, 캠프 때 학습했던 내용에서 크게 벗어나지 않는 문제라, 로직은 어렵지 않게 세울 수 있었다.
• 하지만, 문자열 입력값을 깜박하고 숫자형으로 변환하지 않는다던가, 킹과 돌이 체스판을 벗어나는 경우를 미쳐 생각하지 못하던가 등의 미스로 인해 코드 구현 및 수정 작업 과정에서 애를 먹었다.
• 그래도 오로지 혼자의 힘으로 문제를 해결할 수 있어서 만족스럽다.
• 문제를 좀 더 간단하게 풀 방법이 있을 것 같다는 생각은 들지만, 지금 이렇게 푼 것도 쉽지 않았기에, 일단 이 문제는 여기서 넘어가려 한다.
• (P.S. 개인적으로 실버4 수준의 문제는 아닌 듯..)