새로운 게임 2
Q. 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다.
새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다.
말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다.
체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.
턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.
- A번 말이 이동하려는 칸이
1) 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
- A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
- 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
2) 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
- A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
- A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
3) 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
4) 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.
k = 4 # 말의 개수
chess_map = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
start_horse_location_and_directions = [
[0, 0, 0],
[0, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
# 동 서 북 남
# →, ←, ↑, ↓
dr = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
def get_game_over_turn_count(horse_count, game_map, horse_location_and_directions):
n = len(game_map)
board = [[[] for _ in range(n)] for _ in range(n)]
for i in range(horse_count):
r, c, d = horse_location_and_directions[i]
board[r][c].append(i)
horses_copy = [[r, c, d] for r, c, d in horse_location_and_directions]
def move():
for horse_index in range(horse_count):
r, c, d = horses_copy[horse_index]
new_r = r + dr[d]
new_c = c + dy[d]
# 3. if out-of-range or blue cell, flip the direction (n + 2 % 4)
if new_r < 0 or new_r >= n or new_c < 0 or new_c >= n or game_map[new_r][new_c] == 2:
# new_d = (d + 2) % 4
new_d = (d + 1) % 2 + (d // 2) * 2
horses_copy[horse_index][2] = new_d
new_r = r + dr[new_d]
new_c = c + dy[new_d]
# if still out_of_range or blue, don't move with only direction changed
if new_r < 0 or new_r >= n or new_c < 0 or new_c >= n or game_map[new_r][new_c] == 2:
continue
current_stack = board[r][c]
current_horse_index_within_stack = current_stack.index(horse_index)
moving_horses = current_stack[current_horse_index_within_stack:]
del current_stack[current_horse_index_within_stack:]
# 2. if red, reverse the stack order for moving horses stack
if game_map[new_r][new_c] == 1:
# No moving_horses = moving_horses.reverse() -> return NULL
# maybe you want moving_horses = moving_horses[::-1]
moving_horses.reverse()
# update horse_copy based on moving_horses
for horse in moving_horses:
horses_copy[horse][0] = new_r
horses_copy[horse][1] = new_c
# no append since it appends 'list' not its elements
# use += or extend
board[new_r][new_c].extend(moving_horses)
# check if the game can end by having 4 stack
if len(board[new_r][new_c]) >= 4:
return True
# game has not ended
return False
for turn in range(1, 1001):
if move():
return turn
else:
return -1
print(get_game_over_turn_count(k, chess_map, start_horse_location_and_directions)) # 2가 반환 되어야합니다
start_horse_location_and_directions = [
[0, 1, 0],
[1, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
print("정답 = 9 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))
start_horse_location_and_directions = [
[0, 1, 0],
[0, 1, 1],
[0, 1, 0],
[2, 1, 2]
]
print("정답 = 3 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))Note
Why continue?
By using continue, the function skips the remainder of the current iteration for that specific horse and moves on to the next horse in the list. This is important Because:
- Each horse's move is independent of the others (until they possibly stack).
- Even if one horse cannot move after reversing its direction, other horses still need their moves processed for that turn.
- Using continue ensures that the loop does not prematurely exit and all horses get a chance to move (or attempt to move) during that turn.
If break were used instead of continue, it would exit the loop entirely as soon as any horse encountered a condition where it couldn't move after reversing direction. This would mean that any subsequent horses would not get their turn to move in that round, which could lead to incorrect behavior according to the game's rules.
구슬탈출
Q. 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
보드를 나타내는 2차원 배열 game_map이 주어진다.
이 때, 보드의 행, 열의 길이는 3이상 10 이하다.
보드 내에 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다.
'.'은 빈 칸을 의미하고,
'#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며,
'O'는 구멍의 위치를 의미한다.
'R'은 빨간 구슬의 위치,
'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 True, 없으면 False를 반환한다.
from collections import deque
game_map = [
["#", "#", "#", "#", "#"],
["#", ".", ".", "B", "#"],
["#", ".", "#", ".", "#"],
["#", "R", "O", ".", "#"],
["#", "#", "#", "#", "#"],
]
def is_available_to_take_out_only_red_marble(game_map):
n = len(game_map)
m = len(game_map)
# up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = set()
# set 일때는 add instead of 'append'
# Initialize
rx, ry, bx, by = -1, -1, -1, -1
for i in range(n):
for j in range(m):
if game_map[i][j] == "R":
rx, ry = i, j
if game_map[i][j] == "B":
bx, by = i, j
# BFS Initialization + move count
# deque([(a, b, c)])
queue = deque([(rx, ry, bx, by, 0)])
# add to visited
visited.add((rx, ry, bx, by))
def move_until_blocked(x, y, dx, dy):
steps = 0
while game_map[x + dx][y + dy] != '#' and game_map[x][y] != 'O':
x += dx
y += dy
steps += 1
return x, y, steps
while queue:
rx, ry, bx, by, try_count = queue.popleft()
if try_count > 10:
break
for dx, dy in directions:
new_rx, new_ry, r_steps = move_until_blocked(rx, ry, dx, dy)
new_bx, new_by, b_steps = move_until_blocked(bx, by, dx, dy)
# check if it can be added to visited (valid)
# so check if game ended
if game_map[new_bx][new_by] == 'O':
continue # Blue in hole is a fail state, skip to next directions
if game_map[new_rx][new_ry] == 'O':
return True # Red in hole without blue is a win state
# if collide (same place), further moved one should be behind because it was further away from the wall or hole
if new_rx == new_bx and new_ry == new_by:
if r_steps > b_steps:
new_rx -= dx
new_ry -= dy
else:
new_bx -= dx
new_by -= dy
# if not in visited, add it to visited and queue
if (new_rx, new_ry, new_bx, new_by) not in visited:
visited.add((new_rx, new_ry, new_bx, new_by))
queue.append((new_rx, new_ry, new_bx, new_by, try_count + 1))
return False
print(is_available_to_take_out_only_red_marble(game_map)) # True 를 반환해야 합니다
game_map = [
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", ".", "O", ".", ".", ".", ".", "R", "B", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = False / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))
game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", ".", ".", "R", "#", "B", "#"],
["#", ".", "#", "#", "#", "#", "#"],
["#", ".", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", ".", "#"],
["#", "O", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))Note: Queue
1) Initialize visited using set
visited = set()
visited.add((rx, ry, bx, by))
2) Initialize queue
queue = deque([(rx, ry, bx, by, count if needed)])
3) Directions set
up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
4) If needed: Functions for movement within the big function
5) while queue + new direction calculation
while queue:
rx, ry, bx, by, count = queue.popleft()
if count > 10:
break
for dx, dy in directions:
new_rx, new_ry= rx + dx, ry + dy
... 6) if needed to move to certain directions
define turn_left or turn_back etc. function that returns new d value
rx, ry, d = queue.popleft()
for _ in range(4)
d = rotate_to_left(d)
new_rx, new_ry= rx + directions[d][0], ry + directions[d][1]7) After handling fail case using break or continue,
add to visited & queue
if (new_rx, new_ry, new_bx, new_by) not in visited:
visited.add((new_rx, new_ry, new_bx, new_by))
queue.append((new_rx, new_ry, new_bx, new_by, moves + 1))8) dont forget return at the end
치킨배달
Q. 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.
이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 20은 빈 칸, 1은 집, 2는 치킨집이다.
(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.
(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.
이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.
도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 반환하시오.
입력
N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
또한 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
import itertools
n = 5
m = 3
city_map = [
[0, 0, 1, 0, 0],
[0, 0, 2, 0, 1],
[0, 1, 2, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 2],
]
def get_min_city_chicken_distance(n, m, city_map):
houses = []
chickens = []
for i in range(n):
for j in range(n):
if city_map[i][j] == 1:
houses.append((i, j))
if city_map[i][j] == 2:
chickens.append((i, j))
def distance(house, chicken):
return abs(house[0] - chicken[0]) + abs(house[1] - chicken[1])
# Minimize city chicken distance
min_city_chicken_distance = float('inf')
# chicken combinations (M length)
chicken_location_combinations = list(itertools.combinations(chickens, m))
for chicken_combination in chicken_location_combinations:
current_city_distance = 0
for house in houses:
min_distance = float('inf')
for chicken in chicken_combination:
min_distance = min(min_distance, distance(house, chicken))
current_city_distance += min_distance
# Update the minimum city chicken distance found
min_city_chicken_distance = min(min_city_chicken_distance,current_city_distance)
return min_city_chicken_distance
# 출력
print(get_min_city_chicken_distance(n, m, city_map)) # 5 가 반환되어야 합니다!
city_map = [
[1, 2, 0, 0, 0],
[1, 2, 0, 0, 0],
[1, 2, 0, 0, 0],
[1, 2, 0, 0, 0],
[1, 2, 0, 0, 0]
]
print("정답 = 11 / 현재 풀이 값 = ", get_min_city_chicken_distance(5,1,city_map))
city_map = [
[0, 2, 0, 1, 0],
[1, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[2, 0, 0, 1, 1],
[2, 2, 0, 1, 2]
]
print("정답 = 10 / 현재 풀이 값 = ", get_min_city_chicken_distance(5,2,city_map))Note
조합을 얻으려면?
모든 경우의 수를 구해야 하는 문제를 풀기 위해서는
특정 숫자들의 모든 조합을 얻어야 할 때가 있습니다.
그럴 때는 아래와 같이 itertools 모듈의 combinations 을 이용하시면 됩니다!
from itertools import combinations
itertools.combinations([1,2,3,4,5], 2) # [1,2,3,4,5] 에서 2개씩 뽑을 수 있는 조합을 다 가져와라
<itertools.combinations object at 0x10453acc0>
list(itertools.combinations([1,2,3,4,5], 2))
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
list(itertools.combinations([1,2,3,4,5], 3))
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]
min_city_chicken_distance = float('inf')
