카카오 2020 Blind 블록 이동하기 파이썬

BFS + 시뮬레이션 문제

현재 상태가 가로/ 세로인지, 위/오/아/왼으로 움직일건지로 구분했다.

잘 찾아보면 dir xy로 돌릴 수 있는 규칙을 찾을 수 있을 것 같은데 개인적으로 이렇게 복잡할 땐 오히려 하나씩 생각하면서 구현해가며 푸는 게 시간이 덜 걸리는것 같다
같은 칸에 대해서도 가로, 세로의 경우가 있을 수 있으므로 기준을 잘 잡는게 중요하다.

visit 배열을 visit[101][101][2]로 잡았는데, 마지막 2칸은 세로 / 가로의 경우를 나눈 것이다.

가로일 때는 왼쪽칸, 세로일 때는 위쪽칸을 기준으로 잡았다.

기준을 왼쪽, 위로 잡아 구현했다는 것을 명심하고 칸 수 계산을 잘 해야 한다.

예를 들어 가로로 놓여진 로봇의 현재 (x,y) 에서 오른쪽으로 옮기고 싶으면 board[x][y+2]를 체크해야 하는데,

로봇은 전체적으로 한 칸을 움직이더라도 차지하는 칸이 현재 기준 x에서 두 칸 오른쪽까지이기 때문이다.

대신 현재 로봇의 위치는 그 전에 검증을 끝내고 옮긴 상태이니 board[x][y+1]는 그 전에 검증을 끝냈으므로 체크할 필요가 없다.

시험 당시에도 똑같이 x+2 대신 x+1로 풀어서 시간을 잡아먹었던 것 같은데 똑같이 헤매고 해결한 뒤에야 생각이났다.

같은 실수를 바보같이 맨날 반복하는데 이제 알고리즘 풀이를 좀 정리해서 복습해야겠다 ㅠㅠ 오히려 그 때 보다 더 오래 걸린 것 같다

실제 시험시간에는 c++로 풀었었는데 문자열도 아니고 빡구현이라 파이썬과 큰 차이는 없는 것 같다.

가장 큰 차이는 선언할 때 컨테이너의 자료형 선언이 필요 없다는 것과, 다중 배열을 선언하는 방식인 것 같다.

오히려 c++ 에서는 전역변수로 visit[101][101][2] 하면 크기 지정, 초기화까지 끝인데 파이썬에서는 직접 해줘야 한다

 

from collections import deque
dxy=[[1,0],[0,1]]
visit = [[[0,0] for i in range(101)] for i in range(101)]
def solution(board):    
    N = len(board)
    answer = 0
    q = deque()
    visit[0][0][1] = 1
    q.append((0,0,1,0)) # x, y, dir, cnt
    while q:
        x, y, d, cnt = q.popleft()
        #print(x,y,d,cnt)
        if x+dxy[d][0] == N-1 and y + dxy[d][1] == N-1: #종료 조건
            return cnt

        if d == 1:
            if y-1 >= 0:
                if board[x][y-1] == 0 and visit[x][y-1][1] == 0:
                    visit[x][y-1][1] = 1
                    q.append((x,y-1, 1, cnt+1))
            if x+1 < N:
                if board[x+1][y]==0 and board[x+1][y+1]==0 :
                    if visit[x+1][y][1] == 0:
                        visit[x+1][y][1]= 1
                        q.append((x+1, y, 1, cnt+1))
                    if visit[x][y+1][0] == 0:
                        visit[x][y+1][0] = 1
                        q.append((x, y+1, 0, cnt+1))
                    if visit[x][y][0] == 0:
                        visit[x][y][0] = 1
                        q.append((x,y,0, cnt+1))
            if y+2 < N:
                if board[x][y+2] == 0 and visit[x][y+1][1] == 0:
                    visit[x][y+1][1] = 1
                    q.append((x,y+1, 1, cnt+1))
            if x-1 >= 0:
                if board[x-1][y] == 0 and board[x-1][y+1] == 0:
                    if visit[x-1][y][1] == 0:
                        visit[x-1][y][1]= 1
                        q.append((x-1, y, 1, cnt+1))
                    if visit[x-1][y+1][0] == 0:
                        visit[x-1][y+1][0] = 1
                        q.append((x-1, y+1, 0, cnt+1))
                    if visit[x-1][y][0] == 0:
                        visit[x-1][y][0] =1
                        q.append((x-1, y, 0, cnt+1))
        elif d == 0:
            if x-1 >= 0:
                if board[x-1][y] == 0 and visit[x-1][y][0] == 0:
                    visit[x-1][y][0] = 1
                    q.append((x-1,y, 0, cnt+1))
            if y+1 < N:
                if board[x][y+1]==0 and board[x+1][y+1]==0 :
                    if visit[x][y+1][0] == 0:
                        visit[x][y+1][0]= 1
                        q.append((x, y+1, 0, cnt+1))
                    if visit[x+1][y][1] == 0:
                        visit[x+1][y][1] = 1
                        q.append((x+1, y, 1, cnt+1))
                    if visit[x][y][1] == 0:
                        visit[x][y][1] = 1
                        q.append((x,y,1, cnt+1))

            if x+2 < N:
                if board[x+2][y] == 0 and visit[x+1][y][0] == 0:
                    visit[x+1][y][0] = 1
                    q.append((x+1,y, 0, cnt+1))
            if y-1 >= 0:
                if board[x][y-1] == 0 and board[x+1][y-1] == 0:
                    if visit[x][y-1][0] == 0:
                        visit[x][y-1][0]= 1
                        q.append((x, y-1, 0, cnt+1))
                    if visit[x+1][y-1][1] == 0:
                        visit[x+1][y-1][1] = 1
                        q.append((x+1, y-1, 1, cnt+1))
                    if visit[x][y-1][1] == 0:
                        visit[x][y-1][1] =1
                        q.append((x, y-1, 1, cnt+1))
    return answer