π 곡λΆνλ μ§μ§μνμΉ΄λ μ²μμ΄μ§?
[BAEKJOON python] 19238_μ€ννΈ νμ λ³Έλ¬Έ
728x90
λ°μν
μ€ννΈ νμ
μ€ννΈ νμλ μλμ λμ°©μ§λ‘ λ°λ €λ€μ€ λλ§λ€ μ°λ£κ° μΆ©μ λκ³ , μ°λ£κ° λ°λ₯λλ©΄ κ·Έ λ μ μ λ¬΄κ° λλ¨
νμ κΈ°μ¬λ μ€λ Mλͺ μ μΉκ°μ νμ°λ κ²μ΄ λͺ©ν
νλ μμμ N×N ν¬κΈ°μ 격μ, κ° μΉΈμ λΉμ΄ μκ±°λ λ²½μ΄ λμ¬ μμ
νμκ° λΉμΉΈμ μμ λ, μνμ’μ°λ‘ μΈμ ν λΉμΉΈ μ€ νλλ‘ μ΄λ
νΉμ μμΉλ‘ μ΄λν λ νμ μ΅λ¨κ²½λ‘λ‘λ§ μ΄λ
Mλͺ μ μΉκ°μ λΉμΉΈ μ€ νλμ μ μμΌλ©°, λ€λ₯Έ λΉμΉΈ μ€ νλλ‘ μ΄λ
μ¬λ¬ μΉκ°μ΄ κ°μ΄ νμΉνλ κ²½μ°λ μμ
νμ κΈ°μ¬λ ν μΉκ°μ νμ λͺ©μ μ§λ‘ μ΄λμν€λ μΌμ Mλ² λ°λ³΅
κ° μΉκ°μ μ€μ€λ‘ μμ§μ΄μ§ μμΌλ©°, μΆλ°μ§μμλ§ νμμ ν μ μκ³ , λͺ©μ μ§μμλ§ νμμμ λ΄λ¦΄ μ μμ
νμκΈ°μ¬κ° νμΈ μΉκ°μ κ³ λ₯Ό λλ νμ¬ μμΉμμ μ΅λ¨κ±°λ¦¬κ° κ°μ₯ 짧μ μΉκ°μ κ³ λ¦
μΉκ°μ΄ μ¬λ¬ λͺ μ΄λ©΄ κ·Έμ€ ν λ²νΈκ° κ°μ₯ μμ μΉκ°
κ·Έλ° μΉκ°λ μ¬λ¬ λͺ μ΄λ©΄ κ·Έμ€ μ΄ λ²νΈκ° κ°μ₯ μμ μΉκ°
νμμ μΉκ°μ΄ κ°μ μμΉμ μ μμΌλ©΄ κ·Έ μΉκ°κΉμ§μ μ΅λ¨κ±°λ¦¬λ 0
1) μ°λ£λ ν μΉΈ μ΄λν λλ§λ€ 1λ§νΌ μλͺ¨
2) ν μΉκ°μ λͺ©μ μ§λ‘ μ±κ³΅μ μΌλ‘ μ΄λμν€λ©΄, κ·Έ μΉκ°μ νμ μ΄λνλ©΄μ μλͺ¨ν μ°λ£ μμ λ λ°°κ° μΆ©μ
3) μ΄λνλ λμ€μ μ°λ£κ° λ°λ₯λλ©΄ μ΄λμ μ€ν¨νκ³ , κ·Έ λ μ μ λ¬΄κ° λλ¨
μΉκ°μ λͺ©μ μ§λ‘ μ΄λμν¨ λμμ μ°λ£κ° λ°λ₯λλ κ²½μ°λ μ€ν¨ν κ²μΌλ‘ κ°μ£Όνμ§ μμ
νμμ μΈ λͺ μ μΉκ°μ μΆλ°μ§μ λͺ©μ μ§κ° νμ
λͺ¨λ μΉκ°μ μ±κ³΅μ μΌλ‘ λ°λ €λ€μ€ μ μλμ§ μμλ΄κ³ , λ°λ €λ€μ€ μ μμ κ²½μ° μ΅μ’ μ μΌλ‘ λ¨λ μ°λ£μ μμ μΆλ ₯
μ΄λ λμ€μ μ°λ£κ° λ°λ₯λμ λ€μ μΆλ°μ§λ λͺ©μ μ§λ‘ μ΄λν μ μμΌλ©΄ -1μ μΆλ ₯
λͺ¨λ μλμ μ΄λμν¬ μ μλ κ²½μ°μλ -1μ μΆλ ₯
첫 μ€μ N, M, κ·Έλ¦¬κ³ μ΄κΈ° μ°λ£μ μ
(2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ μ΄κΈ° μ°λ£ ≤ 500,000) μ°λ£λ 무νν λ§μ΄ λ΄μ μ μκΈ° λλ¬Έμ, μ΄κΈ° μ°λ£μ μμ λμ΄μ μΆ©μ
λ€μ μ€λΆν° Nκ°μ μ€μ κ±Έμ³ λ°±μ€μ΄ νλν μμμ μ§λ
0μ λΉμΉΈ, 1μ λ²½
λ€μ μ€μλ λ°±μ€μ΄ μ΄μ μ μμνλ μΉΈμ ν λ²νΈμ μ΄ λ²νΈ
νκ³Ό μ΄ λ²νΈλ 1 μ΄μ N μ΄νμ μμ°μ, μ΄μ μ μμνλ μΉΈμ λΉμΉΈ
κ·Έλ€μ μ€λΆν° Mκ°μ μ€μ κ±Έμ³ κ° μΉκ°μ μΆλ°μ§μ νκ³Ό μ΄ λ²νΈ, λͺ©μ μ§μ νκ³Ό μ΄ λ²νΈ
λͺ¨λ μΆλ°μ§μ λͺ©μ μ§λ λΉμΉΈ, λͺ¨λ μΆλ°μ§λ μλ‘ λ€λ₯΄λ©°, κ° μλμ μΆλ°μ§μ λͺ©μ μ§λ λ€λ¦
import copy
from collections import deque
# N X N 격μν, Mλͺ
μ μΉκ°, μ΄κΈ° μ°λ£μ μ K
n, m, k = map(int, input().split())
graph = []
for i in range(n):
# Nκ°μ μ€μ κ±Έμ³ λ°±μ€μ΄ νλν μμμ μ§λ (0μ λΉμΉΈ, 1μ λ²½)
data = list(map(int, input().split()))
array = []
for d in data:
# λ²½μ΄ μλ λΆλΆμ -1, μ무κ²λ μλ λΆλΆμ -2
if d == 1:
array.append(-1)
else:
array.append(-2)
graph.append(array)
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
# λ°±μ€μ΄ μ΄μ μ μμνλ μΉΈμ ν λ²νΈμ μ΄ λ²νΈ
t_x, t_y = map(int, input().split())
# 1λΆν° μμνκΈ°μ μ½κ² μ°μ° νκΈ° μ°ν΄μ -1 λΉΌμ£Όμ!
t_x -= 1
t_y -= 1
# Mκ°μ μ€μ κ±Έμ³ κ° μΉκ°μ μΆλ°μ§μ νκ³Ό μ΄ λ²νΈ, λͺ©μ μ§μ νκ³Ό μ΄ λ²νΈ
customer = []
for _ in range(m):
# νμ κ³ κ°μ νμ¬ μμΉμ λͺ©μ μ§μ μμΉλ₯Ό μ μ₯
a, b, c, d = map(int, input().split())
customer.append([a, b, c, d])
# μλκ³Όμ 거리 κ³μ°
def customer_dist(graph, t_x, t_y):
g = copy.deepcopy(graph)
visited = [[False] * n for _ in range(n)]
queue = deque()
# νμ
queue.append((t_x, t_y))
# νμ μλ κ³³μ λΉμΉΈμ
g[t_x][t_y] = 0
visited[t_x][t_y] = True
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 > nx or n <= nx or 0 > ny or n <= ny:
continue
if g[nx][ny] == -1 or visited[nx][ny] == True:
continue
g[nx][ny] = g[x][y] + 1
visited[nx][ny] = True
queue.append((nx, ny))
# κ±°λ¦¬λ‘ κ°λμ°¬ graph!
return g
while True:
# μ°λ£ λΆμ‘±
if k < 0:
break
# μλ λ!
if len(customer) == 0:
break
move = []
gg = customer_dist(graph, t_x, t_y)
# νμ - μλ
for c in customer:
# νμ κ³ κ°μ νμ¬ μμΉμ λͺ©μ μ§μ μμΉλ₯Ό μ μ₯
a, b, c, d = c
dis = gg[a - 1][b - 1]
if dis < 0:
continue
move.append([dis, a - 1, b - 1, c - 1, d - 1])
if len(move) == 0:
# μ°λ£λ ν μΉΈ μ΄λν λλ§λ€ 1λ§νΌ μλͺ¨
k = -1
break
else:
# 거리 λ΄λ¦Όμ°¨μ - ν λ΄λ¦Όμ°¨μ - μ΄ λ΄λ¦Όμ°¨μ
move.sort(key=lambda x: (x[0], x[1], x[2]))
# κ³ κ° μμΉ κΉμ§ μ°λ£ λΆμ‘±νλ©΄ μ€λ¨
if move[0][0] > k:
k = -1
break
else:
# κ³ κ° μμΉμ 거리 λ§νΌ μ°λ£ μ°¨κ°
k -= move[0][0]
# νμμμΉ = κ³ κ°νμ¬ μμΉ, κ³ κ° λͺ©μ μ§ μμΉ
t_x, t_y, a, b = move[0][1:]
# λ§μ§λ§ λͺ©μ μ§κΉμ§μ νμ 거리 graph
end = customer_dist(graph, t_x, t_y)
# λͺ©μ μ§ κΉμ§μ 거리
d = end[a][b]
if d < 0:
#
k = -1
break
# 거리λ§νΌ μ°λ£ λΉΌκΈ°
k -= d
if k >= 0:
k += (d * 2)
customer.remove([t_x + 1, t_y + 1, a + 1, b + 1])
# μλμ λͺ©μ μ§κ° μ΄μ νμ μμΉ
t_x, t_y = a, b
else:
# μ°λ£λ ν μΉΈ μ΄λν λλ§λ€ 1λ§νΌ μλͺ¨
k = -1
break
print(k)
μμ μ λ ₯
6 3 15
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
μμ μΆλ ₯
14
728x90
λ°μν
'π¦₯ μ½ν > BAEKJOON' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BAEKJOON python] 16236_μκΈ°μμ΄ (0) | 2023.04.08 |
---|---|
[BAEKJOON python] 20055_μ»¨λ² μ΄μ΄ λ²¨νΈ μμ λ‘λ΄ (0) | 2023.04.08 |
[BAEKJOON python] 23290_λ§λ²μ¬ μμ΄μ 볡μ (0) | 2023.04.08 |
[BAEKJOON python] 21611_λ§λ²μ¬ μμ΄μ λΈλ¦¬μλ (0) | 2023.04.07 |
[BAEKJOON python] 21610_λ§λ²μ¬ μμ΄μ λΉλ°λΌκΈ° (0) | 2023.04.07 |
Comments