구현(Implementation)

CONCEPT : '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'

- 메모리 제한을 유의하며 문제를 풀어야 함

완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

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

 

예제 1. 상하좌우

Q. 여행가 A가 최종적으로 도착하는 위치의 좌표를 구하시오

rule 1. N x N 크기의 정사각형 공간에 (1,1) 좌표 위치에서 여행을 시작한다.

rule 2. L, R, U, D 중 하나로 이동하고 지도밖으로 벗어나는 행동은 무시한다.

 

 

SH 풀이

n = int(input())
data = list(map(str, input().split()))

a, b = 1, 1
for i in data:
    if i == 'R':
        if 1<=b+1<=n:
            b+=1
    elif i == 'D':
        if 1<=a+1<=n:
            a+=1
    elif i == 'L':
        if 1<=b-1<=n:
            b-=1
    elif i == 'U':
        if 1<=a-1<=n:
            a-=1
print(a,b)

책 풀이

n = int(input())
x, y = 1, 1
plans = input().split()

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_types)):
        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)

 

예제 2. 시각

Q 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하시오.

 

tip. 완전 탐색 유형 - 가능한 경우의 수를 모두 검사해보는 탐색 방법.

n = int(input())

count=0
for i in range(n+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i)+str(j)+str(k):
                count+=1
print(count)

 

실전 1. 왕실의 나이트

Q. 8 x 8 좌표 평면 위의 특정한 위치에서 나이트가 이동할 수 있는 경우의 수를 구하시오.

rule 1. 나이트는 L자 형태로만 이동할 수 있다.

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

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

rule 2. 정원 밖으로는 나갈 수 없다.

rule 3. 행 위치는 1~8, 열 위치는 a ~ h로 표현한다.

 

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

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]
    if next_row>=1 and next_row<=8 and next_column >=1 and next_column <=8:
        result +=1
print(result)

 

SH 풀이

def solution(input_data):
    steps = [(-2,-1),(-2,1),(-1,2),(-1,-2),(1,2),(1,-2),(2,1),(2,-1)]
    x = int(ord(input_data[0])) - ord('a') + 1
    y = int(input_data[1])
    count = 0

    for i in steps:
        nx = x + i[0]
        ny = y + i[1]
        if nx > 8 or nx < 1 or ny > 8 or ny < 1:
            continue
        count += 1
    return count

 

실전 2. 게임 개발 - 시뮬레이션 유형

Q. 캐릭터가 있는 장소는 N x M 크기의 사각형이고, 각각의 칸은 육지 또는 바다이며 캐릭터는 동서남북 한 곳을 바라본다. 이때, 메뉴얼에 따라 캐릭터를 이동시킨 뒤, 캐릭터가 방문한 칸의 수를 구하시오.

rule 1. 현재 위치에서 현재 방향으로 기준으로 반시계 방향으로 90도 회전한 방향부터 차례대로 갈 곳을 정한다.

rule 2. 캐릭터의 왼쪽에 아직 가보지 않은 칸이 존재한다면, 왼쪽으로 회전 후 한칸 전진하고 없다면, 왼쪽으로 방향만 회전하고 1단계로 돌아간다.

rule 3. 만약 네 방향 모두 이미 가본 칸이거나 바다인 경우에는 바라보는 방향을 유지한 채로 한칸 뒤로가고 1단계로 돌아간다. (단, 이때 뒤쪽 방향이 바다인 칸이라 갈 수 없는 경우에는 움직임을 멈춘다.)

n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵 생성
d = [[0]*m for _ in range(n)]
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 전체 맵 정보 받아오기
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 북, 동, 남, 서 방향
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전
def turn_left():
    global direction
    direction -=1
    if direction == -1:
        direction =3

# 시뮬레이션 시작
count = 1
turn_time = 0
while True:
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 회전한 후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count+=1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time+=1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 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)