[프로그래머스/Python] 미로 탈출

 

 

문제

문제 설명

 

풀이

 

 

[풀이]

최소 횟수를 구해야 하므로 BFS로 Start지점에서 Lebber까지의 최소 횟수를 구하고, Lebber에서 Exit까지 다시 BFS로 최소 횟수를 구하면 되는 문제다. 즉, BFS를 두 번 써서 해결하면 된다.

​

[요약]

1. Start지점을 찾고 Lebber 까지 걸리는 이동 횟수를 계산한다.

2. Lebber까지 이동이 가능하다면 Lebber부터 Exit까지 이동횟수를 계산한다.

3. 두 이동횟수를 더한 값을 리턴한다.

 

 

 

Code

 

 

dx = [0,0,1,-1]
dy = [1,-1,0,0]
defaultMap=[]
defaultMap2=[]
lenX=0
lenY=0
lebberX=-1
lebberY=-1
def FindMap(yV,xV,myMap,v,isLebber):
    global lenX,lenY,lebberX,lebberY,returnCount
    stacks=[[yV,xV,0]]
    myMap[yV][xV]=0
    while stacks:
        y,x,cnt=stacks.pop(0)
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<lenX and 0<=ny<lenY and myMap[ny][nx]>0:
                stacks.append([ny,nx,cnt+1])
                if isLebber:
                    if myMap[ny][nx]==2:
                        lebberX=nx
                        lebberY=ny
                        return v+cnt+1
                else:
                    if myMap[ny][nx]==3:
                        lebberX=nx
                        lebberY=ny
                        return v+cnt+1
                myMap[ny][nx]=0 # 여기가 더 빠름
    return -1


def solution(maps):
    global defaultMap, defaultMap2, lenY,lenX
    startPoint=[]
    yV,xV=0,0
    lenY=len(maps)
    lenX=len(maps[0])
    for i in range(lenY):
        lst=[]
        for j in range(lenX):
            if maps[i][j]=="X":
                lst.append(0)
            elif maps[i][j]=="O": 
                lst.append(1)
            elif maps[i][j]=="S":
                lst.append(5)
                yV=i
                xV=j
            elif maps[i][j]=="L":
                lst.append(2)
            else: # 출구
                lst.append(3)
        defaultMap.append(lst)
        lst2=[]
        for i in lst:
            lst2.append(i)
        defaultMap2.append(lst2)
    Cnt=FindMap(yV,xV,defaultMap,0,True)
    if Cnt>0:
        return FindMap(lebberY,lebberX,defaultMap2,Cnt,False)
    else:
        return -1

 

---

 

단순 BFS 문제인데, 오랜만에 Python으로 알고리즘을 풀어서 코드가 쓸데없이 길어진 것 같다...

코드가 왤케 길지;; 처음에 리스트의 Y랑 X도 헷갈렸다...