백준 2178 미로 탐색 python (BFS 최단거리)

 

미로 탐색은 BFS 너비탐색을 이용한 최단 거리 구하기의 대표적 문제다.

 

Node 객체에는 x좌표, y좌표 그리고 최단거리를 구하기 위한 거리를 정의했다.

 

1. 출발 위치 Node 를 큐에 넣고

2. next_visit함수를 이용해 갈수 있는 Node를 큐에 담는다

3. 큐에 Node를 하나씩 꺼내서 탐색한다.

4. 이때 방문한 Node의 좌표를 visit 배열에 넣어 갔던 곳은 가지 않도록 한다.

5. 도착점에 도착할때까지 반복

 

class Node:
    def __init__(self,x,y,dist = 1):
        self.xSpot = x
        self.ySpot = y
        self.dist = dist
    #좌표 반환
    def get_xy(self):
        return (self.xSpot, self.ySpot)

def next_visit(maze ,node):
    nextNodes = []
    x = node.xSpot
    y = node.ySpot
    dist = node.dist + 1

    if x > 0 and maze[x-1][y] == '1':
        nextNodes.append( Node(x-1, y, dist))

    if x < len(maze) - 1 and maze[x+1][y] == '1':
        nextNodes.append( Node(x+1, y, dist))

    if y > 0 and maze[x][y-1] == '1':
        nextNodes.append(  Node(x, y-1, dist) )

    if y < len(maze[0]) - 1  and maze[x][y+1] == '1':
        nextNodes.append( Node(x, y+1, dist))

    return nextNodes


def code_2178():
    #input
    n, m = map(int, input().split())
    maze = []
    for i in range(0,n):
        maze.append(input())

    rootNode = Node(0, 0)
    queue = [rootNode]
    visit = []

    while queue:
        node = queue.pop(0)
        #goal
        if node.get_xy() == (n-1, m-1):
            print(node.dist)
            break
        #next
        if node.get_xy() not in visit:
            visit.append(node.get_xy())
            queue.extend(next_visit(maze, node))

code_2178()

 

 

python class에 익숙하지가 않아서 구현하는데 쵸큼 걸렸다;;