문제링크
문제설명
NN크기의 지도에서 21크기의 로봇을 움직인다. 지도는 빈칸 0과 벽 1로 이루어져있고, 로봇의 시작 위치는 (1,1),(1,2)임 이때 (N,N)까지 가는 최단거리는?
문제풀이
시도 1
로봇의 이동방향을 상하좌우와 1번축 기준 시계방향-반시계방향으로 회전, 2번축 기준 시계방향-반시계방향으로 회전, 총 8개로 나누었다.
from collections import deque
#상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = 0
def in_board(pos):
for p in pos:
if p not in range(0,N):
return False
return True
def get_next(robot, board):
[x_1, y_1], [x_2, y_2] = robot
next = []
for i in range(len(dx)):
if in_board([x_1+dx[i], y_1+dy[i], x_2+dx[i], y_2+dy[i]]) :
if board[x_1+dx[i]][y_1+dy[i]] != 1 and board[x_2+dx[i]][y_2+dy[i]] != 1:
next.append({(x_1+dx[i], y_1+dy[i]), (x_2+dx[i], y_2+dy[i])})
#1번축 기준으로 시계방향, 반시계방향 회전
if in_board([x_1+1, x_2+1, y_2-1]):
if board[x_1+1][y_1] != 1 and board[x_2+1][y_2] != 1:
next.append({(x_1, y_1),(x_2+1, y_2-1)})
if in_board([x_1-1, x_2-1, y_2-1]):
if board[x_1-1][y_1] != 1 and board[x_2-1][y_2] != 1:
next.append({(x_1, y_1),(x_2-1, y_2-1)})
#2번축 기준으로 시계방향, 반시계방향 회전
if in_board([x_1-1, y_1+1, x_2-1]):
if board[x_1-1][y_1] != 1 and board[x_2-1][y_2] != 1:
next.append({(x_1-1, y_1+1),(x_2, y_2)})
if in_board([x_1+1, y_1+1, x_2+1]):
if board[x_1+1][y_1] != 1 and board[x_2+1][y_2] != 1:
next.append({(x_1+1, y_1+1),(x_2, y_2)})
return next
def solution(board):
q = deque()
robot = {(0,0), (0,1)}
global N
N = len(board)
q.append((robot, 0))
visited = []
visited.append(robot)
while q:
pos, time = q.popleft()
print(pos, time)
if (N-1,N-1) in pos:
return time
else:
for next in get_next(pos, board):
if next not in visited:
visited.append(next)
q.append((next, time+1))
print(solution( [[0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 1, 0, 1, 1], [1, 1, 0, 0, 1], [0, 0, 0, 0, 0]]))
로봇이 세로로 놓여있을때랑 가로로 놓여있을때 이동방향이 달라짐을 고려하지 않았다 . ..
시도 2
축 기준이 아닌 로봇의 현재 방향을 기준으로 회전시켜야한다.
import sys
from collections import deque
input = sys.stdin.readline
#상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = None
def bfs(board):
q = deque()
visited = []
q.append(([(1,1), (1,2)], 0))
visited.append([(1,1), (1,2)])
while q:
robot, time = q.popleft()
[x_l, y_l], [x_r, y_r] = robot
#print(robot, time)
if (N, N) in robot:
return time
for i in range(4):
#상하좌우
#다음 이동할 좌표가 범위안에 있는지? 벽이 아닌지?
nx_l, ny_l, nx_r, ny_r = x_l+dx[i], y_l+dy[i], x_r+dx[i], y_r+dy[i]
if board[nx_l][ny_l] != 1 and board[nx_r][ny_r] != 1:
robot = [(nx_l, ny_l), (nx_r, ny_r)]
if robot not in visited:
q.append((robot, time+1))
visited.append(robot)
#블록이 가로로
if x_l == x_r:
if board[x_l+1][y_l] == 0 and board[x_r+1][y_r] == 0:
if [(x_l,y_l), (x_l+1, y_l)] not in visited:
robot = [(x_l,y_l), (x_l+1, y_l)]
visited.append(robot)
q.append((robot, time+1))
if [(x_r+1, y_r), (x_r,y_r)] not in visited:
robot = [(x_r+1, y_r), (x_r,y_r)]
visited.append(robot)
q.append((robot, time+1))
if board[x_l-1][y_l] == 0 and board[x_r-1][y_r] == 0:
if [(x_l,y_l), (x_l-1, y_l)] not in visited:
robot = [(x_l,y_l), (x_l-1, y_l)]
visited.append(robot)
q.append((robot, time+1))
if [(x_r-1, y_r), (x_r,y_r)] not in visited:
robot = [(x_r-1, y_r), (x_r,y_r)]
visited.append(robot)
q.append((robot, time+1))
#블록이 세로로
elif y_l == y_r:
if board[x_l][y_l+1] == 0 and board[x_r][y_r+1] == 0:
if {(x_l,y_l), (x_l,y_l+1)} not in visited:
robot = {(x_l,y_l), (x_l,y_l+1)}
visited.append(robot)
q.append((robot, time+1))
if {(x_r,y_r+1), (x_r,y_r)} not in visited:
robot = {(x_r,y_r+1), (x_r,y_r)}
visited.append(robot)
q.append((robot, time+1))
if board[x_l][y_l-1] == 0 and board[x_r][y_r-1] == 0:
if {(x_l,y_l), (x_l,y_l-1)} not in visited:
robot = {(x_l,y_l), (x_l,y_l-1)}
visited.append(robot)
q.append((robot, time+1))
if {(x_r,y_r-1), (x_r,y_r)} not in visited:
robot = {(x_r,y_r-1), (x_r,y_r)}
visited.append(robot)
q.append((robot, time+1))
def solution(board):
global N
N = len(board)
new_board = [[1]*(N+2) for _ in range(N+2)]
for i in range(N):
for j in range(N):
new_board[i+1][j+1] = board[i][j]
time = bfs(new_board)
return time아오 근데
개짱나 ,, , ,, ,,
시도 3
from collections import deque
#상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = 0
def get_next(robot, board):
[x_l, y_l], [x_r, y_r] = robot
next = []
for i in range(len(dx)):
if board[x_l+dx[i]][y_l+dy[i]] != 1 and board[x_r+dx[i]][y_r+dy[i]] != 1:
next.append({(x_l+dx[i], y_l+dy[i]), (x_r+dx[i], y_r+dy[i])})
#블록이 가로로
if x_l == x_r:
if board[x_l+1][y_l] == 0 and board[x_r+1][y_r] == 0:
next.append({(x_l,y_l), (x_l+1, y_l)})
next.append({(x_r+1, y_r), (x_r,y_r)})
if board[x_l-1][y_l] == 0 and board[x_r-1][y_r] == 0:
next.append({(x_l,y_l), (x_l-1, y_l)})
next.append({(x_r-1, y_r), (x_r,y_r)})
#블록이 세로로
elif y_l == y_r:
if board[x_l][y_l+1] == 0 and board[x_r][y_r+1] == 0:
next.append({(x_l,y_l), (x_l,y_l+1)})
next.append({(x_r,y_r+1), (x_r,y_r)})
if board[x_l][y_l-1] == 0 and board[x_r][y_r-1] == 0:
next.append({(x_l,y_l), (x_l,y_l-1)})
next.append({(x_r,y_r-1), (x_r,y_r)})
return next
def solution(board):
q = deque()
robot = {(1,1), (1,2)}
global N
N = len(board)
new_board = [[1]*(N+2) for _ in range(N+2)]
for i in range(N):
for j in range(N):
new_board[i+1][j+1] = board[i][j]
q.append((robot, 0))
visited = []
visited.append(robot)
while q:
pos, time = q.popleft()
#print(pos, time)
if (N,N) in pos:
return time
else:
for next in get_next(pos, new_board):
if next not in visited:
visited.append(next)
q.append((next, time+1))- (0,0),(0,1)이 아닌 원래 보드 주위로 1인 벽을 둘러서 따로 in_board()와 같은 함수호출 없이 가능하도록
- 매 좌표에 대한 검사 대신 이동가능한 모든 좌표를 get_next()를 이용해 리스트에 담고, 그 리스트에 대해 방문한적이 있는지를 검사했다
사실 코드는 간단해지긴 했지만 로직은 비슷한데 뭐가 글케 다른지 모르겠음, ,,
Hongik CE