2021 카카오 채용연계형 인턴십-미로탈출

김가영·2021년 7월 27일

Algorithm

목록 보기

78/78

미로 탈출

추가 테스트 케이스

제가 만든 추가 테스트 케이스를 공유합니다.

전체 코드

from collections import deque
import heapq as hq
def solution(n, start, end, roads, traps):

    answer = 0
    
    roadsFrom = {}
    roadsTo = {}
    visited = {}
    
    for i in range(n+1):
        visited[i] = {}
        roadsFrom[i] = []
        roadsTo[i] = []
    
    for s, e, c in roads:
        roadsFrom[s].append((e, c))
        roadsTo[e].append((s, c))
    

    q = []
    hq.heappush(q, [0, start, []])
    visited[start][()] = 0
    
    def renewTraps(cur_traps_on, new):
        if new not in traps:
            return cur_traps_on
        if new in cur_traps_on:
            cur_traps_on.remove(new)
            return cur_traps_on
        if new in traps:
            cur_traps_on.append(new)
            return sorted(cur_traps_on)
        return cur_traps_on
    
    def push():
        new_traps_on = renewTraps(traps_on.copy(), destination)
        if tuple(new_traps_on) in visited[destination] and visited[destination][tuple(new_traps_on)] < count + cost:
            return
        visited[destination][tuple(new_traps_on)] = count + cost
        hq.heappush(q, [count+cost, destination, new_traps_on])

    
    while q:
        count, cur, traps_on = hq.heappop(q)
        if cur == end:
            return count
            
        if cur not in traps_on:
            for destination, cost in roadsFrom[cur]:
                if destination not in traps_on:
                    push()
            for destination, cost in roadsTo[cur]:
                if destination in traps_on:
                    push()
        else:
            for destination, cost in roadsFrom[cur]:
                if destination in traps_on:
                    push()
            for destination, cost in roadsTo[cur]:
                if destination not in traps_on:
                    push()

    return answer

풀이

기본적인 풀이법은 BFS입니다.
함정 x에 처음 방문하면 x와 연결된 길들의 방향이 바뀝니다. 다시 함정 x에 방문하면 원래 방향으로 바뀝니다.
길들의 방향은 함정들의 정보를 통해 알 수 있습니다. -> 함정의 정보를 저장해야합니다.

함정의 정보를 이용하자

함정을 처음 방문하여 길들의 방향이 원래 방향의 반대가 된 것을 함정이 활성화되었다라고 하겠습니다. 반대는 비활성화되었다고 표현하겠습니다.
a에서 b로 갈 수 있는 길(a → b)이 존재할 때, 해당 길을 이용할 수 있는 지를 확인하기 위해서는 a와 b의 활성화 상태만을 확인하면 됩니다.
- a와 b가 모두 활성화되지 않았다면(또는 함정이 아니라면) 길의 방향은 그대로입니다.
- a와 b가 모두 활성화되었다면 길의 방향은 두번 바뀌어 그대로가 됩니다.
- a가 활성화되었고 b가 활성화되지 않았다면(또는 함정이 아니라면) 길의 방향은 반대가 됩니다.
- b가 활성화되었고 a가 활성화되지 않았다면(또는 함정이 아니라면) 길의 방향은 반대가 됩니다.

BFS

queue(q)에는 현재 방번호와 현재 활성화된 trap들의 번호, 현재 시간이 저장됩니다. (현재 시간을 기준으로 우선순위 큐를 이용하고 있기 때문에 현재 시간이 첫번째 원소로 저장됩니다.)
방문한 정보는 visited 에 저장됩니다.
visited에는 방번호와 현재 활성화된 함정의 리스트, 현재 cost를 저장해야합니다. 그 이유는 다음과 같습니다.
- 현재 방번호가 같더라도 활성화된 함정의 리스트가 다르다면 길의 방향이 달라집니다.
- 활성화된 함정 리스트가 같더라도 더 적은 비용을 가지고 있을 수 있습니다.(추가 테스트케이스3번 참고)
visited에 단순히 cost와 함정 리스트를 함께 저장하고 이와 다르면 방문하도록 설정하면 시간 초과가 날 수 있습니다. → 함정 리스트를 먼저 비교하고, cost가 더 적을 경우에만 방문하도록 설정해야합니다.
그래서 visited[방번호][트랩리스트(frozenset)] 에 해당 방번호에 특정 트랩리스트를 가지고 방문한 최소 cost를 저장하도록 했습니다.
visited와 visited[방번호]는 모두 딕셔너리입니다.

