CH2.구현
이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다룸.
- 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법.
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제.
🗨 예제 4-1 <상하좌우>
p.110 (문제 길어서 생략)
문제 유형 : 시뮬레이션
입력 조건
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1<=N<=100)
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1<=이동 횟수<=100)
L : 왼쪽으로 한 칸 이동
R : 오른쪽으로 한 칸 이동
U : 위로 한 칸 이동
D : 아래로 한 칸 이동출력 조건
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.
👆 입력으로 받은 L,R,U,D를 data 리스트에 넣고 for문을 돌리면서 x,y좌표의 값이 N*N 정사각형 공간을 벗어나지 않는지 확인했다.
N = int(input())
data = list(input().split())
x = 0
y = 0
for v in data:
if v=='R':
if (y+1)>=N:
continue
else:
y+=1
elif v=='L':
if (y-1)<0:
continue
else:
y-=1
elif v=='U':
if (x-1)<0:
continue
else:
x-=1
elif v=='D':
if (x+1)>=N:
continue
else:
x+=1
print(x+1,y+1)🗨 예제 4-2 <시각>
p.113
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시간이다.
- 00시 00분 03초
- 00시 13분 30초
반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.
- 00시 02분 55초
- 01시 27분 45초
문제 유형 : 완전 탐색
입력 조건
- 첫째 줄에 정수 N이 입력된다.(0<=N<=23)
출력 조건
- 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
👆 첨에 중복순열로 풀려고 끙끙댔다... permutation(?) 써가면서..^^ 풀이 보니까, 문제의 시간제한이 2초이기 때문에 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제였다.
N = int(input())
count=0
for i in range(N+1):
for j in range(60):
for k in range(60):
# 3이 문자열에 하나라도 포함되면 count 증가.
if '3' in str(i)+str(j)+str(k): count+=1
print(count)🗨 왕실의 나이트
p.115 (문제 생략)
문제 유형 : 시뮬레이션
입력 조건
- 첫째 줄에 8*8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.
나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기출력 조건
- 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.
👆 첨에 구현할 때, 유니코드로 변환하는 ord 함수를 몰랐기 때문에, column('a'~'z') 리스트를 따로 두고, 입력받은 column을 column 리스트에서 찾아 index를 반환받는 방법으로 구현했었다.
그리고 dx,dy를 따로 저장해서 좌표 계산을 진행했는데, 풀이를 보니 (dx,dy) 한번에 튜플로 구현해서 리스트에 저장하는 방법도 있었다.
data = list(input())
col = data[0]
row = int(data[1])
col_data = ['a','b','c','d','e','f','g','h']
col_index = col_data.index(col)+1
## 이부분을 다르게 고칠 수 있다
# col_index = int(ord(data[0]))-int(ord('a'))+1
#ord 함수 : 해당 문자의 유니코드 값을 반환
# a~z : 97~112에 해당함.
count = 0
dx = [2,2,-2,-2,1,-1,1,-1]
dy = [-1,1,1,-1,-2,-2,2,2]
## 이부분도 다르게 고칠 수 있음 dx,dy -> steps 로 고치고 for문을
# for step in steps : 로 하면 더 간결함
# steps = [(2,-1),(2,1),(-2,1),(-2,-1),(1,-2),(-1,-2),(1,2),(-1,2)]
for i in range(0,8):
m_x = col_index+dx[i]
m_y = row + dy[i]
if 0<m_x<=8 and 0<m_y<=8:
count+=1
print(count)🗨 게임 개발
p.118 (문제 생략)
문제 유형 : 시뮬레이션
입력 조건
- 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다.(3<=N,M<=50)
- 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A,B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.
0 : 북쪽
1 : 동쪽
2 : 남쪽
3 : 서쪽- 셋째 줄부터 맵이 육지인지 바다인지에 대한 저어보가 주어진다 N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다.
0 : 육지
1 : 바다출력 조건
- 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.
캐릭터 움직임의 매뉴얼 조건
- 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향) 부터 차례대로 갈 곳을 정한다.
- 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
- 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
👆 어질어질...빠르게 포기 후 해설봄
# N, M을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())
# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리
# 전체 맵 정보를 입력받기
array = []
for i in range(n):
array.append(list(map(int, input().split())))
# 북, 동, 남, 서 방향 정의
# ex. 북쪽을 보고 있는 경우, 앞으로 전진하면 (x-1,y) 가 되므로
# (dx,dy) = (-1,0)
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)참고
- 일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx,dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.
- 2차원 리스트 선언시, 컴프리헨션 문법을 사용해 초기화한다.
- turn_left() 함수에서 global 키워드를 사용했는데, 이는 정수형 변수인 direction 변수가 함수 바깥에서 선언된 전역변수이기 때문이다.
