[공부] 완전 탐색, 시뮬레이션 - 시각 문제, 나이트 문제

완전 탐색(Brute Forcing)

가능한 경우의 수를 모두 검사해보는 탐색 방법

---

시각 세기 문제

• 정수 N이 입력되면 N시간 안에 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램 작성.

입력 : 첫째 줄에 정수 N 입력 (0<=N<=23)
출력 : 00시 00분 00초부터 N시 59분 59초까지의 모든
시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력

n = int(input())

count = 0
for i in range(n+1): #n시
    for j in range(60):  # 59분
        for k in range(60): # 59초
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k): #시 분 초를 문자열 형태로 나열한 모습
                count += 1
print(count)

<결과>

<풀이 과정>

• 가능한 모든 시각의 경우를 하나씩 모두 세서 푸는 문제
• 하루는 24 x 60 x 60 = 86,400가지 중 3이 하나라도 있는지를 확인하면 됨
• 완전 탐색 문제 유형

---

완전탐색 + 시뮬레이션 + 2차원 공간

왕실의 나이트 문제

• 8 * 8 좌표 평면이 주어짐
• 이동할 때 L자 형태로만 이동하고 좌표평면 밖으로 나갈 수 없음.
• 이동 경우는
  1. 수평 2칸 이동 후 수직 한칸,
  2. 수직 2칸 이동 후 수평 한 칸
• 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수 출력
• 나이트의 모든 위치 경우는 8임.
  열 위치는 알파벳 (a~h), 행 위치는 (1~8)
  예) c2에 있을 땐 경우의 수 6가지, a1에 있을 때 경우의 수 2가지

입력 : 현재 나이트가 위치한 곳의 좌표를 나타내는 열,행 입력
출력 : 나이트가 이동할 수 있는 경우의 수 출력
예) a1 -> 2

# 현 위치 받기 ,문자 리스트로 받게됨
input_data = input()
column = int(ord(input_data[0])) - int(ord('a')) + 1  #열(알파벳) a = 1
row = int(input_data[1]) #행(숫자)

# 2차원 배열로 방향 벡터를 잡기
# 시계 방향으로 정리 (0~7)
steps = [(-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps: # 각각의 방향을 확인하면서
    # 이동하고자 하는 위치 확인
    # x좌표[0]는 행이고 y좌표[1]는 열이다
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 = 범위 안이라면,
    # 카운트를 증가
    # and는 모두 참이어야 참임.
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8 :
        result += 1

print(result)

<결과>

ord
ord(c)는 문자의 유니코드 값을 돌려주는 함수이다.

※ ord 함수는 chr 함수와 반대이다.

ord('a') => 97
ord('가') => 44032

<풀이과정>

• 나이트의 위치를 입력 받은 후 : a(열-y좌표), 1(행-x좌표) 문자 리스트를 int로 숫자로 바꿔줌
• 나이트의 8가지 경로를 2차원 배열로 정리한 후 리스트에 넣기
  ↑ 방향 정의노트
• 각 8가지 경로로 이동이 가능한지를 확인한다.
• result값을 초기화하고 for문을 돌며 steps의 방향 요소요소를 확인한다.
• step에 담긴 방향 리스트에 [0], [1]은 x-행과 y-열이 담겨있으므로
  next_row, next_column에 현위치+이동위치를 넣어줌
• if 조건문으로 next_row와 next_column으로 이동이 가능할때
  result값을 증가시킨다.
• 마지막으로 result값을 print하면 끝

출처 : 동빈나 알고리즘 영상