4번 / 수레 움직이기
https://school.programmers.co.kr/learn/courses/30/lessons/250134
문제 설명
n x m 크기 격자 모양의 퍼즐판이 주어집니다.
퍼즐판에는 빨간색 수레와 파란색 수레가 하나씩 존재합니다. 각 수레들은 자신의 시작 칸에서부터 자신의 도착 칸까지 이동해야 합니다.
모든 수레들을 각자의 도착 칸으로 이동시키면 퍼즐을 풀 수 있습니다.
당신은 각 턴마다 반드시 모든 수레를 상하좌우로 인접한 칸 중 한 칸으로 움직여야 합니다. 단, 수레를 움직일 때는 아래와 같은 규칙이 있습니다.
규칙
1. 수레는 벽이나 격자 판 밖으로 움직일 수 없습니다.
2. 수레는 자신이 방문했던 칸으로 움직일 수 없습니다.
3. 자신의 도착 칸에 위치한 수레는 움직이지 않습니다. 계속 해당 칸에 고정해 놓아야 합니다.
4. 동시에 두 수레를 같은 칸으로 움직일 수 없습니다.
5. 수레끼리 자리를 바꾸며 움직일 수 없습니다.
풀이
- 우선 각 수레의 시작 지점을 구합니다.
for i in range(N):
for j in range(M):
if maze[i][j] == 1:
red = [i, j]
if maze[i][j] == 2:
blue = [i, j]- 각 조건에 맞는 path를 추가하기 위해 변수들을 선언
visit_r = 빨간색 수레가 방문한 지점
visit_b = 파란색 수레가 방문한 지점
r_flag = 빨간색 수레가 도착지점에 있는가?
b_flag = 파란색 수레가 도착지점에 있는가?- 조건 확인
빨간색 수레가 도착했다면 파란색 수레만 이동합니다.
이때, 파란색 수레는 조건 1, 2, 4를 만족해야 합니다.
파란색 수레가 도착했다면 빨간색 수레만 이동합니다.
이때, 빨간색 수레는 조건 1, 2, 4를 만족해야 합니다.
만약, 두 수레가 동시에 이동한다면 두 수레의 위치가 교차되지 않는지 확인해야합니다.
from collections import deque
import copy
def solution(maze):
answer = 0
# 0=빈칸, 1=빨간, 2=파란, 3=빨간 도착, 4=파란 도착 5=벽
# BFS
N = len(maze)
M = len(maze[0])
for i in range(N):
for j in range(M):
if maze[i][j] == 1:
red = [i, j]
if maze[i][j] == 2:
blue = [i, j]
dx = [ -1, 1, 0, 0]
dy = [0, 0, -1, 1]
visit_r = [[False]*M for _ in range(N)]
visit_b = [[False]*M for _ in range(N)]
r_flag = False
b_flag = False
path = deque()
path.append(red+blue+[visit_r]+[visit_b]+[0])
while path:
rx, ry, bx, by, vr, vb, cnt = path.popleft()
v_r = copy.deepcopy(vr)
v_b = copy.deepcopy(vb)
v_r[rx][ry] = True
v_b[bx][by] = True
# red, blue 도착
if maze[rx][ry] == 3 and maze[bx][by] == 4:
return cnt
break
elif maze[rx][ry] == 3:
r_flag = True
b_flag = False
elif maze[bx][by] == 4:
b_flag = True
r_flag = False
else:
r_flag = False
b_flag = False
for i in range(4):
if b_flag:
rnx, rny = rx + dx[i], ry + dy[i]
if 0 <= rnx < N and 0 <= rny < M:
# 겹치치 않고, 벽이 아니고, 방문한 적이 없으면
if not (rnx, rny) == (bx, by) and not maze[rnx][rny] == 5 and not v_r[rnx][rny]:
path.append([rnx, rny, bx, by, v_r, v_b, cnt+1])
elif r_flag:
bnx, bny = bx + dx[i], by + dy[i]
if 0 <= bnx < N and 0 <= bny < M:
if not (bnx, bny) == (rx, ry) and not maze[bnx][bny] == 5 and not v_b[bnx][bny]:
path.append([rx, ry, bnx, bny, v_r, v_b, cnt+1])
else :
rnx, rny = rx + dx[i], ry + dy[i]
if 0 <= rnx < N and 0 <= rny < M:
if not maze[rnx][rny] == 5 and not v_r[rnx][rny]:
for j in range(4):
bnx, bny = bx + dx[j], by + dy[j]
if 0 <= bnx < N and 0 <= bny < M:
# 벽이 아니고 방문한 적 없고, 겹치지 않고, 교차되지 않는다면
if not maze[bnx][bny] == 5 and not v_b[bnx][bny] and not (rnx, rny) == (bnx, bny) and not (rx == bnx and ry == bny and bx == rnx and by == rny):
path.append([rnx, rny, bnx, bny, v_r, v_b, cnt+1])
return 0후기
BFS를 통해 두 개의 수레를 이동시켜야 한다는 점에서 당황했으나, 조건을 잘 분류해서 문제를 해결할 수 있었던 것 같다.
