Get directions to final point in a labyrinth represented by a multidimensional list

labyrinth.py

from collections import namedtuple


def get_directions_to_final_point(labyrinth):

    def check_neighbour(f, c, direction):
        """ Check if the neighbour might be added to branch
        or is needed create a new branch """
        if labyrinth[f][c] == 0 and (f, c) not in copy_pos_branch:
            if len(branch) == len_branch:
                branch.append(Node(f, c, direction))
                return

            new_branch = list(copy_branch)
            new_branch.append(Node(f, c, direction))
            branches.append(new_branch)

    Node = namedtuple('Node', ['y', 'x', 'direction'])

    branches = [[Node(1, 1, '')]]
    goal = (len(labyrinth) - 2, len(labyrinth[0]) - 2)

    search = True
    while search:
        for branch in branches[:]:
            copy_branch = list(branch)
            copy_pos_branch = [(node.y, node.x) for node in branch]
            file_, column = branch[-1].y, branch[-1].x
            len_branch = len(copy_branch)

            check_neighbour(file_, column + 1, 'E')
            check_neighbour(file_ + 1, column, 'S')
            check_neighbour(file_ - 1, column, 'N')
            check_neighbour(file_, column - 1, 'W')

            if len(branch) == len_branch:
                # If wasn't changed branch or wasn't created a new branch,
                # then remove branch
                branches.remove(branch)

            if (branch[-1].y, branch[-1].x) == goal:
                search = False
                break

        # Prune branches that has a same last node
        temp_branches = []
        last_nodes = set()
        for branch in branches:
            if (branch[-1].y, branch[-1].x) not in last_nodes:
                last_nodes.add((branch[-1].y, branch[-1].x))
                temp_branches.append(branch)

        branches = temp_branches

    print ''.join([r.direction for r in branch])  # directions
    return ''.join([r.direction for r in branch])


get_directions_to_final_point([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])