알고리즘 코드카타 124- 미로 탈출

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

프로그래머스

 

 

문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항
5 ≤ maps의 길이 ≤ 100
5 ≤ maps[i]의 길이 ≤ 100
maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
S : 시작 지점
E : 출구
L : 레버
O : 통로
X : 벽
시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

 

 

이제는 익숙해진 미로찾기 문제, BFS탐색으로 풀어볼 예정이다.

 

def solution(maps):
    for i, m in enumerate(maps):
        if 'S' in m:
            s_x, s_y = (m.find("S"), i)
        if 'L' in m:
            l_x, l_y = (m.find("L"), i)

 

먼저 미로의 시작점을 탐색한다. maps리스트를 순회하면서 S가 있는 행을 마주친다면 해당 행의 순번과 S의 위치를 반환하여 시작지점의 좌표값을 구한다.

또한, 이 문제에서 도착점에 도달하기 전에 출구를 열기 위해서 레버를 조작해야 하므로 S -> L -> E순으로 이동해야한다.

즉, S에서 출발하는 경우와 L에서 출발하는 경우를 모두 고려해야하기 때문에 위와 같은 방법으로 L의 좌표도 구해준다.(S에서 L까지의 최단경로를 탐색하면서 L의 좌표를 반환할 수도 있지만 두 방법 모두 사용해보니 S와 L의 좌표를 각각 구해주는 편이 속도가 더 빨라서 이렇게 작성을 했다.)

 

# def solution(maps):
#     for i, m in enumerate(maps):
#         if 'S' in m:
#             s_x, s_y = (m.find("S"), i)
#         if 'L' in m:
#             l_x, l_y = (m.find("L"), i)
    distance_s_to_l = bfs(maps, s_x, s_y, 'L')
    distance_l_to_e = bfs(maps, l_x, l_y, 'E')
    
    if distance_s_to_l == -1 or distance_l_to_e == -1:
        return -1
    else:
        return distance_s_to_l + distance_l_to_e

 

bfs 탐색을 통해서 목적지까지의 거리를 계산한다. bfs함수는 지도, 출발지점의 좌표, 목적지를 인자로 받아서 출발지점에서 목적지까지의 최단거리를 반환하는 함수이다. 이때 목적지까지 도달할 수 없다면 -1을 반환한다.

그러므로 distance_s_to_l, distance_l_to_e 둘중 하나의 값이 -1일 경우 목적지에 도달할 수 없기 때문에 solution함수는 -1을 반환하고 그렇지 않을 경우에는 두 최단거리의 합을 더해서 출발지점에서 레버를 거쳐서 도착지점까지 도착을 하는 최단거리를 반환한다.

 

def bfs(maps, x, y, to):
    delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
    explore = [(x, y, 0)]

 

이제 미로를 탐색하기 위해서 bfs함수를 작성한다.

각 방향을 표시하기 위해서 delta를 지정해두었고 시작지점의 좌표를 탐험할 리스트의 목록인 explore에 저장을 했다.

 

# def bfs(maps, x, y, to):
#     delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
#     explore = [(x, y, 0)]
    
    while explore:
        current_x, current_y, current_d = explore.pop(0)
        for d in range(4):
            new_x = current_x + delta_x[d]
            new_y = current_y + delta_y[d]

 

explore리스트의 원소가 없을때까지 반복문을 실행한다. 탐색을 시도할 때마다. explore.pop(0)로 explore의 원소들을 제거하기 때문에 explore가 모두 비게 된 다는 것은 탐색할 공간이 없다는 것을 의미하기 때문이다.

explore의 가장 앞의 원소를 pop해서 현재 위치와 거리를 저장한다. 그리고 4방향에 대해서 반복한다. d의 값은 0~3까지의 값을 가지게 되며 각각 delta_x, delta_y의 원소들과 대응이 된다.

 

# def bfs(maps, x, y, to):
#     delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
#     explore = [(x, y, 0)]
    
#     while explore:
#         current_x, current_y, current_d = explore.pop(0)
        for d in range(4):
            new_x = current_x + delta_x[d]
            new_y = current_y + delta_y[d]
            if 0 <= new_x < len(maps[0]) and 0 <= new_y < len(maps) and maps[new_y][new_x] != 'X':
                
                explore.append((new_x, new_y, current_d+1))
    
    return -1

 

delta가 적용된 x, y값을 각각 new_x, new_y라고 하고 해당 위치를 탐색한다. 조건문의 각조건을 다음과 같다.

