반응형
[4] 실전 문제
1. 구현
#4-1. 게임 개발(Page118)
아이디어 : 전형적인 시뮬레이션 문제이다.
방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를만들어 방향을 정하는 것이 효과적이다.
# 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())))
# 북, 동, 남, 서 방향 정의
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)
#4-2 럭키 스트레이트(Page321)
아이디어 : 정수형 데이터가 입력으로 들어왔을 때, 이를 각 자릿수로 구분하여 합을 계산한다.
파이썬의 경우 입력받은 데이터가 문자열 형태로이므로, 문자열에서 각 문자를 하나씩 확인하며 정수하영으로 변환한 뒤에 그 값을 합 변수에 더할 수 있다.
n = input()
length = len(n) # 점수값의 총 자릿수
summary = 0
# 왼쪽 부분의 자릿수 합 더하기
for i in range(length // 2):
summary += int(n[i])
# 오른쪽 부분의 자릿수 합 더하기
for i in range(length // 2, length):
summary -= int(n[i])
# 왼쪽 부분과 오른쪽 부분의 자릿수 합이 동일한지 검사
if summary == 0:
print("LUCKY")
else:
print("READY")
#4-3. 문자열 압축(Page323)
아이디어 : 문자열의 길이가 1,000 이하이기 때문에 가능한 모든 경우의 수를 탐색하는 완전 탐색을 수행할 수 있다.
def solution(s):
answer = len(s)
#1개 단위(step)부터 압축 단위를 늘려가며 확인
for step in range(1, len(s) // 1):
compressed = ""
prev = s[0:step] #앞에서부터 step만큼의 문자열 추출
count = 1
# 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
for j in range(step, len(s), step):
#이전 상태와 동일하다면 압축 횟수(count) 증가
if prev == s[j:j + step]:
count += 1
#다른 문자열이 나왔다면(더 이상 압축하지 못하는 경우라면)
else:
compressed += str(count) + prev if count >= 2 else prev
prev = s[j:j + step] #다시 상태 초기화
count = 1
#남아 있는 경우 문자열에 대해서 처리
compressed += str(count) + prev if count >= else prev
#만들어지는 압축 문자열이 가장 짧은 것이 정답
answer = min(answer, len(compressed))
return answer
s = "aabbaccc"
print(solution(s))
#4-4. 자물쇠와 열쇠(Page325)
아이디어 : 완전 탐색을 수월하게 하기 위해서 자물쇠 리스트의 크기를 3배 이상으로 변경하면 계산이 수월해진다.
또한 자물쇠의 모든 흠을 채울 수 있는지 확인하기 위해 자물쇠 리스트에 열쇠 리스트의 값을 더한 뒤에, 더한 결과를 확인했을 때 자물쇠 부분의 모든 값이 정확히 1인지 확인한다.
# 2차원 리스트 90도 회전
def rotate_a_matrix_by_90_degree(a):
n = len(a) # 행 길이 계산
m = len(a[0]) #열 길이 계산
result = [[0] * n for _ in range(m)] #결과 리스트
for i in range(n):
for j in range(m):
result[j][n - i - 1] = a[i][j]
return result
# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
lock_length = len(new_lock)//3
for i in range(lock_length, lock_length *2):
for j in range(lock_length, lock_length *2):
if new_lock[i][j] != 1:
return False
return True
def solution(key, lock):
n = len(lock)
m = len(key)
#자물쇠의 크기를 기준으로 3배로 변환
new_lock = [[0]*(n*3) for _ in range(n*3)]
#새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
for i in range(n):
for j in range(n):
new_lock[i+n][j+n] = lock[i][j]
# 4가지 방향에 대해서 확인
for rotation in range(4):
key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
for x in range(n*2):
for y in range(n*2):
#자물쇠에 열쇠 끼어 넣기
for i in range(m):
for j in range(m):
new_lock[x+i][y+j] += key[i][j]
#새로운 자물쇠에 열쇠가 정확히 들어맞는지 검사
if check(new_lock) == True:
return True
#자물쇠에서 열쇠를 다시 빼기
for i in range(m):
for j in range(m):
new_lock[x+i][y+j] -= key[i][j]
return False
key = [[0,0,0], [1,0,0], [0,1,1]]
lock = [[1,1,1], [1,1,0], [1,0,1]]
print(solution(key,lock))
#4-5 뱀(Page327)
아이디어 : 전형적인 시뮬레이션 문제 유형이다.
2차원 배열상의 특정 위치에서 동,남,서,북의 위치로 이동하는 기능을 구현해야 한다. (뱀은 처음에 오른쪽을 바라보고 있음)
매 시점마다 뱀이 존재하는 위치를 항상 2차원 리스트에 기록해야 한다.
n = int(input())
k = int(input())
data = [[0] * (n+1) for _ in range(n+1)] # 맵 정보
info = [] #방향 회전 정보
# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
a,b = map(int, input().split())
data[a][b] = 1
# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
x,c = input().split()
info.append((int(x),c))
# 처음에는 오른쪽으로 보고 있으므로(동,남,서,북)
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def turn(direction, c):
if c == "L":
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
return direction
def simulate():
x,y = 1, 1 # 뱀의 머리 위치
data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
direction = 0 #처음에는 동쪽을 보고 있음
time = 0 #시작한 뒤에 지난 '초' 시간
index = 0 #다음에 회전할 정보
q = [(x,y)] #뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)
while True:
nx = x + dx[direction]
ny = y + dy[direction]
#맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
#사과가 없다면 이동 후에 꼬리 제거
if data[nx][ny] == 0:
data[nx][ny] = 2
q.append((nx,ny))
px, py = q.pop(0)
data[px][py] = 0
#사과가 있다면 이동 후에 꼬리 그대로 두기
if data[nx][ny] == 1:
data[nx][ny] = 2
q.append((nx,ny))
#벽이나 뱀의 몸통과 부딪혔다면
else:
time += 1
break
x,y = nx, ny #다음 위치로 머리를 이동
time += 1
if index < 1 and time == info[index][0]: #회전할 시간인 경우 회전
direction = turn(direction, info[index][1])
index += 1
return time
print(simulate())
#4-6 기둥과 보 설치(Page329)
아이디어 : 전형적인 시뮬레이션 문제이다. 전체 명령의 개수는 총 1,000개 이하이다. 전체 명령의 개수를 M이라 할 때, 시간 복잡도 O(M^2)으로 해결하는 것이 이상적일 것이다. 하지만 본 문제의 시간 제한은 5초로 넉넉한 편이므로 O (M^3)의 알고리즘을 이용해도 정답 판정을 받을 수 있다.
#현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
for x,y,stuff in answer:
if stuff == 0: #설치된 것이 '기둥'인 경우
# '바닥 위' 혹은 '보의 한쪽 끝부분 위' 혹은 '다른 기둥 위'라면 정상
if y == 0 or [x-1, y, 1] in answer or [x,y,1] in answer or [x,y-1,0] in answer:
continue
return False #아니라면 거짓(False) 반환
elif stuff == 1: #설치된 것이 '보'인 경우
#'한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
if [x,y-1,0] in answer or [x+1,y-1, 0] in answer or ([x-1, y, 1] in answer and [x+1,y,1] in answer):
continue
return False #아니라면 거짓(False) 반환
return True
def solution(n, build_frame):
answer = []
for frame in build_frame: #작업(frame)의 개수는 최대 1,000개
x,y,stuff,operate = frame
if operate == 0: #삭제하는 경우
answer.remove([x,y,stuff]) #일단 삭제를 해본 뒤에
if not possible(answer): #가능한 구조물인지 확인
answer.append([x,y,stuff]) #가능한 구조물이 아니라면 다시 설치
if operate == 1: #설치하는 경우
answer.append([x,y,stuff]) #일단 설치를 해본 뒤에
if not possible(answer): #가능한 구조물인지 확인
answer.remove([x,y,stuff]) #가능한 구조물이 아니라면 다시 제거
return sorted(answer)
#4-7. 치킨 배달(Page332)
아이디어 : 기존에 존재하는 치킨집을 줄여서 최대 M개로 유지하면서, 일반 집들로부터 M개이 치킨집까지의 거리를 줄이는 것이 목표이다. 이후에 도시의 치킨 거리 합의 최솟값을 계산하면 된다.
파이썬의 조합라이브러리를 제공하므로, 이를 이용하여 모든 경우를 간단히 계산할 수 있다.
from itertools import combinations
n,m = map(int,input().split())
chichken, house = [], []
for r in range(n):
data = list(map(int, input().split()))
for c in range(n):
if data[c] == 1:
house.append((r,c)) #일반 집
elif data[c] == 2:
chicken.append((r,c)) #치킨 집
#모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 계산
candiates = list(combinations(chicken, m))
#치킨 거리의 합을 계산하는 함수
def get_sum(candidate):
result = 0
#모든 집에 대하여
for hx, hy in house:
#가장 가까운 치킨집 찾기
temp = 1e9
for cx, cy in candidate:
temp = min(temp, abs(hx-cx) + abs(hy-cy))
#가장 가까운 치킨집까지의 거리를 더하기
result += temp
#치킨 거리의 합 반환
return result
#치킨 거리의 합의 최소를 찾아 출력
result = 1e9
for candidate in candidates:
result = min(result, get_sum(candidate))
print(result)
#4-8. 외벽 점검(Page335)
아이디어 : 주어지는 데이터의 개수가 적을 때는 모든 경우를 일일이 확인하는 완전 탐색으로 접근해볼 수 있다.
문제에서 찾고자 하는 값은 '투입해야 하는 친구 수의 최솟값'이다. 따라서 친구를 나열하는 모든 경우의 수를 각각 확인하여 친구를 최소 몇 명 배치하면 되는지 계산하면 문제를 해결할 수 있다.
from itertools import permutations
def solution(n,weak,dist):
#길이를 2배로 늘려서 '원형'을 일자 형태로 변형
length = len(weak)
for i in range(length):
weak.append(weak[i] + n)
answer = len(dist) + 1 #투입할 친구 수의 최솟값을 찾아야 하므로 len(dist) +1로 초기화
#0부터 length-1까지의 위치를 각각 시작점으로 설정
for start in range(length):
#친구를 나열하는 모든 경우의 수 각각에 대하여 확인
for friends in list(permutations(dist,len(dist))):
count = 1 #투입할 친구의 수
#해당 친구가 점검을 할 수 있는 마지막 위치
position = weak[start] + friends[count-1]
#시작점부터 모든 취약 지점을 확인
for index in range(start, start + length):
#점검할 수 있는 위치를 벗어나는 경우
if position < weak[index]:
count += 1 #새로운 친구를 투입
if count > len(dist): #더 투입이 불가능하다면 종료
break
position = weak[index] + friends[count - 1]
answer = min(answer, count) #최솟값 계산
if answer > len(dist):
return -1
return answer반응형