[TIL_Carrotww] 49 - 22/11/10

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 등대
프로젝트 끝나고 저번에 못 풀었던 문제 풀어보려고 하는데 두 가지 방법으로 접근했는데 안풀린다...
찾아봤더니 어려운 문제기는 하더라 (친구가 골랐는데 셋 다 못풀정도의 파멸적인 난이도)
일단 두 방법 모두 기록해 보려고 한다 ㅠ
못풀었지만...

• 1번 풀이

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)

    path_list = sorted(path_dict.items(), key=lambda x:len(x[1]))

    path_list = [[x[0], x[1], len(x[1])] for x in path_list]

    cnt = 0

    while path_list:
        pop_n, pop_path, pop_cnt = path_list.pop()
        cnt += 1
        for x in range(len(path_list)):
            if path_list[x][2] != 0 and pop_n in path_list[x][1]:
                path_list[x][2] -= 1

        if sum([x[2] for x in path_list]) == 0:
            break

        path_list.sort(key=lambda x:x[2])

    return cnt

위 사진과 같이 각 노드에서 많은 기준으로 정렬을 하면
빨간색 부분이 가장 먼저 빠지고, 그 다음 노드들을 정렬,
파란색 -> 검정색 순으로 빠지며 그 횟수를 return 한다.
하지만 코드로 구현하면 sort를 게속 해주게 되고 시간 복잡도에서 탈락한다. 물론 코드도 지금 완벽히 구현한 것은 아니다...

• 2번 풀이

from collections import defaultdict, deque

def solution(n, lighthouse):
    # start point를 잡는다 - 맨 끝에 있는 노드
    path = defaultdict(list)
    for a, b in lighthouse:
        path[a].append(b)
        path[b].append(a)

    light_list, visited = set(), set()

    start = -1
    for key, val in path.items():
        if len(val) == 1:
            start = key
            light_list.add(val[0])
            break

    queue = deque([start])

    while queue:
        temp = queue.popleft()
        visited.add(temp)
        state = True
        for i in path[temp]:
            if i in light_list:
                state = False
        for i in path[temp]:
            if i in visited:
                continue
            queue.append(i)
        if state and temp not in light_list:
            light_list.add(temp)

    return light_list

BFS 를 생각하여 양 옆 노드가 방문 했는지를 체크, 양 옆 노드가 불이 켜져있는지를 체크하며 불을 킨다.
당연히 안된다. 테스트케이스 1에서 붙어있는 노드가 불이 켜져있기 때문... 여러가지를 해보려다가 못풀었다.

• 잡담
  BFS로 푸는것이 맞는 것 같기는 한데 아직 아이디어를 찾지 못했다... 정답자가 71명이라 검색해도 나오지 않는것이 답답하다..
  내일 다시 풀어봐야겠다.