[TIL_Carrotww] 51 - 22/11/14

📝Carrotww의 코딩 기록장

🧲 python algorithm programmers 등대

🔍 programmers 등대 Level3
와 드디어 풀었다 2일정도 걸린거 같은데 주말 포함 4일? 아 풀자마자 적는거라 기분이 너무 좋다 ㅎㅎ

from collections import defaultdict

def solution(n, lighthouse):
    path_dict = defaultdict(list)

    for a, b in lighthouse:
        path_dict[a].append(b)
        path_dict[b].append(a)

    result = 0
    while path_dict:
        for end_node, side_node in path_dict.copy().items():
            if len(side_node) == 1 and end_node in path_dict:
                temp = side_node[0]
                del_node_list = [x for x in path_dict[temp]]
                del path_dict[temp]
                for i in del_node_list:
                    path_dict[i].remove(temp)
                    if not path_dict[i]:
                        del path_dict[i]
                result += 1

    return result

• 해설

1. path_dict로 양방향 길을 만들어 준다.
2. len(side_node) == 1 -> 해당 if 문에서 끝 노드가 걸릴것이고 해당 노드 반대편에 불을 켜준 후 (result += 1) 원본 dict에서 제거
3. 양방향으로 만들어 주었으므로 불 켜진 반대편 노드들에서 켜진 방향으로 길을 remove 후 값이 없으면 해당 노드도 dict에서 제거

🧲 문제 후기

🔍 답을 볼까 하는 생각도 있었지만 애초에 답도 없었고 프로그래머스의 다른사람 풀이 보기 기능은 점수를 너무 많이 가져가기 때문에 누를 엄두가 나지 않았다.

문제를 푼 후 다른 사람들 풀이를 보니 dfs로 많이 푼 것 같다.
나도 dfs로 다시 풀어봐야겠다.

이 문제 잡고있느라 뭐 아무것도 못했다 ;
오늘 만족스럽게 끝!