[알고리즘] 프로그래머스 미로 탈출 - Python

문제 : 프로그래머스 미로 탈출 문제

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

프로그래머스

 

처음에 문제를 보자마자 dfs/bfs 라는 것을 알 수 있었다. 나는 bfs를 선택했다. 그 이유는 경로까지 걸린 거리를 측정해야해했기 때문에 dfs보다는 bfs를 사용하는 것이 적합하다고 생각했다. 

 

그리고 구현 방법은 크게 3가지 단계로 생각했다. 

• S, L, E 각각의 인덱스 기록하기 및 board 0으로 초기화
• bfs 2회 : 첫번째 bfs(S에서 L까지), 두번째 bfs(L에서 E까지)
• 도달하지 못한 경우 판별

처음에는 board를 두지 않고 바로 maps에 기록하며 bfs를 하려고 했다. 다만 이렇게 할 경우 문자를 숫자로 바꾸고 다시 문자로 바꾸는 번거로운 작업이 추가될 것이기에 board를 두어 따로 걸린 거리를 측정하는 것으로 했다. 

이렇게 구현을 했을 때 가장 초기 코드는 다음과 같다. 

 

from collections import deque
def solution(maps):
    answer = 0
    si,sj,li,lj,ei,ej=0,0,0,0,0,0
    board=[[0]*len(maps[0]) for _ in range(len(maps))]
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j]=='X':
                continue
            elif maps[i][j]=='S':
                si,sj=i,j
            elif maps[i][j]=='L':
                li,lj=i,j
            elif maps[i][j]=='E':
                ei,ej=i,j
    def bfs(bi,bj, exi,exj):
        q=deque()
        q.append((bi,bj))
        dx=[0,1,-1,0]
        dy=[1,0,0,-1]
        while q:
            ci,cj=q.popleft()
            for i in range(4):
                ni,nj=ci+dx[i],cj+dy[i]
                ni = ci + dx[i]
                nj = cj + dy[i]
                if 0<=ni<len(maps) and 0<=nj<len(maps[0]) and maps[ni][nj] != 'X' and board[ni][nj] == 0:
                    board[ni][nj]=board[ci][cj]+1
                    q.append((ni,nj))
        if board[exi][exj]==0: return -1
        else: return board[exi][exj]
    
    time_l = bfs(si,sj,li,lj)
    if time_l ==-1:
        return -1
    else:
        return bfs(li,lj,ei,ej)
    return answer

 

이 코드에서 발생하는 문제는 bfs 2회를 돌리면서 board가 초기화되지 않았다는 것이다. 이 부분이 중요한 이유는 첫번째 bfs와 두번째 bfs는 별개이기 때문이다. 만약 두 번의 bfs에서 같은 경로로 거쳐가게 되면 오염된 board의 숫자를 참고하게 되기 때문에 잘못된 답이 도출된다는 것을 알았다. 

 

그래서 다음과 같이 수정해보았다. 

from collections import deque
def solution(maps):
    answer = 0
    si,sj,li,lj,ei,ej=0,0,0,0,0,0
    board=[[0]*len(maps[0]) for _ in range(len(maps))]
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j]=='X':
                continue
            elif maps[i][j]=='S':
                si,sj=i,j
            elif maps[i][j]=='L':
                li,lj=i,j
            elif maps[i][j]=='E':
                ei,ej=i,j
    def bfs(bi,bj, exi,exj):
        q=deque()
        q.append((bi,bj))
        dx=[0,1,-1,0]
        dy=[1,0,0,-1]
        while q:
            ci,cj=q.popleft()
            for i in range(4):
                ni,nj=ci+dx[i],cj+dy[i]
                ni = ci + dx[i]
                nj = cj + dy[i]
                if 0<=ni<len(maps) and 0<=nj<len(maps[0]) and maps[ni][nj] != 'X' and board[ni][nj] == 0:
                    board[ni][nj]=board[ci][cj]+1
                    q.append((ni,nj))
        if board[exi][exj]==0: return -1
        else: return board[exi][exj]
    
    time_l = bfs(si,sj,li,lj)
    if time_l == -1:
        return -1
    else:
        board=[[0]*len(maps[0]) for _ in range(len(maps))]
        return time_l+bfs(li,lj,ei,ej)
    return answer

 

중간에 board 초기화를 다시 해주었다. 그런데 이 코드로도 하나의 테스트 케이스를 통과하지 못하였다. 그 이유를 생각해보니 첫번째 bfs에서는 -1인 경우를 검사해주었지만, 두번째 bfs 이후에 -1이 나왔을 때는 -1을 출력하는 것이 아닌 첫번째 bfs와 두번째 bfs의 결과의 합을 구하기 때문이었다. 그래서 이 부분을 수정한 최종 코드는 다음과 같다. 

 

from collections import deque
def solution(maps):
    answer = 0
    si,sj,li,lj,ei,ej=0,0,0,0,0,0
    board=[[0]*len(maps[0]) for _ in range(len(maps))]
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j]=='X':
                continue
            elif maps[i][j]=='S':
                si,sj=i,j
            elif maps[i][j]=='L':
                li,lj=i,j
            elif maps[i][j]=='E':
                ei,ej=i,j
    def bfs(bi,bj, exi,exj):
        q=deque()
        q.append((bi,bj))
        dx=[0,1,-1,0]
        dy=[1,0,0,-1]
        while q:
            ci,cj=q.popleft()
            for i in range(4):
                ni,nj=ci+dx[i],cj+dy[i]
                ni = ci + dx[i]
                nj = cj + dy[i]
                if 0<=ni<len(maps) and 0<=nj<len(maps[0]) and maps[ni][nj] != 'X' and board[ni][nj] == 0:
                    board[ni][nj]=board[ci][cj]+1
                    q.append((ni,nj))
        if board[exi][exj]==0: return -1
        else: return board[exi][exj]
    
    time_l = bfs(si,sj,li,lj)
    if time_l == -1:
        return -1
    else:
        board=[[0]*len(maps[0]) for _ in range(len(maps))]
        time_e=bfs(li,lj,ei,ej)
        if time_e ==-1: return -1
        else : return time_l+time_e
    return answer

 

이 코드로는 테스트 케이스를 모두 통과한다. 

 

bfs/dfs는 구현할 때 예외 케이스를 꼼꼼하게 처리해야한다는 것을 또 한번 느꼈다..