• 0 <= new_x < len(maps[0]) : x의 인덱스가 maps을 벗어났는지 아닌지 확인한다.
• 0 <= new_y < len(maps[0]) : y의 인덱스가 maps을 벗어났는지 아닌지 확인한다.
• maps[new_y][new_x] != 'X' : 현재 탐색중인 좌표의 값이 벽인지 아닌지 확인한다.

이상의 조건을 모두 통과했을 경우 해당 칸을 기준으로 다시 탐색을 하기 위해서 explore에 해당 좌표를 추가한다. 그리고 한칸을 이동했다는 의미이므로 current_d를 하나 증가시킨다.

또한 while반복문이 종료된 경우, 목적지에 도달하지 못하고 탐색이 종료되었으므로 -1을 반환하면 된다.

 

# def bfs(maps, x, y, to):
#     delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
#     explore = [(x, y, 0)]
    
#     while explore:
#         current_x, current_y, current_d = explore.pop(0)
        if maps[current_y][current_x] == to:
            return current_d
#         for d in range(4):
#             new_x = current_x + delta_x[d]
#             new_y = current_y + delta_y[d]
#             if 0 <= new_x < len(maps[0]) and 0 <= new_y < len(maps) and maps[new_y][new_x] != 'X':
                
#                 explore.append((new_x, new_y, current_d+1))
    
#     return -1

 

이제 탐색을 시작하는 시점의 값이 목적지와 일치할 경우 현재 거리를 반환해주면 목적지까지의 최단경로 탐색은 끝나게 된다.

?

 

그런데 결과는 시간초과가 나왔다. 시간초과가 되지 않은 다른 케이스들은 모두 통과한 것을 보니 로직에 문제가 있는 것은 아닌듯했다. 그래서 수정을 위해 코드를 다시보니 아차싶었다. 중복탐색을 방지하는 코드를 추가했어야했는데 그걸 하지 않은 바람에 이미 탐색한 장소를 또 탐색하면서 계산량이 많이 늘어나버렸기 때문이다.

 

# def bfs(maps, x, y, to):
#     delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
#     explore = [(x, y, 0)]
    visit = [(x,y)]
    
#     while explore:
#         current_x, current_y, current_d = explore.pop(0)
#         if maps[current_y][current_x] == to:
#             return current_d
#         for d in range(4):
#             new_x = current_x + delta_x[d]
#             new_y = current_y + delta_y[d]
            if 0 <= new_x < len(maps[0]) and 0 <= new_y < len(maps) and maps[new_y][new_x] != 'X' and (new_x, new_y) not in visit:
                
#                 explore.append((new_x, new_y, current_d+1))
                visit.append((new_x, new_y))
    
#     return -1

 

이미 방문한 좌표를 표시해주기 위해서 visit라는 리스트를 작성한다. 그리고 올바른 탐색구간이 맞는지 확인하는 조건문에 다음 조건을 추가한다.

• (new_x, new_y) not in visit : 탐색할 위치가 visit에 없는 경우, 즉 아직 방문하지 않은 좌표인지 확인한다.

그리고 탐색할 리스트인 explore에 추가하고 동시에 이미 탐색한 좌표라는 의미로 visit에도 추가해주면 완료!

성공!

 

def bfs(maps, x, y, to):
    delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
    explore = [(x, y, 0)]
    visit = set((x,y))
    
    while explore:
        current_x, current_y, current_d = explore.pop(0)
        if maps[current_y][current_x] == to:
            return current_d
        for d in range(4):
            new_x = current_x + delta_x[d]
            new_y = current_y + delta_y[d]
            if 0 <= new_x < len(maps[0]) and 0 <= new_y < len(maps) and maps[new_y][new_x] != 'X' and (new_x, new_y) not in visit:
                
                explore.append((new_x, new_y, current_d+1))
                visit.add((new_x, new_y))
    
    return -1

 

마지막으로 속도개선을 위해서 visit를 list에서 set으로 바꿔주었다.

def solution(maps):
    for i, m in enumerate(maps):
        if 'S' in m:
            s_x, s_y = (m.find("S"), i)
        if 'L' in m:
            l_x, l_y = (m.find("L"), i)
    distance_s_to_l = bfs(maps, s_x, s_y, 'L')
    distance_l_to_e = bfs(maps, l_x, l_y, 'E')
    
    if distance_s_to_l == -1 or distance_l_to_e == -1:
        return -1
    else:
        return distance_s_to_l + distance_l_to_e

 

속도가 개선되었다.

 

몇주전만 해도 공간탐색 문제만 나오면 골치가 아팠는데 많이 익숙해진것같다.