[2020 카카오 신입 공채 1차] 블록 이동하기

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

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

 

모든 간선의 길이가 1인 그래프 문제의 경우 BFS를 이용하여 해결할 수 있습니다.

 

 다만 이 문제같은 경우 로봇의 길이가 2x1이기 때문에 좌표 2개를 신경써야 하고, 또한 회전을 구현해야 한다는 점에서 상당히 까다로운 문제입니다. 해당 문제의 시간제한은 1초이며, board의 한 변의 길이가 5 이상 100이하라는 점에서 크게 iteration 횟수에 구애받지 않고 풀이할 수 있으나, 기본적으로 BFS를 사용하면 시간 복잡도는 O(N)입니다. 소스 코드는 다음과 같습니다.

from collections import deque

def solution(board):
    start = {(1, 1), (1, 2)}
    n = len(board)
    board = [[1] * (n + 2)] + list(map(lambda x : [1] + x + [1], board)) + [[1] * (n + 2)]
    visited = []
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    q = deque()
    q.append((start, 0))
    visited.append(start)
    
    answer = int(1e9)
    while q:
        loc, cost = q.popleft()
        (x1, y1), (x2, y2) = list(loc)
		
        # BFS는 가장 먼저 도달하는 경우가 최단 경로임을 보장
        if (x1 == n and y1 == n) or (x2 == n and y2 == n):
            return cost
		
        # 갈 수 있는 모든 경우의 수를 리스트로 관리
        cand = []
        for i in range(4):
            nx1, ny1 = x1 + dx[i], y1 + dy[i]
            nx2, ny2 = x2 + dx[i], y2 + dy[i]
            if board[nx1][ny1] == 0 and board[nx2][ny2] == 0:
                cand.append({(nx1, ny1), (nx2, ny2)})
        if x1 == x2:
            for i in [-1, 1]:
                if board[x1 + i][y1] == 0 and board[x2 + i][y2] == 0:
                    cand.append({(x1, y1), (x1 + i, y1)})
                    cand.append({(x2, y2), (x2 + i, y2)})
        elif y1 == y2:
            for i in [-1, 1]:
                if board[x1][y1 + i] == 0 and board[x2][y2 + i] == 0:
                    cand.append({(x1, y1), (x1, y1 + i)})
                    cand.append({(x2, y2), (x2, y2 + i)})
        
        for l in cand: # 후보군의 좌표 중
            if l not in visited: # 아직 방문하지 않은 곳을 탐색
                visited.append(l)
                q.append((l, cost + 1))
                
    return 'ERROR'

 

 여기서 핵심은 3가지입니다. 첫 번째, board의 관리입니다. 간단한 그래프 탐색에서는 각 좌표가 index error를 반환하지 않는 범위에 있다는 것만 보장하면 되었습니다. 그러나 이 문제의 경우 상하좌우로 이동하는 경우 외에도 회전하는 경우의 좌표까지 고려해야 하기 때문에 각각의 경우에 대해서 좌표의 크기 제한을 고려하는 것은 비효율적입니다. 따라서 다음과 같은 코드를 이용하여 각 변에 1을 패딩하여 줍니다.

board = [[1] * (n + 2)] + list(map(lambda x : [1] + x + [1], board)) + [[1] * (n + 2)]

 이렇게 하면 다음과 같은 결과를 얻을 수 있습니다. 상하좌우에 1만큼 1이 패딩되어 마치 벽처럼 작용하고, 따라서 각 좌표가 1이 아닌 것만 확인한다면 로봇이 그래프 밖의 지점에 도달하지 않음을 보장할 수 있습니다.

[[1, 1, 1, 1, 1, 1, 1],
 [1, 0, 0, 0, 1, 1, 1],
 [1, 0, 0, 0, 1, 0, 1],
 [1, 0, 1, 0, 1, 1, 1],
 [1, 1, 1, 0, 0, 1, 1],
 [1, 0, 0, 0, 0, 0, 1],
 [1, 1, 1, 1, 1, 1, 1]]

 

 두 번째는 visited 변수입니다. BFS를 이용한 그래프 탐색은 일반적으로 동일한 크기의 그래프 상에 방문 정보를 기록하는데 반해, 이 문제는 고려해야 할 좌표가 두개이기 때문에 그러한 방식으로 위치 정보를 저장하는 것은 불가능합니다. 따라서 방문한 좌표를 리스트에 보관하되 각 좌표는 set 자료 구조를 이용하여 이후 첫 번째 좌표와 두 번째 좌표의 위치가 바뀌더라도 방문 지점이 중복되지 않도록 합니다.

for l in cand:
   if l not in visited:
    	visited.append(l)
        q.append((l, cost + 1))

 여기서 한 가지 신경써야 할 점은 append를 하는 위치입니다. 만약 while문의 상단에서 append할 경우 cand 변수에 기록된 '다음으로 이동할 좌표'에 대한 중복이 발생할 수 있습니다. 따라서 반드시 해당 위치에서 visited 변수에 좌표를 append하여 방문처리해주어야 하며, 실제로 반대의 경우 제출 시 시간 초과 오류가 발생했습니다.

 

세 번째는 BFS의 특성을 얼마나 이해했는가가 관건입니다. BFS를 이용할 경우 현재 노드의 인접 노드에 대한 거리를 모두 고려합니다. 따라서 목적지 (N, N)에 가장 먼저 도달하는 경우가 최단 경로라는 것을 보장할 수 있습니다. 다음과 같이 (n, n) 좌표까지 탐색이 완료된 경우 다른 경우의 수를 고려하지 않고 바로 return 해주는 것이 시간복잡도 면에서 이득입니다.

if (x1 == n and y1 == n) or (x2 == n and y2 == n):
    return cost

 

 상당히 복잡한 수준의 구현을 요구함에도 불구하고 경우의 수가 워낙에 많아 시간 복잡도를 고려하지 않으면 시간 초과를 받는 어려운 문제였습니다. 카카오에서 제출하는 문제는 1시간 이내에 푼 적이 많이 없는 것 같습니다.. 그래프 탐색은 나름 자신있다고 생각했는데 아직 가야할 길이 멀다는 것을 알게 해 준 문제인 듯 합니다.