[프로그래머스][KAKAO_인턴][2021] 미로 탈출

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

https://programmers.co.kr/learn/courses/30/lessons/81304

코딩테스트 연습 - 미로 탈출

 

내가 작성한 코드

None

• BFS / 다익스트라 등 다양한 시도를 했었다
  • 다익스트라 구현중 함정과 연관된 edge만 뒤집는 방식에서 막혔다
  • 시간관계상 다음에 살펴보기로 했다

 

다른 사람이 작성한 코드

import heapq as h
def solution(n, start, end, roads, traps):
    start -=1; end -=1;
    INF = float("inf");
    graph = [[] for _ in range(n)]
    trap_dict = {trap-1:idx for idx, trap in enumerate(traps)};
    nodes = [];
    isVisit = [[False]*n for _ in range(1<<len(traps))]
    
    for road in roads:
        start_i, end_i, cost = road
        graph[start_i-1].append([end_i-1,cost,0])
        graph[end_i-1].append([start_i-1,cost,1])
    
    h.heappush(nodes,(0,start,0))
    while nodes:
        cur_time, cur_node, state = h.heappop(nodes);
        if cur_node == end : return cur_time;      
        if isVisit[state][cur_node] == True: continue;
        else: isVisit[state][cur_node] = True;
            
        for next_node, next_cost, road_type in graph[cur_node]:
            next_state = state
            cur_isTrap = 1 if cur_node in trap_dict else 0;
            next_isTrap = 1 if next_node in trap_dict else 0;

            if cur_isTrap == 0 and next_isTrap == 0:
                if road_type == 1: continue
            elif (cur_isTrap + next_isTrap) == 1:
                node_i = cur_node if cur_isTrap == 1 else next_node
                isTrapOn = (state & (1<<trap_dict[node_i]))>>trap_dict[node_i]
                if isTrapOn != road_type: continue
            else:
                isTrapOn = (state & (1<<trap_dict[cur_node]))>>trap_dict[cur_node]
                n_isTrapOn = (state & (1<<trap_dict[next_node]))>>trap_dict[next_node]
                if (isTrapOn ^ n_isTrapOn) != road_type: continue
            
            if next_isTrap == 1:
                next_state = state ^ (1<<trap_dict[next_node])

            h.heappush(nodes,(cur_time+next_cost, next_node, next_state))

• 제대로 정독하진 못했지만, 비트마스킹으로 함정의 상태를 표시하신 듯 하다
• 그림까지 그려주시면서 설명이 되어있다

 

https://sklubmk.github.io/2021/07/15/28bed7b50dc1/

[프로그래머스] (LV4) 미로 탈출

 

기억해야할 것

• Node와 Edge에 대한 연결 방식을 항상 dict로 해왔다
• 이와 같은 문제에서 어떤 식으로 두 관계를 정의하여 활용해야하는지 알아둬야겠다