[이것이 코딩테스트다] 미로 탈출

미로 탈출

난이도 1.5

이것이 코딩테스트다 with python

 

python3

from collections import deque


def solution(_map):
    visited = []
    queue = deque([(0, 0)])
    count = 0

    # 해당 문제에서 시작점은 하나로 고정이므로, for문을 사용할 필요가 없습니다.
    return bfs(_map, visited, queue, count)


def add_coord(c1):
    def _add_coord(c2):
        return c1[0] + c2[0], c1[1] + c2[1]

    return _add_coord


def is_in_boundary(_map):
    def _is_in_boundary(c):
        is_in_row = 0 <= c[0] < len(_map)
        if not is_in_row:
            return False
        is_in_column = 0 <= c[1] < len(_map[c[0]])
        if not is_in_column:
            return False
        return True

    return _is_in_boundary


def is_can_visit(_map):
    def _is_can_visit(c):
        return _map[c[0]][c[1]] == 1

    return _is_can_visit


def is_not_visited(visited):
    def _is_not_visited(c):
        return c not in visited

    return _is_not_visited


def bfs(_map, visited, queue, count):
    # 방문할 수 있는 모든 노드를 방문한 경우.
    if len(queue) == 0:
        return count

    # 방문처리하기에 앞서 큐에서 빼줍니다.
    coord = queue.popleft()
    row, column = coord

    # 탈출 조건. 방문 여부 확인은 여기서 하는 대신, queue 에 넣을 때 해주는 것이 더 효율적이다.
    if _map[row][column] == 0:
        return count

    # 방문처리. 방문한경우, 경로의 길이를 1 증가시킵니다.
    visited.append(coord)
    count += 1
    print(coord, visited, queue, count)

    # 탈출구에 도착한 경우
    rows = len(_map) - 1
    columns = len(_map[rows]) - 1
    if coord == (rows, columns):
        return count

    # 큐에 이웃 노드 넣기
    path = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    neighbor = list(filter(is_not_visited(visited),
                           filter(is_can_visit(_map), filter(is_in_boundary(_map), map(add_coord(coord), path)))))

    neighbor_len = len(neighbor)
    queue.extend(neighbor)
    # BFS. 만약 최단경로가 아닌 노드를 방문했다면(방문할 이웃 노드가 0개인 경우), 증가시켰던 길이를 1 줄여줍니다.
    return bfs(_map, visited, queue, count - 1 if neighbor_len == 0 else count)


_map = [
    [1, 0, 1, 0, 1, 0],
    [1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1],
]
print(solution(_map))

DFS나 BFS를 이용한 좌표 문제를 풀 땐 항상

1. 좌표 계산 함수
2. 경계 확인 함수
3. 방문 확인 함수

는 기본으로 구현하고 들어가는 것 같네요.