[programmers] DFS/BFS - 블록이동

문제링크

코딩테스트 연습 - 블록 이동하기

문제설명

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()를 이용해 리스트에 담고, 그 리스트에 대해 방문한적이 있는지를 검사했다

사실 코드는 간단해지긴 했지만 로직은 비슷한데 뭐가 글케 다른지 모르겠음, ,,