2020 KAKAO BLIND RECRUITMENT - 블록 이동하기

대망의 2020 마지막 문제 블록 이동하기 입니다.

 

다음 주 중에 2021 KAKAO 리쿠르팅이 열리는 시점에서 문제를 다 풀었다는 점이 뜻 깊네요.

 

2021 KAKAO 리쿠르팅 지원하시는 분들 홧팅입니다.

 

https://programmers.co.kr/learn/courses/30/lessons/60063

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

---

이 문제는 사실 이론적 내용이 어렵지 않습니다.

 

코딩 테스트를 준비하신 분이라면 전부 아시는 BFS를 이용하는 문제니까요.

 

근데 이걸 막상 구현하려고 하면 좀 멈칫 멈칫 한다는게 문제인데, 실제 시험 중엔 그럴 수 없으니 문제를 풀기 전 개념을 똑바로 잡고 가도록 합시다.

 

문제 해결을 위해 필요한 것들

 

1) 로봇은 항상 두 칸을 차지한다.

 

2) 로봇은 벽을 지나갈 수 없고, 트랙 밖으로 이탈할 수 없다.

 

3) 1,1 => N, N으로 이동시킨다. 로봇의 어느 부분이 도착해도 상관없다.

 

4) 로봇을 90도 회전할 때, 로봇이 어느 부분이든 축이 될 수 있지만, 회전하는 방향에는 벽이 없어야한다.

 

여기까지 하시면 쉽게 문제를 해결할 수 있습니다.

 

시험 당시엔 왤케 무서워했는지 모르겠네요.

 

본 문제를 해결하기 위해서 제가 설계한 함수와 파라미터는 아래와 같습니다.

함수

1) solution => 문제 input을 받는 함수

 

2) bfs => bfs를 수행하는 함수

 

3) move_check => 이동이 가능한지 체크하는 함수

 

4) rot_check => 회전이 가능한지 체크하는 함수

파라미터

ㄱ) visited => 방문 처리를 위한 전역 리스트

 

ㄴ) dq => BFS를 위한 deque 자료구조

 

ㄷ) dxdy => 4방향 탐색을 위함

 

이거만 하면 끝이에여

 

제일 중요시 해야하는 함수가 4) 함수가 되겠습니다.

 

왜냐 로봇이 ㅡ 모양으로 있는 것과 ㅣ 모양으로 있는 것은 회전할 때, 조건을 따로 탐색해야하기 때문에 은근 헷갈리거든요.

 

그렇기 때문에 그냥 회전하려는 방향을 싸잡아서 한꺼번에 벽이 있나 없나를 체크하시는것이 좀 더 편하실거에요.

 

from collections import deque


visited = []
dq = deque()
dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def move_check(board, next):
    y1 = next[0]; x1 = next[1]
    y2 = next[2]; x2 = next[3]
    n = len(board)
    return True if 0 <= x1 < n and 0 <= y1 < n and 0 <= x2 < n and 0 <= y2 < n and board[y1][x1] == 0 and board[y2][x2] == 0 else False
    

def list_to_str(li):
    return ''.join(map(str, li))


def rot_check(board, next):
    n = len(board)
    y1 = next[0]; x1 = next[1]
    y2 = next[2]; x2 = next[3]
    
    if next[4] == 1:
        if 0 <= y1 + 1 < n and board[y1 + 1][x1] == 0 and board[y1 + 1][x2] == 0:
            if not {(y1 ,x1), (y1 + 1, x1)} in visited:
                dq.append([y1, x1, y1 + 1, x1, 2, next[5] + 1])
                visited.append({(y1 ,x1), (y1 + 1, x1)})
            if not {(y2 + 1, x2), (y2, x2)} in visited:
                dq.append([y2 + 1, x2, y2, x2, 2, next[5] + 1])
                visited.append({(y2 + 1, x2), (y2, x2)})
        if 0 <= y1 - 1 < n and board[y1 - 1][x1] == 0 and board[y1 - 1][x2] == 0:
            if not {(y1 ,x1), (y1 - 1, x1)} in visited:
                dq.append([y1, x1, y1 - 1, x1, 2, next[5] + 1])
                visited.append({(y1 ,x1), (y1 - 1, x1)})
            if not {(y2 - 1, x2), (y2, x2)} in visited:
                dq.append([y2 - 1, x2, y2, x2, 2, next[5] + 1])
                visited.append({(y2 - 1, x2), (y2, x2)})
    else:
        if 0 <= x1 + 1 < n and board[y1][x1 + 1] == 0 and board[y2][x1 + 1] == 0:
            if not {(y1 ,x1), (y1, x1 + 1)} in visited:
                dq.append([y1, x1, y1, x1 + 1, 1, next[5] + 1])
                visited.append({(y1 ,x1), (y1, x1 + 1)})
            if not {(y2, x2), (y2, x2 + 1)} in visited:
                dq.append([y2, x2, y2, x2 + 1, 1, next[5] + 1])
                visited.append({(y2 + 1, x2), (y2, x2)})
        if 0 <= x1 - 1 < n and board[y1][x1 - 1] == 0 and board[y2][x1 - 1] == 0:
            if not {(y1 ,x1), (y1, x1 - 1)} in visited:
                dq.append([y1, x1, y1, x1 - 1, 1, next[5] + 1])
                visited.append({(y1 ,x1), (y1, x1 - 1)})
            if not {(y2, x2), (y2, x2 - 1)} in visited:
                dq.append([y2, x2, y2, x2 - 1, 1, next[5] + 1])
                visited.append({(y2 - 1, x2), (y2, x2)})
    
def bfs(board):
    n = len(board) - 1
    robot = [0, 0, 0, 1, 1, 0] # y1, x1, y2, x2, status, time
    visited.append({(robot[0], robot[1]), (robot[2], robot[3])})
    dq.append(robot)
    while dq:
        now = dq.popleft()
        if (now[0] == n and now[1] == n) or (now[2] == n and now[3] == n):
            return now[5]
        for _ in dxdy:
            next = [now[0] + _[0], now[1] + _[1], now[2] + _[0], now[3] + _[1], now[4], now[5] + 1]
            if move_check(board, next) and not {(next[0], next[1]), (next[2], next[3])} in visited:
                visited.append({(next[0], next[1]), (next[2], next[3])})
                dq.append(next)
        rot_check(board, now)
    

def solution(board):
    return bfs(board)

---

지금까지 2020 KAKAO BLIND RECRUITMENT - 블록 이동하기 였습니다. ^_^