Lv2. 게임 맵 최단거리

문제 보기 :  게임 맵 최단거리

프로그래머스

 

---

문제

• 정답률 : 61%

---

작성 코드

from collections import deque
    
def bfs(g,start,n,m):
    vis = [[False]*m for i in range(n)]
    vis[start[0]][start[1]] = True
    
    d = [[-1,0],[1,0],[0,-1],[0,1]]
    
    dd = deque([start])
    while dd:
        x,y = dd.popleft()
        if x == n-1 and y == m-1:
            return g[x][y]
        for dx,dy in d:
            X = dx+x ; Y = dy+y
            if 0<=X<n and 0<=Y<m and g[X][Y]==1 and not vis[X][Y]:
                g[X][Y] = g[x][y]+1
                vis[X][Y] = True
                dd.append([X,Y])
    return -1
            
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    return bfs(maps,[0,0],n,m)

---

풀이

삼성 코테를 준비하면서 DFS/BFS 코드를 외우고 있는데 이 문제가 딱 문제여서 풀이했다.

완전 BFS 문제의 정석이라.. BFS의 다른 방식도 있기도 해서 그 코드도 첨부한다.

from collections import deque

def bfs(graph,start,visited):
    visited[start] = True
    dd = deque([start])
    while dd:
        node = dd.popleft()
        print(node, end=' ')
        for n in sorted(graph[node]):
            if not visited[n]:
                dd.append(n)
                visited[n]=True

viss = [False]*(n+1)
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

bfs(graph,v,viss)