[Python] 블록 이동하기 (DFS/BFS)

문제

프로그래머스

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

문제 풀이

• 편하게 탐색하기 위해 보드 밖 영역에 1을 삽입한 새로운 보드 만들기
• 현재 위치는 중복되지 않게 하기 위해 튜플로 관리
• 큐에 현재위치 튜플과 소요된 시간 넣고, 현재 위치 방문처리
• 큐를 팝했을 때 원하는 위치에 도달 했다면 현재까지 소요된 시간 반환
• 그 후 이동가능한 위치가 현재 방문되지 않았다면 소요된 시간 증가시키고, 큐에 삽입

코드

from collections import deque

def get_next_pos(pos,board):
    next_pos = [] # 이동 가능한 위치들
    pos = list(pos) # 현재 위치정보 리스트로 변환(집합 -> 리스트)
    pos1_y,pos1_x,pos2_y,pos2_x = pos[0][0], pos[0][1], pos[1][0], pos[1][1]

    # 상하좌우 이동
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    # 현재 놓여져 있는 상태에서 상하좌우 이동할 수 있는지 확인
    for i in range(4):
        pos1_next_y, pos2_next_y = pos1_y + dy[i], pos2_y + dy[i]
        pos1_next_x, pos2_next_x = pos1_x + dx[i], pos2_x + dx[i]

        # 이동하고자 하는 칸이 0인지 확인 (벽이없고, 좌표를 벗어나지 않았는지 확인)
        if board[pos1_next_y][pos1_next_x] == 0 and board[pos2_next_y][pos2_next_x] == 0:
            # 회전하지 않는경우의 이동좌표 삽입
            next_pos.append({(pos1_next_y, pos1_next_x), (pos2_next_y, pos2_next_x)})

    # 로봇이 가로로 놓여있는 경우, 세로로 회전할 수 있는지 탐색
    if pos1_y == pos2_y:
        for i in [-1, 1]: # 위나 아래로 회전
            if board[pos1_y + i][pos1_x] == 0 and board[pos2_y + i][pos2_x] == 0: # 위쪽 혹은 아래쪽 벽이 없다면
                # 왼쪽 칸 기준으로 위 아래 회전
                next_pos.append({(pos1_y, pos1_x), (pos1_y + i, pos1_x)})
                # 오른쪽 칸 기준으로 위 아래 회전
                next_pos.append({(pos2_y, pos2_x), (pos2_y + i, pos2_x)})

        # 로봇이 세로로 놓여있는 경우, 왼쪽 오른쪽으로 회전할 수 있는지 탐색
    elif pos1_x == pos2_x:
        for i in [-1, 1]:
            if board[pos1_y][pos1_x + i] == 0 and board[pos2_y][pos2_x + i] == 0:
                # 위 칸을 기준으로 왼쪽 오른쪽으로 회전
                next_pos.append({(pos1_y,pos1_x),(pos1_y, pos1_x + i)})
                # 아래 칸을 기준으로 왼쪽 오른쪽으로 회전
                next_pos.append({(pos2_y,pos2_x),(pos2_y, pos2_x + i)})

    return next_pos

def solution(board):
    # 그래프 밖에 1두른 new_board 만들기
    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 = deque()
    visited = []
    pos = {(1, 1), (1, 2)} # 시작위치 (튜플로 관리하면 중복발생 X)
    q.append((pos,0)) # 시작위치와 소요시간 삽입
    visited.append(pos) # 방문처리
    # 큐가 빌 때까지 반복
    while q:
        pos, sec = q.popleft()
        # 원하는 위치에 도달했다면 소요시간 반환
        if (n, n) in pos:
            return sec
        # 현재위치에서 이동 가능한 위치 확인
        for next_pos in get_next_pos(pos, new_board):
            # 아직 방문하지 않은 위치라면 큐에 삽입하고 방문처리
            if next_pos not in visited:
                q.append((next_pos, sec + 1))
                visited.append(next_pos)
    return 0