목차
- 한밤의 습격자
- 2회 윷놀이 최강자전
- DP같은 PQ
- 나누어 떨어뜨리기
- 수영장
1. 한밤의 습격자
풀이
from collections import deque
"""
* BFS 문제의 변형입니다.
* 일반 BFS 미로찾기에, 낮/밤에는 지도가 달라지는 기믹을 적용합니다.
* visited 외에 waited를 하나 더 만들어서, 가만히 기다리는 턴 수를 기록합니다.
* 가만히 기다리는 턴 수는 최대 9턴(낮+밤이 한바퀴 도는 동안)까지만 기다려보면 되기 때문입니다.
* 새로운 곳에 도달하면, 상하좌우 이동하는 것 외에 1~9턴 대기하고 출발하는 것도 같이 시도해 보는 것이지요!
* 또한 지도를 하나 더 만들어, 밤에는 밤 지도를 참고합니다.
"""
from copy import deepcopy
def solution(maze):
N = len(maze)
M = len(maze[0])
q = []
q.append((0, 0, 0))
di = [0, 0, 1, -1, 0]
dj = [1, -1, 0, 0, 0]
maze_night = deepcopy(maze)
for i in range(N):
for j in range(M):
if maze[i][j] == 2:
maze_night[i][j] = 3
elif i > 0 and maze[i-1][j] == 2:
maze_night[i][j] = 3
elif i < N-1 and maze[i+1][j] == 2:
maze_night[i][j] = 3
elif j > 0 and maze[i][j-1] == 2:
maze_night[i][j] = 3
elif j < M-1 and maze[i][j+1] == 2:
maze_night[i][j] = 3
mazes = [maze, maze_night]
visited = [[0 for _ in range(M)] for _ in range(N)]
waited = [[0 for _ in range(M)] for _ in range(N)]
while q:
i, j, t = q.pop(0)
d = (t // 5) % 2 == 1
if mazes[d][i][j] == 3:
continue
if (i, j) == (N-1, M-1):
return visited[i][j]
for di_, dj_ in zip(di, dj):
new_i = i + di_
new_j = j + dj_
if (new_i, new_j) == (i, j):
if waited[new_i][new_j] >= 10:
continue
q.append((new_i, new_j, t + 1))
waited[new_i][new_j] += 1
visited[new_i][new_j] += 1
if new_i < 0 or new_i >= N or new_j < 0 or new_j >= M:
continue
if visited[new_i][new_j] > 0:
continue
next_d = ((t+1) // 5) % 2 == 1
if mazes[next_d][new_i][new_j] == 0 or mazes[next_d][new_i][new_j] == 2:
q.append((new_i, new_j, t + 1))
visited[new_i][new_j] = visited[i][j] + 1
return -1
Testcase
# 테스트 1
입력값 〉 [[0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0], [0, 1, 0, 2, 0, 0], [1, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 0], [1, 1, 1, 0, 2, 0]]
기댓값 〉 222. 2회 윷놀이 최강자전
풀이
"""
* 이번 윷놀이 문제는 DP 문제입니다.
* 따져줘야 하는 경우의 수가 매우 많기 때문에, 이것을 BFS로 하기에는 적절하지 않습니다.
* 따져줘야 하는 종류는 아래와 같습니다.
*
* 1. 시작점에서 출발하여 도개걸
* 2. 숏컷을 타고 도개걸
* 3. 시작점에서 출발하여 윷모 + 도개걸윷모
* 4. 숏컷을 타고 윷모 + 도개걸윷모
* 5. 시작점에서 출발할아여 윷모 + 숏컷을 타고 도개걸윷모
* 6. 숏컷을 타고 윷모 + 숏컷을 타고 도개걸윷모
*
* 아주 다양한 경우의 수가 있고, 코드에서 복잡한 숫자들과 for, if문은 모두 위를 커버하기 위함입니다.
"""
def solution(N, edges):
dp = [float('inf') for _ in range(N+1)]
dp[0] = 0
first_moves = [0, 4, 5]
second_moves1 = [1, 2, 3]
second_moves2 = [1, 2, 3, 4, 5]
for i in range(N):
shortcuts = list(map(lambda e: e[1] - 1,
filter(lambda e: e[0] == i, edges)))
for start in [i] + shortcuts:
for move1 in first_moves:
j = start + move1
if move1 > 0:
shortcuts2 = list(map(lambda e: e[1] - 1,
filter(lambda e: e[0] == j, edges)))
else:
shortcuts2 = []
for start2 in [j] + shortcuts2:
second_moves = second_moves1 if move1 == 0 else second_moves2
for move2 in second_moves:
k = start2 + move2
if k <= N:
dp[k] = min(dp[k], dp[i] + 1)
return dp[N]Testcase
# 테스트 1
입력값 〉 34, [[1, 4], [6, 12], [15, 24]]
기댓값 〉 3
# 테스트 2
입력값 〉 100, [[12, 40], [18, 53], [59, 89]]
기댓값 〉 53. DP같은 PQ
풀이
from heapq import heappop, heappush
"""
* DP문제처럼 보이지만, 우선순위 큐 문제입니다.
* DP로 풀려고 하면 O(N*k) 연산을 해야 하므로, 너무 느립니다.
* 우선순위 큐로 따질 필요가 없는 경우는 버려서 빠르게 연산합니다.
"""
def solution(arr, k):
heap = []
heappush(heap, (-arr[0], 0))
for i in range(1, len(arr)):
while heap and heap[0][1] < i-k:
heappop(heap)
heappush(heap, (heap[0][0] - arr[i], i))
while heap[0][1] != len(arr) - 1:
heappop(heap)
return -heappop(heap)[0]Testcase
# 테스트 1
입력값 〉 [1, -1, -20, 4, -7, 5], 2
기댓값 〉 9
# 테스트 2
입력값 〉 [3, -4, 5, 1, 3, -5, -12, 4, -4, 5], 3
기댓값 〉 214. 나누어 떨어뜨리기
풀이
"""
* 수학적인 센스가 필요한 문제입니다.
* numsDivided의 숫자를 모두 나누어 떨어지게 하려면,
* numsDivided의 최대공약수를 나누어 떨어지게 하면 됩니다.
* 이것을 이용해서 나눗셈 연산을 최소로 하는 것이 핵심!
"""
from math import gcd
def solution(numsDivide, numsDivided):
arr = sorted(list(set(numsDivide)))
div = gcd(*list(set(numsDivided)))
for n in arr:
if div % n == 0:
return len(list(filter(lambda x: x < n, numsDivide)))
return -1Testcase
# 테스트 1
입력값 〉 [2, 9, 3, 6, 2, 4, 3], [9, 18, 27, 9, 15]
기댓값 〉 25. 수영장
풀이
from heapq import heappush, heappop
def solution(heights):
heap = []
n = len(heights)
m = len(heights[0])
visited = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if i == 0 or j == 0 or i == n-1 or j == m-1:
heappush(heap, (heights[i][j], (i, j)))
visited[i][j] = 1
directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
water = 0
while heap:
h, pos = heappop(heap)
i, j = pos
for direction in directions:
new_i = i + direction[0]
new_j = j + direction[1]
if (new_i < 0 or new_i > n-1 or new_j < 0 or new_j > m-1):
continue
if visited[new_i][new_j] > 0:
continue
visited[new_i][new_j] = 1
if h > heights[new_i][new_j]:
water += h - heights[new_i][new_j]
heights[new_i][new_j] = h
heappush(heap, (heights[new_i][new_j], (new_i, new_j)))
return waterTestcase
# 테스트 1
입력값 〉 [[3, 4, 5, 4, 3, 3], [3, 2, 1, 1, 2, 3], [4, 2, 1, 1, 2, 3], [3, 3, 3, 3, 5, 3]]
기댓값 〉 12
# 테스트 2
입력값 〉 [[3, 3, 3, 3, 3, 3], [3, 1, 3, 1, 1, 3], [3, 1, 3, 2, 1, 3], [3, 3, 3, 3, 3, 3]]
기댓값 〉 11출처
해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.
모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.
Comment