[BFS, 그래프] 프로그래머스 lv3. 블록이동하기

문제

문제링크

1. 로봇은 90도 회전하거나, 평행이동을 한다
2. 한 번 이동할 때 시간이 1씩 증가한다
3. n,n에 도착했을 때의 시간을 구해라

아이디어
q에서 꺼내서
if 끝 : 횟수 out
    이동
    조건 맞으면 q에 (좌표, 횟수) 넣기
    평행이동
    회전
          가로 => 세로
          세로 => 가로

알고리즘, 시간복잡도
BFS
시간 복잡도 O(V+E)?

자료구조
q = [[x1,y1,x2,y2], 횟수]
hist = [[x1,y1,x2,y2], [...], ...] # q에 들어갔던 좌표인지 확인,
x1 y1 x2 y2 => 왼오상하 순서로 넣고 뺀다

함수
move : 이동후 좌표 리스트 반환
bfs : 큐돌기

'''

회고

• 블록의 회전이 꽤나 까다로웠다.
• 블록 회전 부분을 for 반복문으로 하면 코드가 더 간결해질 거 같다.
• 회전 부분은 구현했었으나, 평행이동을 고려하지 않았었다 => 다른 분 꺼 참고한 부분
• 경로(좌표)를 담는 배열이나 SET 자료구조를 누락했었다! => 뒤늦게 추가, 하지만 좌표를 한번 묶어야 set에 넣을 수 있다. 다음엔 set로도 풀어보자
• set로 안 할 거면 중복 체크 때 좌표 섞여서 다른 요소로 인식하지 않도록 왼쪽 상단에 있는 좌표를 먼저 넣는 것을 주의할 것
• 좌표가 범위인지 체크 => 외벽을 1로 만들어서 시작해도 된다

from collections import deque

def solution(board):
    N = len(board)

    def check(arr):
        ax,ay,bx,by = arr
        if 0<=ax<N and 0<=ay<N and 0<=bx<N and 0<=by<N:
            if board[ax][ay]==0 and board[bx][by] == 0:
                return True


    def move(x1,y1,x2,y2):
        result = []
        # 평행이동
        for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx1, ny1 = x1+dx, y1+dy
            nx2, ny2 = x2+dx, y2+dy
            if check([nx1,ny1,nx2,ny2]):
                result.append([nx1,ny1,nx2,ny2])

        # 같은 행이면 세로로 이동
        if x1 == x2:
            # x1 위로, x2 위로
            if check([x1-1, y1, x2-1, y2]):
                nx1, ny1 = x1, y1
                nx2, ny2 = x1-1, y1
                result.append([nx2,ny2,nx1,ny1])

                nx1, ny1 = x2-1, y2
                nx2, ny2 = x2, y2
                result.append([nx1,ny1,nx2,ny2])

            # x1 아래로, x2 아래로
            if check([x1+1, y1, x2+1, y2]):
                nx1, ny1 = x1, y1
                nx2, ny2 = x1+1, y1
                result.append([nx1,ny1,nx2,ny2])

                nx1, ny1 = x2+1, y2
                nx2, ny2 = x2, y2
                result.append([nx2,ny2,nx1,ny1])

        # 같은 열이면 가로로 이동
        if y1 == y2:
            # y1 왼쪽으로, y2 왼쪽으로
            if check([x1, y1-1, x2, y2-1]):
                nx1, ny1 = x1, y1
                nx2, ny2 = x1, y1-1
                result.append([nx2,ny2,nx1,ny1])

                nx1, ny1 = x2, y2-1
                nx2, ny2 = x2, y2
                result.append([nx1,ny1,nx2,ny2])

            # y1 오른쪽으로, y2 오른쪽으로
            if check([x1, y1+1, x2, y2+1]):
                nx1, ny1 = x1, y1
                nx2, ny2 = x1, y1+1
                result.append([nx1,ny1,nx2,ny2])

                nx1, ny1 = x2, y2+1
                nx2, ny2 = x2, y2
                result.append([nx2,ny2,nx1,ny1])

        return result


    def bfs(ax, ay, bx, by):
        q = deque()
        hist = []
        answer = 0
        cnt = 0
        q.append([[ax,ay,bx,by], cnt])
        while q:
            xys, cnt = q.popleft()
            x1,y1,x2,y2 = map(int,xys)

            if (x1 == N-1 and y1 == N-1) or (x2 == N-1 and y2 == N-1):
                answer = cnt
                break

            for r in move(x1,y1,x2,y2):
                if r not in hist:
                    q.append([r, cnt+1])
                    hist.append(r)

        if answer !=0:
            return answer


    answer = bfs(0,0,0,1)
    return answer