구현

CYSSSSSSSSS·2023년 7월 4일

구현 알고리즘

알고리즘

목록 보기

72/83

구현

머리속으로는 쉽게 생각할수 있지만 코드로 짜기 힘든 문제의 유형
완전 탐색 , 시뮬레이션 문제

상하좌우

여행가 A 는 N*N 크기의 정사각형 공간 위에 서있다.
이 공간은 1 x 1 크기의 정사각형으로 이루어져있다.
가장 왼쪽 위의 좌표는 (1,1) 이며 , 가장 오른쪽 아래는 N X N 에 해당한다.
A 는 상하좌우 방향으로 이동이 가능 , 시작 좌표는 항상 (1,1) 에서 시작한다.
계획서에는 L,R,U,D 중 하나의 문자가 반복적으로 적혀 있다.
문제 에서는 공간의 크기 N 과 계획서에 관련된 내용이 주어졌을떄 A의 최종 도착 지점의 좌표를 출력하는 프로그램을 작성하는 프로그램을 작성하시오

해결

이동 명령에 따른 x,y 의 변화를 리스트로 만들어 명령어 와 일치하는 이동 리스트를 찾아서 이동시킨다.
이떄 범위를 벗어나는 값은 if 문을 통해 확인 하고 아닌경우 x,y 좌표를 변화를 준다.

# 맵의 크기
n = int(input())

# 시작점
x,y = 1,1

# 이동 방향
plans = input().split()

#명령에 따른 이동 방향 x:의 이동 / y:행의 이동

dx = [0,0,-1,1] # 행의 이동에서 U , D 만 값이 부여
dy = [-1,1,0,0] # 열의 이동은 L , R 일떄만

# 파이썬에는 list.index 를 통해 이동 방향에 대한 index 를 알수 있다.
move_types = ['L','R','U','D']

for plan in plans:
    for move in move_types:
        if plan == move:
            idx = move_types.index(plan)
            nx = x + dx[idx]
            ny = y + dy[idx]

    if nx < 1 or ny < 1 or nx > n or ny > n: # 탐색 맵에서 벗어난 범위는 넘어가는 시스템
        continue

    x,y = nx,ny # 좌표 이동 


print(x,y)

시각

정수 N 을 입력하면 00시 00분 00초 부터 N시 59분 59초 까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력하는 프로그램을 작성하시오

해결

단순 반복으로 00시 00분 00초 부터 ~ N시 59분 59초 까지 3이 들어가는 경우의수를 세주면 되는 문제이다.

n = int(input())
count = 0
for i in range(n+1):
    for j in range(60):
        for k in range(60):
            print(f'{i}시 {j}분 {k}초')
            if '3' in str(i) or '3' in str(j) or '3' in str(k):
                count += 1

print(count)

왕실의 나이트

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

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

좌표 평면 행의 위치는 1 ~ 8 로 표현 열의 위치는 a ~ h 로 표현 한다.
첫쨰 줄에 나이트위치가 주어질떄 이동 가능한 경우의 수를 구하는 프로그램을 작성하시오.

해결

특정한 이동으로 하는 모든 경우를 탐색하여 범위에서 벗어나지 않는 이동을 카운팅 하면 되는 쉬운 문제이다.

location = input()

xs = ['a', 'b', 'c', 'd', 'e', 'f', 'h']
ys = ['1', '2', '3', '4', '5', '6', '7', '8']

x = xs.index(location[0])
y = ys.index(location[1])

# 나이트 로 이동 할수 있는 경우는 총 8가지 이다.
dx = [-2, -2, -1, 1, 2, 2, -1, 1]
dy = [-1, 1, 2, 2, -1, 1, -2, -2]

count = 0

for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0 <= nx < 8 and 0 <= ny < 8:
        count += 1

print(count)

게임 개발

현민이는 게임 캐릭터가 맵 안에 움직이는 시스템을 개발중이다.
크기가 N X M 으로 직사각형으로 각각의 칸은 육지 또는 바다이다.
캐릭터는 동서남북 중 한곳을 바라본다.
맵의 각 칸은 (A,B) 으로 나타낼수 있으며 A 는 북쪽에서 떨어진 정도
B는 서쪽으로 떨어진 정도 를 나타낸다.
캐릭터는 상하좌우 이동이 가능하다 + 바다로 이루어진 공간은 이동할수 없다.
캐릭터는 다음과 같은 메뉴얼로 이동한다.

현재 위치에서 현재 방향을 기준으로 왼쪽 방향 (반시계 방향으로 90 도 이동하여 차례대로 갈 곳을 정한다)
캐릭터 왼쪽에서 아직 가보지 않은 칸이 존재 한다면 왼쪽 방향으로 이동후에 왼쪽으로 한칸 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면 , 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단 이떄 뒤쪽 방향으로 갈수 없는 경우에는 움직임을 멈춘다.
첫쨰 줄에 지도 의 크기가 N,M 으로 주어진다
둘쨰 줄 부터 게임 캐릭터가 있는 칸의 좌표와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다 d 의 값은 다음과 같다.

0: 북쪽
1: 동쪽
2: 남쪽
3: 서쪽
셋째 줄 부터 맵이 육지인지 바다인지 입력한다 = 맵의 정보를 입력

0: 육지
1: 바다

해결

n, m = map(int, input().split())
x, y, d = map(int, input().split())
visited = [[0] * m for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
map = [list(map(int, input().split())) for _ in range(n)]

# 현재 위치를 방문 처리
visited[x][y] = 1


# 왼쪽으로 이동 표현
def turn_left():
    global d
    d -= 1  # 왼쪽으로 90도 회전은 -1 차감 한것과 똑같다
    if d == -1:  # 단 이떄 0 -> 3 으로 갈떄는 if 조건문을 사용하여 3으로 초기화
        d = 3

count = 1
turn_time = 0

while True:
    turn_left() # 왼쪽으로 이동 
    nx = x + dx[d]
    ny = x + dy[d]
    
    if d[nx][ny] == 0 and map[nx][ny] == 0:
        d[nx][ny] = 1
        x,y = nx,ny
        count += 1
        turn_time = 0
        continue
    
    else:
        turn_time += 1
    
    if turn_time == 4: # 네방향 전부 이동 불가인경우
        nx = x - dx[d]
        ny = y - dy[d]
        
        if map[nx][ny] == 0: # 뒤로 이동 할수 있는경우
            x,y = nx,ny
        else: # 뒤에가 바다인경우 
            break
        turn_time = 0
        

print(count)