코드

기본 세팅

    answer = 0
    
    roadsFrom = {}
    roadsTo = {}
    visited = {}
    
    for i in range(n+1):
        visited[i] = {}
        roadsFrom[i] = []
        roadsTo[i] = []
    
    for s, e, c in roads:
        roadsFrom[s].append((e, c))
        roadsTo[e].append((s, c))

처음 세팅 부분입니다.
roadsFrom[i] 는 i번 방에서 출발하는 길들의 (도착 방, 걸리는 시간) 리스트입니다.
roadsTo[i] 는 i번 방으로 도착하는 길들의 (출발 방, 걸리는 시간) 리스트입니다.

BFS

    while q:
        count, cur, traps_on = hq.heappop(q)
        if cur == end:
            return count
            
        if cur not in traps_on:
            for destination, cost in roadsFrom[cur]:
                if destination not in traps_on:
                    push()
            for destination, cost in roadsTo[cur]:
                if destination in traps_on:
                    push()
        else:
            for destination, cost in roadsFrom[cur]:
                if destination in traps_on:
                    push()
            for destination, cost in roadsTo[cur]:
                if destination not in traps_on:
                    push()

q에는 count(현재 시간), cur(현재 방번호), traps_on(현재 활성화된 트랩)이 저장됩니다.
현재 방번호가 목적지인 경우에는 값을 리턴하고 종료합니다.

현재 방에서 갈 수 있는 다음 방들을 구하기 위해서는

현재 방이 활성화된 함정인지
목적지 방이 활성화된 함정인지 정보가 필요합니다.

경우를 나눠 현재 방이 활성화되었는지 확인하고, 활성화되지 않았다면

현재 방에서 갈 수 있는 길들 리스트(roadsFrom[cur])에서 목적지도 활성화되지 않은 방들을 찾아 q에 넣으려고 시도합니다(push, 뒷부분에 설명)
현재 방으로 오는 길들의 리스트(roadsTo[cur])에서 목적지가 활성화된 방들을 찾아 q에 넣으려고 시도합니다(push)

현재 방이 활성화된 경우도 같은 방법으로 q에 넣으려고 시도합니다.

push 함수

    def renewTraps(cur_traps_on, new):
        if new not in traps:
            return cur_traps_on
        if new in cur_traps_on:
            cur_traps_on.remove(new)
            return cur_traps_on
        if new in traps:
            cur_traps_on.append(new)
            return sorted(cur_traps_on)
        return cur_traps_on
    
    def push():
        new_traps_on = renewTraps(traps_on.copy(), destination)
        if tuple(new_traps_on) in visited[destination] and visited[destination][tuple(new_traps_on)] < count + cost:
            return
        visited[destination][tuple(new_traps_on)] = count + cost
        hq.heappush(q, [count+cost, destination, new_traps_on])

renewTraps 은 현재 활성화된 함정들(cur_traps_on)이 존재하고 새로운 방(new)을 방문하였을 때 새롭게 변경된, 활성화된 함정 리스트를 리턴합니다.

push 는 새로운 목적지를 추가하려고 시도하는 함수입니다. 만약 visited[목적지][트랩] 가 존재하면 해당 목적지에 같은 (활성화된) 트랩 리스트를 가지고 방문한 적이 있다는 뜻입니다. 당시의 비용을 확인하고 비용이 더 적을 때에만 q에 추가합니다. visited[목적지][트랩]가 존재하지 않는다면 해당 목적지에 같은 트랩리스트를 가지고 방문한 적이 없다는 의미이므로 바로 q에 추가합니다.