π β Q. λ¬Έμ μ€λͺ
λ‘λ΄ μ²μκΈ°κ° μ£Όμ΄μ‘μ λ, μ²μνλ μμμ κ°μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
λ‘λ΄ μ²μκΈ°κ° μλ μ₯μλ NΓM ν¬κΈ°μ μ§μ¬κ°νμΌλ‘ λνλΌ μ μμΌλ©°, 1Γ1ν¬κΈ°μ μ μ¬κ°ν μΉΈμΌλ‘ λλμ΄μ Έ μλ€. κ°κ°μ μΉΈμ λ²½ λλ λΉ μΉΈμ΄λ€. μ²μκΈ°λ λ°λΌλ³΄λ λ°©ν₯μ΄ μμΌλ©°, μ΄ λ°©ν₯μ λ, μ, λ¨, λΆμ€ νλμ΄λ€. μ§λμ κ° μΉΈμ (r, c)λ‘ λνλΌ μ μκ³ , rμ λΆμͺ½μΌλ‘λΆν° λ¨μ΄μ§ μΉΈμ κ°μ, cλ μμͺ½μΌλ‘ λΆν° λ¨μ΄μ§ μΉΈμ κ°μμ΄λ€.λ‘λ΄ μ²μκΈ°λ λ€μκ³Ό κ°μ΄ μλνλ€.
- νμ¬ μμΉλ₯Ό μ²μνλ€.
- νμ¬ μμΉμμ νμ¬ λ°©ν₯μ κΈ°μ€μΌλ‘ μΌμͺ½λ°©ν₯λΆν° μ°¨λ‘λλ‘ νμμ μ§ννλ€.
a. μΌμͺ½ λ°©ν₯μ μμ§ μ²μνμ§ μμ 곡κ°μ΄ μ‘΄μ¬νλ€λ©΄, κ·Έ λ°©ν₯μΌλ‘ νμ ν λ€μ ν μΉΈμ μ μ§νκ³ 1λ²λΆν° μ§ννλ€.
b. μΌμͺ½ λ°©ν₯μ μ²μν 곡κ°μ΄ μλ€λ©΄, κ·Έ λ°©ν₯μΌλ‘ νμ νκ³ 2λ²μΌλ‘ λμκ°λ€.
c. λ€ λ°©ν₯ λͺ¨λ μ²μκ° μ΄λ―Έ λμ΄μκ±°λ λ²½μΈ κ²½μ°μλ, λ°λΌλ³΄λ λ°©ν₯μ μ μ§ν μ±λ‘ ν μΉΈ νμ§μ νκ³ 2λ²μΌλ‘ λμκ°λ€.
d. λ€ λ°©ν₯ λͺ¨λ μ²μκ° μ΄λ―Έ λμ΄μκ±°λ λ²½μ΄λ©΄μ, λ€μͺ½ λ°©ν₯μ΄ λ²½μ΄λΌ νμ§λ ν μ μλ κ²½μ°μλ μλμ λ©μΆλ€.
λ‘λ΄ μ²μκΈ°λ μ΄λ―Έ μ²μλμ΄μλ μΉΈμ λ μ²μνμ§ μμΌλ©°, λ²½μ ν΅κ³Όν μ μλ€.μ λ ₯ 쑰건
λ‘λ΄ μ²μκΈ°κ° μλ μΉΈμ μ’ν (r, c)μ λ°λΌλ³΄λ λ°©ν₯ dκ° μ£Όμ΄μ§λ€. μ΄ λ dκ° 0μΈ κ²½μ°μλ λΆμͺ½μ, 1μΈ κ²½μ°μλ λμͺ½μ, 2μΈ κ²½μ°μλ λ¨μͺ½μ, 3μΈ κ²½μ°μλ μμͺ½μ λ°λΌλ³΄κ³ μλ κ²μ΄λ€.λν μ²μνκ³ μ νλ λ°©μ μ§λλ₯Ό 2μ°¨μ λ°°μ΄λ‘ μ£Όμ΄μ§λ€.
λΉ μΉΈμ 0, λ²½μ 1λ‘ μ£Όμ΄μ§λ€. μ§λμ 첫 ν, λ§μ§λ§ ν, 첫 μ΄, λ§μ§λ§ μ΄μ μλ λͺ¨λ μΉΈμ λ²½μ΄λ€.λ‘λ΄ μ²μκΈ°κ° μλ μΉΈμ μνλ νμ λΉ μΉΈμ΄λΌκ³ νμ λ,
λ‘λ΄ μ²μκΈ°κ° μ²μνλ μΉΈμ κ°μλ₯Ό λ°ννμμ€.
r, c, d = 7, 4, 0
room_map = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
π‘ 2μ°¨μ λ°°μ΄μ μ’ μ½νλ° μ΄ λ¬Έμ λ₯Ό νλ©° μ’ κ°ν΄μ§ κ² κ°λ€ μ§μ§ κ±°μ λ€ μ κ·Όνμλλ° for λ¬Έ μμ νμ μν΄μ£Όκ³ 2μ€ for λ¬Έμ μ΄κ±Έ λμΉ λͺ»μ±κ³ μκΎΈ μ΄μνκ² λμ μκ°μ λ무 λ§μ΄ νλΉν΄μ λ
무 λ΅λ΅νλ€ γ
λ λ°©ν₯μ μ‘μμ£Όλ ν¨μμ μ’ν(r, c) μ (d) κΉμ§ λ£μ΄μ£Όλ €κ³ νμ§λ§ νμ΄λ μ’ λ κΉλν λ°©μμΌλ‘ μ κ·Όνμ¬ κ·Έ λ°©μμΌλ‘ μ κ·Όνμλ€.
λ€μλΆν°λ μ’ λ κΌΌκΌΌν μ΄ν΄λ³΄μ... γ
π‘ νμ΄
current_r, current_c, current_d = 7, 4, 0
current_room_map = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
def get_position(d):
return (d + 3) % 4
def get_back(d):
return (d + 2) % 4
# λΆ 0 -> 3 | back -> 2
# λ 1 -> 0 | back -> 3
# λ¨ 2 -> 1 | back -> 0
# μ 3 -> 2 | back -> 1
def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
# total_r, total_c = len(room_map), len(room_map[0])
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
n = len(room_map)
m = len(room_map[0])
clear = 1
room_map[r][c] = 2
queue = [[r, c, d]]
while queue:
r, c, d = queue.pop()
temp = d
for i in range(4):
temp = get_position(temp)
nx_r, nx_c = r + dr[temp], c + dc[temp]
if 0 <= nx_r < n and 0 <= nx_c < m and room_map[nx_r][nx_c] == 0:
clear += 1
room_map[nx_r][nx_c] = 2
queue.append([nx_r, nx_c, temp])
break
elif i == 3:
nx_r, nx_c = r + dr[get_back(d)], c + dc[get_back(d)]
queue.append([nx_r, nx_c, d])
if room_map[nx_r][nx_c] == 1:
return clear
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))
current_room_map2 = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("μ λ΅ = 29 / νμ¬ νμ΄ κ° = ", get_count_of_departments_cleaned_by_robot_vacuum(6,3,1,current_room_map2))
current_room_map3 = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("μ λ΅ = 33 / νμ¬ νμ΄ κ° = ", get_count_of_departments_cleaned_by_robot_vacuum(7,4,1,current_room_map3))
current_room_map4 = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("μ λ΅ = 25 / νμ¬ νμ΄ κ° = ", get_count_of_departments_cleaned_by_robot_vacuum(6,2,0,current_room_map4))
π μ€λμ λ¬Έμ νλλ§ μ¬λ¦¬λ € νλ€. λ°λ‘ λ§ν¬κ° μλ λ¬Έμ κ° μλ κ°μ μλ£μμ κ°μ Έμ¨ λ¬Έμ λΌ μ¬λ¬ λ¬Έμ λ₯Ό μμ±νλ©΄ TILμ΄ λ무 κΈΈμ΄μ Έ νΌκ³€νλ€... μμ§ λ무 λ§μ΄ λΆμ‘±νλ€. λ¬Έμ κ° μν릴λλ μ’ λ΅λ΅ν¨μ΄ λ§μ΄ μ°Ύμμ€μ§λ§ κ·Έλλ ν΄κ²°νλλ° μ§λ¦Ών λ§μ΄ μμΌλκΉ γ γ 2μ°¨μ λ°°μ΄ κ΅΄λ¦¬λλ° μ’ λ μ΅μν΄μ Έμ μλλ₯Ό μ¬λ €μΌκ² λ€.
μ€λ λ!