[Python] 구현_왕실의 나이트

구현

구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
특징 : 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기는 것은 어려우 문제를 의미.
문제유형 분류 : 완전탐색 + 시뮬레이션 유형 모두 구현으로 분류

• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

# 예제 4-1 상하좌우
n = int(input())
x, y = 1, 1
plans = input().split()

#L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

for plan in plans:
	#이동 후 좌표 구하기
	for i in range(len(move_typeds)):
    	if plan == move_types[i]:
        	nx = x + dx[i]
            ny = y + dy[i]
     # 공간을 벗어나느 경우 무시-> [이부분 생각 못함.]
     if nx < 1 or ny < 1 or nx > n or ny > n:
     	continue
     # 이동 수행
     x, y = nx, ny
print(x, y)

• 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법
  전체 데이터의 개수가 100만 개 이하일때 완전탐색 사용하는 것이 적절함.

# 예제 4-2 시각
h = int(input())

count = 0
for i in range(h + 1):
	for j in range(60):
    	for k in range(60):
        	# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
            	count += 1
print(count)

-> 그리디 알고리즘과 구현 알고리즘의 차이보다,
하나의 문제에 구현과 그리디 유형이 함께 포함된 형태로 출제되는 경우가 많음.

대표예제2 왕실의 나이트

문제

행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다.
나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다
나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다
나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다

수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이처럼 8 × 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라.
왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a 부터 h로 표현한다.

c2에 있을 때 이동할 수 있는 경우의 수는 6가지이다
a1에 있을 때 이동할 수 있는 경우의 수는 2가지이다

입력

첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1 처럼 열과 행으로 이뤄진다.

출력

첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

입력 예시

a1

출력 예시

2

풀이

1) dx랑 dy에 해당되는 점 위치를 얼마나 움직여야하는 지 다 저장해야하므로,
나이트가 이동할 수 있는 방향 정의하기. (8가지)
2) '상하좌우' 문제에서의 dx, dy 리스트 선언이 이동방향을 기록했다면,
steps 변수가 dx, dy 변수의 기능을 대신하여 수행함.

# 상하좌우(시뮬레이션) 문제와 비슷

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

result = 0
for step in steps:
	next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 다운
    # 체스판과 같은 8 × 8 좌표 평면으로 표현(범위)
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)