728x90
😉 아이디어
1. 2개의 수레에 대한 좌표 탐색 중첩 👉 이중 탐색 _!DFS or BFS!_
2. 2개의 수레를 이동하는 중 _!수레의 위치가 서로 뒤바뀌는 경우!_와 _!두 개의 수레 도착 지점이 동일한 경우!_를 제외해야한다.
3. _!수레의 위치가 서로 뒤바뀌는 경우!_의 조건문 체크에 오류가 있었다.
- 기존 : _!(n_bx, n_by) != red_start and (n_rx, n_ry) != blue_start!_
- 수정 : _!not ((n_bx, n_by) == red_start and (n_rx, n_ry) == blue_start)!_
- 두 개의 좌표 중 하나라도 원점 좌표와 일치하지 않으면, _!참!_이 되어야 하지만(스위칭이 아니므로) 기존 조건식은 _!거짓!_ 처리 중이었다.
😉 풀이
from collections import deque
import copy
def solution(maze):
positions = get_positions(maze)
answer = bfs(maze, positions)
return answer
def get_positions(maze):
rows = len(maze)
cols = len(maze[0])
red_start = (0, 0)
blue_start = (0, 0)
red_end = (0, 0)
blue_end = (0, 0)
for x in range(rows):
for y in range(cols):
value = maze[x][y]
if value == 1:
red_start = (x, y)
elif value == 2:
blue_start = (x, y)
elif value == 3:
red_end = (x, y)
elif value == 4:
blue_end = (x, y)
return red_start, blue_start, red_end, blue_end
def bfs(maze, positions):
dq = deque([])
rows = len(maze)
cols = len(maze[0])
dx = (1, -1, 0, 0)
dy = (0, 0, 1, -1)
red_start, blue_start, red_end, blue_end = positions
red_visited = [[False] * cols for _ in range(rows)]
blue_visited = [[False] * cols for _ in range(rows)]
red_visited[red_start[0]][red_start[1]] = True
blue_visited[blue_start[0]][blue_start[1]] = True
result_count = float('inf')
dq.append((red_start, blue_start, red_visited, blue_visited, 0))
while dq:
red_start, blue_start, red_visited, blue_visited, count = dq.popleft()
if red_start == red_end and blue_start == blue_end:
result_count = min(result_count, count)
continue
if red_start == red_end: # 레드 수레
n_rx, n_ry = red_start
for j in range(4):
n_bx, n_by = blue_start[0] + dx[j], blue_start[1] + dy[j]
if (0 <= n_bx < rows
and 0 <= n_by < cols
and maze[n_bx][n_by] != 5
and not blue_visited[n_bx][n_by]
and not ((n_bx, n_by) == red_start and (n_rx, n_ry) == blue_start)
and (n_rx, n_ry) != (n_bx, n_by)): # 동일한 좌표로 수레 이동 제한
new_blue_visited = copy.deepcopy(blue_visited)
new_blue_visited[n_bx][n_by] = True
new_blue_start = (n_bx, n_by)
dq.append((red_start, new_blue_start, red_visited, new_blue_visited, count + 1))
elif blue_start == blue_end: # 블루 수레 골인
n_bx, n_by = blue_start
for j in range(4):
n_rx, n_ry = red_start[0] + dx[j], red_start[1] + dy[j]
if (0 <= n_rx < rows
and 0 <= n_ry < cols
and maze[n_rx][n_ry] != 5
and not red_visited[n_rx][n_ry]
and not ((n_bx, n_by) == red_start and (n_rx, n_ry) == blue_start)
and (n_rx, n_ry) != (n_bx, n_by)): # 동일한 좌표로 수레 이동 제한
new_red_visited = copy.deepcopy(red_visited)
new_red_visited[n_rx][n_ry] = True
new_red_start = (n_rx, n_ry)
dq.append((new_red_start, blue_start, new_red_visited, blue_visited, count + 1))
else: # 골인 x
for i in range(4):
n_rx, n_ry = red_start[0] + dx[i], red_start[1] + dy[i]
if (0 <= n_rx < rows
and 0 <= n_ry < cols
and maze[n_rx][n_ry] != 5
and not red_visited[n_rx][n_ry]
):
for j in range(4):
n_bx, n_by = blue_start[0] + dx[j], blue_start[1] + dy[j]
if (0 <= n_bx < rows
and 0 <= n_by < cols
and maze[n_bx][n_by] != 5
and not blue_visited[n_bx][n_by]
and not ((n_bx, n_by) == red_start and (n_rx, n_ry) == blue_start)
and (n_rx, n_ry) != (n_bx, n_by)): # 동일한 좌표로 수레 이동 제한
new_red_visited = copy.deepcopy(red_visited)
new_blue_visited = copy.deepcopy(blue_visited)
new_red_visited[n_rx][n_ry] = True
new_blue_visited[n_bx][n_by] = True
new_red_start = (n_rx, n_ry)
new_blue_start = (n_bx, n_by)
dq.append((new_red_start, new_blue_start, new_red_visited, new_blue_visited, count + 1))
if result_count == float('inf'):
result_count = 0
return result_count✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/250134
