[프로그래머스] 게임 맵 최단거리 in python

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

---

문제를 보며 요약한 내용=>
내 위치 : (1,1)
상대 위치 : (n,m)
검은색 = 막힌 길 (0)
흰색 = 갈 수 있는 길 (1)
맵 벗어난 길은 갈 수 없다.

상대 팀 진영으로 가는 가장 빠른 길 -> bfs?
도착못할수도 있다. -> visited[x][y]=-1이면 도착 못한 거! => -1 출력


최단 거리를 구하는 문제라서bfs를 사용했다!가장 인접한 구간부터 탐색을 진행한다.따라서 가장 가까운 길로 도달한 값이 visited에 저장이 되게끔 설계하면 되는 것이다.

 

 

can_go 메서드 부분에서not visited[x][y]를 빼먹으면무한 루프에 빠지니까 조심할 것...!(매일 빼먹는 나 자신, 반성하자) 

 

from collections import deque
visited=[]
n,m=-1,-1

def in_range(x,y):
    global n,m
    return 0<=x<n and 0<=y<m

def can_go(x,y,maps):
    global visited
    return in_range(x,y) and maps[x][y]==1 and not visited[x][y]

def bfs(x,y,maps):
    global visited
    dxs,dys=[-1,1,0,0],[0,0,-1,1] # 상,하,좌,우
    queue=deque()
    queue.append((x,y))
    visited[x][y]=1
    while queue:
        cx,cy=queue.popleft()
        for dx,dy in zip(dxs,dys):
            nx,ny=cx+dx,cy+dy
            if can_go(nx,ny,maps):
                queue.append((nx,ny))
                visited[nx][ny]=visited[cx][cy]+1
                

def solution(maps):
    global visited,n,m
    answer = 0
    n=len(maps) # 행 
    m=len(maps[0]) # 열
    visited=[[0 for _ in range(m)] for _ in range(n)]
    bfs(0,0,maps)
    answer=visited[n-1][m-1]
    if answer==0:
        return -1
    return answer