[프로그래머스] 블록 이동하기 (파이썬)

dongEon·2023년 4월 6일
0

난이도 : LV 3

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60063#

문제해결 아이디어

  • 다른사람의 문제풀이를 참고해서 풀었다.
  • 최단경로 문제라서 BFS를 사용했다.
  • 탐색을하면서 canMove 함수를 사용하여 회전, 이동이 가능한 경우를 리턴
  • canMove 함수에서 리턴 받은 경우들중 confirm(세트)를 통해 기존에 방문했는 지 확인한다.
  • 방문하지 않은경우 confirm에 로봇의 좌표(두개)를 넣어주고, cnt+1을 하고 큐에 다시 넣어준다.
    로봇중 한 부위라도 도착점에 도착하면 cnt를 리턴

소스코드

from collections import deque

dx,dy = [-1,1,0,0],[0,0,-1,1]

def canMove(board,cur1,cur2):
    # 직선이동
    arr = [] # 이동가능한 좌표 모음
    
    for i in range(4):
        nx1 = cur1[0] + dx[i]
        ny1 = cur1[1] + dy[i]
        nx2 = cur2[0] + dx[i]
        ny2 = cur2[1] + dy[i]
        
        if board[nx1][ny1] == 0 and board[nx2][ny2] == 0:
            arr.append(((nx1,ny1), (nx2,ny2)))
    
    # 회전이동
    # 세로로 있는지 가로로 있는지 확인
    if cur1[0] == cur2[0]: # 가로방향
        up = -1
        down = 1        
        for d in [up,down]:
            if board[cur1[0]+d][cur1[1]] == 0 and board[cur2[0]+d][cur2[1]] ==0:
                arr.append((cur1, (cur1[0]+d, cur1[1])))
                arr.append((cur2, (cur2[0]+d, cur2[1])))
    else: # 세로방향 일때
        left = -1
        right = 1
        
        for d in [left,right]:
            if board[cur1[0]][cur1[1]+d] == 0 and board[cur2[0]][cur2[1]+d] == 0:
                arr.append(((cur1[0], cur1[1]+d), cur1))
                arr.append(((cur2[0], cur2[1]+d), cur2))
                
    return arr
    

def solution(board):
    # 두개의 좌표로 visited 여부를 체크할때는 그냥 set안에서 존재하는 지 여부로 하자    
    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()
    q.append(((1,1),(1,2),0))
    confirm = set([((1,1),(1,2))])        
    
    while q:
        cur1,cur2,cnt = q.popleft()
        if cur1 == (n,n) or cur2 == (n,n):
            return cnt
        
        for next in canMove(new_board, cur1, cur2):
            if next not in confirm:
                q.append((next[0],next[1],cnt+1))
                confirm.add(next)
profile
개발 중에 마주한 문제와 해결 과정, 새롭게 배운 지식, 그리고 알고리즘 문제 해결에 대한 다양한 인사이트를 공유하는 기술 블로그입니다

0개의 댓글