문제 링크
문제 요약
체스 보드를 8x8 격자로, 행은 1부터 8, 열은 ‘a’부터 ‘h’로 표현하고 있습니다. 칸의 이름은 열(알파벳)과 행(숫자) 순서로 지정됩니다. -나이트 나이트는 한 번의 이동으로 칸 수직 이동 후 칸 수평 이동하거나, 칸 수직 이동 후 칸 수평 이동할 수 있습니다. 이때, 값과 나이트의 시작 위치가 주어졌을 때, 이 나이트가 한 번의 이동으로 위협할 수 있는(도달할 수 있는) 모든 칸을 찾아야 합니다.
풀이
이 문제는 체스판의 좌표계를 이해하고, 나이트의 독특한 이동 방식을 수치적으로 구현하는 것이 핵심입니다.
-
좌표 변환: 체스판의 ‘a1’과 같은 문자열 좌표를 내부적인 수치 좌표(예:
(열, 행))로 변환하고, 계산된 수치 좌표를 다시 문자열 좌표로 변환하는 함수가 필요합니다.- 코드에서는
to_axis(s)함수를 통해 ‘a''h’를 18의 열 번호로, ‘1''8’을 18의 행 번호로 변환합니다. 예를 들어 ‘a1’은(1, 1)이 됩니다. to_str(y, x)함수는 이와 반대로(y, x)좌표를 다시 ‘a1’과 같은 문자열로 변환합니다.
- 코드에서는
-
나이트의 이동: -나이트는 다음과 같은 8가지 방향으로 이동할 수 있습니다.
- 행, 열
- 행, 열
이를 코드로 구현하기 위해
dx와dy배열을 정의하여 모든 가능한 이동 방향을 표현했습니다.dx = [a, a, -a, -a, b, b, -b, -b]dy = [b, -b, b, -b, a, -a, a, -a]
-
도달 가능한 칸 탐색:
- 주어진 시작 위치를
to_axis함수를 이용해 수치 좌표(y, x)로 변환합니다. dx,dy배열을 순회하며 각 이동 방향에 대해 새로운 좌표(ny, nx)를 계산합니다.- 계산된
(ny, nx)가 체스판의 유효한 범위(열 18, 행 18) 내에 있는지 확인합니다. - 유효한 위치라면,
to_str함수를 이용해 다시 문자열 좌표로 변환한 후, 결과 리스트에 추가합니다.
- 주어진 시작 위치를
-
중복 제거 및 정렬:
a나b가 0이거나a와b가 같은 경우, 또는 특정 시작 위치에서는 서로 다른 이동 방향이 동일한 칸으로 이어질 수 있습니다. 따라서set자료구조를 사용하여 중복된 칸을 제거합니다. 리스트를set으로 변환한 후 다시list로 변환하여 중복을 제거할 수 있습니다.- 문제의 요구사항에 따라 도달 가능한 칸들을 정렬해야 합니다. 체스 칸 표기법(예:
a1,e6,f5)은 열이 먼저 오고 행이 뒤에 오기 때문에, 문자열 자체를 오름차순으로 정렬하면 문제에서 요구하는 “열 기준으로 오름차순, 열이 같으면 행 기준으로 오름차순” 정렬이 자연스럽게 이루어집니다. 파이썬의list.sort()는 기본적으로 문자열을 사전식(lexicographical)으로 정렬하므로 별도의 커스텀 정렬 로직 없이도 요구사항을 만족합니다.
이 과정을 통해 -나이트가 도달할 수 있는 모든 유효한 칸을 찾고, 정렬된 형태로 출력할 수 있습니다.
정답 코드
"""
[20574: General Knight](https://www.acmicpc.net/problem/20574)
Tier: Bronze 1
Category: math, implementation, data_structures, string, sorting, arithmetic, hash_set
"""
import sys
from math import sqrt, pi, sin, factorial, ceil, floor
from datetime import datetime, timedelta
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
from operator import itemgetter, attrgetter, mul, add, sub, truediv
from typing import List, Tuple, Dict, Set, Any, Union
SYS_INPUT = True
RECURSION_LIMIT = 10 ** 7
SET_RECURSION = False
BLANK = " "
if SET_RECURSION:
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda : sys.stdin.readline().rstrip() if SYS_INPUT else input()
mii = lambda : [*map(int,inp().split())]
mfi = lambda : [*map(float,inp().split())]
ii = lambda : int(inp())
fi = lambda : float(inp())
isplit = lambda : inp().split()
p = print
def gcd(a, b): return gcd(b, a % b) if b > 0 else a
def lcm(a, b): return a * b // gcd(a, b)
def to_axis(s):
y = ord(s[0]) - ord('a') + 1
x = int(s[1])
return (y, x)
def to_str(y, x):
return chr(y + ord('a') - 1) + str(x)
def solve():
a, b = mii()
s = inp()
dx = [a, a, -a, -a, b, b, -b, -b]
dy = [b, -b, b, -b, a, -a, a, -a]
y, x = to_axis(s)
l = []
for i in range(8):
ny = y + dy[i]
nx = x + dx[i]
if 1 <= ny <= 8 and 1 <= nx <= 8:
l.append(chr(ny + ord('a') - 1) + str(nx))
l = list(set(l))
l.sort()
print(len(l))
for i in l:
print(to_str(*to_axis(i)), end= ' ')
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()