<PART 2> 구현(완전탐색,시뮬레이션)

구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
EX) 리그오브레전드에서 정글이라는 포지션으로 이길 수 있는 완벽한 계획이 있다라더라도 피지컬이 안되면 진다. 하지만 구현은 계획만 있어도 된다.

완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 

예제 4 -1 상하좌우

N x N 크기의 정사각형 공간이 있다. 맨 왼쪽 위가 (1,1)이고 차례대로 좌표가 부여된다.
1. 처음 시작은 (1,1)이며, 다음 행동으로 옮길 때 이동의 규칙이 있다.
2. 상하좌우중에 1개씩 선택해서 할 수 있으며 정사각형 공간을 넘어가는 동작일 경우 횟수를 추가되지만 움직이지 않는다.
3. 최종 좌표를 출력하라
상하좌우: U, D, L, R

입력 예시)
5
R R R U D D

출력 예시)
3 4

- 내가 짠 코드 

n = int(input())
a = [1,1]
targets= list(input().split(" "))
 
for target in targets :
    if target == "L":
        if a[1] != 1:
            a[1] = a[1]-1    
        else:
            continue
    if target == "R":
        if a[1] != n:
            a[1] = a[1]+1    
        else:
            continue
    if target == "U ":
        if a[0] != 1:
            a[0] = a[0]-1    
        else:
            continue
    if target == "D":
        if a[0] != n:
            a[0] = a[0]+1    
        else:
            continue
print(a[0], a[1])    

코드의 단순반복이 너무 많아 책의 코드를 참고한 다음 다시 코드를 작성하였습니다.

n = int(input())
a = [1,1]
 
#list로 됨
plans= input().split(" ")
 
# for문으로 쓸 때 한꺼번에 사용
dx = [0,0,-1,1]
dy = [-1,1,0,0]
target = ['L','R','U','D']
 
for plan in plans:
    for i in range(len(targets)):
        if plan == target[i]:
            x = a[0] + dx[i]
            y = a[1] + dy[i]
    
    if x < 1 or y<1 or x > n or y>n:
        continue
    a[0], a[1] = x,y
 
print(a[0], a[1])    

풀이: L,R,U,D의 케이스일 때 이동좌표를 같이 설정할 수 있도록 리스트로 먼저 선언 해줍니다.
입력받은 행동을 1개씩 비교하여 바로 좌표를 넣을 수 있게 하고 공간에 초과되지 않을 때 좌표를 대입합니다. 
이번 문제를 통해서 좌표문제들은 dx,dy,target처럼 한번에 이동시킬 수 있도록 짜는 것이 효율적임을 알게 되었습니다.

예제4-2 시각

00시 00분 00초 부터 N시 59분 59초까지 3이 들어가는 경우의 수를 모두 구하여라

입력 예시)
5

출력 예시)
11475

n = int(input())
count = 0 
 
for hour in range(0,n+1):
    for minute in range(0,60):
        for seconds in range(0,60):
            if '3' in str(hour) + str(minute) + str(seconds):
                count += 1
print(count)
                

<2> 왕실의 나이트

8x8 체스판이 있습니다. 임의의 위치를 정해주고 그 자리에서 나이트처럼 두칸앞, 좌우 한칸이동과 같이 대각선이동이 몇번 가능한지 경우의 수를 측정하는 문제입니다.

입력예시)
a1

출력예시)
2

체스판 예시
\ a b c d e f g h
1
2
3
4
5
6
7
8

input_data = input() #a1, b3같은 것
row = int(input_data[1]) #뒤의 숫자가 행이 됨
#a가 1이 되야하므로 아스키 -> int형으로 바꾼 뒤 게산함
column = int(ord(input_data[0]))-int(ord('a'))+1
 
knights= [(1,2),(-1,-2),(-1,2),(1,-2),(2,1),(-2,-1),(-2,1),(2,-1)]
result=0
for knight in knights:
    d_row = row + knight[1]
    d_column = column + knight[0]
    if d_row < 1 or d_column < 1 or d_row > 8 or d_column > 8:
        continue
    result+=1
 
print(result)

풀이: 특이한 것은 a~g까지의 문자열이 열입니다. 그러므로 아스키코드로 바꾸고 int로 바꿔준 다음 a아스키코드를 빼줍니다음+1을 해주면 a~g가 1~8로 바뀌어서 계산이 가능해집니다.
그런 다음 1~8범위를 초과하면 횟수를 더하지 않습니다.

배운 점:
1. 1=>, <=8을 조건에 사용했으면 continue를 사용하지 않을 수 있었다.
2. 문자가 나오면 아스키로 바꾸어서 계산가능하게 한다.

지금까지는 완전탐색의 문제였다.

<3> 게임개발      시뮬레이션(매뉴얼)

N X M 크기의 직사각형 맵이 있습니다.
맵의 각 칸은 (A,B)칸 이고 A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수입니다.
캐릭터는 상하좌우 움직일 수 있으며 바다로 된 칸에는 못갑니다. 캐릭터의 이동 매뉴얼은 다음과 같습니다.
1. 현재 위치에서 현재 방향을 기준으로 반시계방향부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재하다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

캐릭터가 방문한 칸의 수를 출력하는 프로그램을 작성하시오.
- 0: 북쪽, 1:동쪽 2:남쪽, 3:서쪽
- 0: 육지, 1:바다

입력예시)
4 4  # 4x4맵 생성
1 1 0 #(1,1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1 # 첫줄은 모두 바다
1 0 0 1 # 둘째 줄은 바다/육지/육지/바다
1 1 0 1 # 셋째 줄은 바다/바다/육지/바다
1 1 1 1  # 넷째 줄은 모두 바다출력예시)
3

입력예시)
5 5
2 2 0
1 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 0 0 1
1 1 1 1 1 

출력예시)
5 (중앙 0에서 시작하여 바로 왼쪽부터 회전하므로 5가 된다.)

# 맵 크기 받기
n,m=map(int,input().split())
 
#초기 맵을 0으로 설정하기
d = [[0]*m for _ in range(n)]
x,y,direction = map(int,input().split()) # 초기 위치와 방향 입력받기
 
#현재 위치가 1이 되게 한다.
d[x][y]=1
count = 1 #시작위치는 육지여야하니깐 바로 1추가
 
#전체맵받기
array = []
for i in range(n):
    array.append(list((map(int,input().split()))))
 
#북동남서, 문제에서 0-> 북, 1-> 동, 2->남, 3->서
dx = [-1,0,1,0]
dy = [0,1,0,-1]
 
#북서남동(반시계)
def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3
 
#시뮬레이션
turn_time = 0
while True:
    #왼쪽으로 회전
    turn_left()
    # 회전하고 이동
    nx = x+dx[direction] #nx는 가야할 좌표, x는 현재 위치
    ny = y+dy[direction]
    # 이동한 좌표가 처음가는 곳이라면 count하고 횟수 더하기
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        x = nx
        y = ny
        count +=1
        turn_time = 0
        d[nx][ny] = 1
        continue             
    # 그 외인 상황(전부 다돌았을때 바다거나 전부 다 가본곳 결국 1인 곳일때)
    else:
        turn_time += 1
    if turn_time == 4: #4방향이 봤을 때
        nx = x - dx[direction]
        ny = y - dy[direction]
        #뒤로 갈수 있을 때
        if array[nx][ny]==0:
            x = nx
            y = ny
            
        #전부 바다일 때
        else:
            break
        turn_time = 0
print(count)