구현, 피지컬 싸움

PS에서 구현이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀건 소스 코드를 작성하는 과정은 필수이므로 결국 구현 문제유형은 모든 PS 유형을 포함하는 개념이다.

우리는 알고리즘 문제를 보고, 문제 풀이 방법을 고민한다. 고민 후 문제에 대한 풀이 방법이 떠오른다고 정답을 받을 수 있는 것은 아니다. 생각한 문제 풀이 방법을 프로그래밍 언어로 정확히 구현해야 한다.

결국 구현 유형의 문제는 ‘풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기기 어려운 문제’를 의미한다. 그런 의미에서 구현 유형의 문제는 코딩 피지컬을 요구하는 문제라고도 할 수 있다.

상하좌우

N*N의 좌표공간에서 RRRUDD와 같은 방향을 나타내는 문자열이 들어왔을 때 최종 도착 지점의 좌표를 출력하는 문제이다.

  • L: 왼쪽, R: 오른쪽, U: 위, D: 아래
  • N*N 크기의 공간을 벗어나는 움직임은 무시

풀이

1
2
3
4
5
6
7
8
9
10
11
12
w=int(input())
x,y=1,1
move=input().split()
d={'L':-1,'R':1,'U':-1,'D':1}
for mov in move:
    if mov in ['U', 'D']:
        t_x=x+d[mov]
        if 0<t_x<=w: x=t_x
    else:
        t_y=y+d[mov]
        if 0<t_y<=w: y=t_y
print(x,y)

구현 유형 문제의 특징은 문제의 요구사항대로 구현하면 된다는 것이다. 이 때 N*N 크기의 공간을 벗어나는 움직임의 예외 처리를 정확히 해주어야 한다.

시각

정수 N이 입력되었을 때 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하는 문제이다.

풀이

1
2
3
4
5
6
count=0
for h in range(int(input())+1):
    for m in range(60):
        for s in range(60):
            if '3' in str(h)+str(m)+str(s): count+=1
print(count)

이 문제의 경우 모든 시각의 경우를 하나씩 모두 세서 풀어도 문제가 되지 않는다. N이 23으로 (최대로) 입력되었다고 해도 84300가지밖에 존재하지 않기에 시각을 1씩 증가시키면서 3이 포함되어 있는지 검사해도 무방하다.

왕실의 나이트

8*8 좌표 평면에서 특정 방향으로만 이동할 수 있는데, 이 때 이동할 수 있는 좌표의 경우의 수를 구하는 문제이다.

이동 방법은 다음과 같다.

  • 수평으로 두 칸 이동 -> 수직으로 한 칸 이동
  • 수직으로 두 칸 이동 -> 수평으로 한 칸 이동

풀이

1
2
3
4
5
6
7
8
9
cur=input()
mov=[[1,-2],[2,-1],[2,1],[1,2],[-1,2],[-2,1],[-2,1],[-1,-2]]
x_=['a','b','c','d','e','f','g','h']
x=x_.index(cur[0])+1
y=int(cur[1])
count=0
for i in mov:
    if 0<x+i[0]<=8 and 0<y+i[1]<=8: count+=1
print(count)

앞서 풀었던 상하좌우 문제와 거의 똑같은 유형의 문제이다. 이동할 수 있는 경우의 수는 8가지임으로 mov에 모든 경우의 수를 집어넣고 좌표 공간에서 벗어나는지만 확인하면 된다.

게임개발

특정 조건 하에서 좌표 공간을 이동할 때 방문한 좌표의 수를 구하는 문제이다.

이동 조건은 다음과 같다.

  • 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 90도 회전)
  • 왼쪽 방향에 방문하지 않은 칸이 존재하면 -> 왼쪽 방향으로 회전 후 왼쪽으로 한 칸 전진
  • 왼쪽 방향에 방문하지 않은 칸이 없다면 -> 왼쪽 방향으로 회전 후 처음 단계로 돌아가기
  • 네 방향 모두 방문했거나 바다로 되어 있다면 바라보는 방향에서 한 칸 뒤로 가고 처음으로 돌아가기 (단, 뒤쪽 방향이 바다라서 뒤로 못가면 멈추기)

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
w,h=map(int,input().split())
x,y,d=map(int,input().split())
m=[list(map(int,input().split())) for _ in range(w)]

v=[[0]*h for _ in range(w)]
v[x][y]=1

dx,dy=[-1,0,1,0],[0,1,0,-1]

count=1
turn=0

def turnLeft():
    global d
    d -= 1
    if d == -1: d=3

while 1:
    turnLeft()
    nx,ny=x+dx[d],y+dy[d]
    if v[nx][ny]==0 and m[nx][ny]==0:
        v[nx][ny]=1
        x,y=nx,ny
        count+=1
        turn=0
        continue
    else: turn+=1
    if turn==4:
        nx,ny=x-dx[d],y-dy[d]
        if m[nx][ny]==0:x,y=nx,ny
        else: break
        turn=0

print(count)

문제가 길지만 사실상 문제에 나온 요구사항을 그대로 코드에 옮기기만 하면 되는 문제이다. 방문 체크를 위한 배열 v, d를 바탕으로 움직이는 방향을 dx, dy로 변수화하고, 움직인 횟수 count, 방향을 돌리고 모든 방향을 돌았을 때 예외처리 하기위해 turn을 선언한다.

방향 관련 구현 유형의 문제

위와 같이 상하좌우로 움직이는 좌표 공간에서 “방향”을 설정해서 이동하는 문제는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다. 위 예제에서 캐릭터를 움직일 때 동, 서, 남, 북 방향을 dx, dy로 별도로 리스트화해서 생각하면 if d==1: ~ 등의 불필요한 구현을 없앨 수 있다.