[프로그래머스/파이썬(Python)] 미로 탈출 level2

💌문제

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

 

💌풀이

---

조건 중에

• 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다

를 잘 생각해야 했던 문제이다.

 

flag 변수를 가지고 bfs를 두 번 돌렸다.

처음 bfs는 레버를 찾고,

다음으로 돌리는 bfs는 출구를 찾는다.

레버를 찾게 되면 flag값을 1로 변경한다.

그래서 flag 0일 때는 레버를 찾고 있는 중으로, S, E, O를 방문할 수 있게 했다. 레버를 발견하면 좌표값을 반환하고 answer에 레버까지 도달한 최단거리를 저장한다.

flag가 1일 때는 레버위치에서부터 출구를 찾는 중으로 S, L, O를 방문할 수 있게 했다. 출구를 발견하면 answer에 최단거리를 합산해서 저장한뒤 반환한다.

만약 레버를 찾았는데 출구는 못 찾은 경우가 있을 수 있다. 그래서 레버까지 도달한 answer 값과 출구를 찾는 bfs를 돌린 후의 answer값이 그대로라면 출구를 못찾았다는 것이므로 -1을 반환해야 한다.

 

좀 더럽게 짠 것 같아 아쉽다.

실제 코테에 나왔으면 엣지케이스때문에 실패했을 문제다. 조건을 잘 생각하고 항상 엣지케이스 생각도 잘 해야 할 것 같다.

💌파이썬 코드

---

from collections import deque
flag=0
answer=0
def solution(maps):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    
    def bfs(x,y):
        global flag,answer
        visited=[[0]*len(maps[0]) for _ in range(len(maps))]
        visited[x][y]=1
        q=deque()
        q.append((x,y))
        
        while q:
            cx,cy=q.popleft()
            for i in range(4):
                nx,ny=cx+dx[i],cy+dy[i]
                if nx<0 or nx>=len(maps) or ny<0 or ny>=len(maps[0]):
                    continue
                if (maps[nx][ny]=='O' or maps[nx][ny]=='S') and visited[nx][ny]==0:
                    visited[nx][ny]=visited[cx][cy]+1
                    q.append((nx,ny))
                elif maps[nx][ny]=='L' and flag==0:
                    visited[nx][ny]=visited[cx][cy]+1
                    labor=[nx,ny]
                    flag=1
                    answer=visited[nx][ny]-1
                    return labor
                elif maps[nx][ny]=='E' and flag==1:
                    visited[nx][ny]=visited[cx][cy]+1
                    end=[nx,ny]
                    answer+=visited[nx][ny]-1
                    return end
                elif maps[nx][ny]=='L' and visited[nx][ny]==0 and flag==1:
                    visited[nx][ny]=visited[cx][cy]+1
                    q.append((nx,ny))
                elif maps[nx][ny]=='E' and visited[nx][ny]==0 and flag==0:
                    visited[nx][ny]=visited[cx][cy]+1
                    q.append((nx,ny))
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j]=='S':
                x=bfs(i,j)
                break
    if answer==0 and flag==0:
        return -1
    firstAns=answer
    x=bfs(x[0],x[1])
    if firstAns==answer:
        return -1
    
    return answer