[프로그래머스 등대][Lv.3][Python][BFS]

나는 병신이다

N 개의 점과 N-1개의 선분, i->j까지 가는 모든 루트가 존재한다면 이건 Tree의 형태로밖에 나오지 않는다

 

그래서 나는 트리의 말단에서 그 위로 뻗어나오는 부모노드의 불을 켜주고, 그 부모노드의 연결된 길을 지워준다. 

또 말단인부분을 반복반복....하면 답이 나온다

 

나는 처음에 가능한 visit을 한 루트를 지워가며 확인을 했는데, 이걸 리스트로 했다. 

이렇게 하면 n이 100000인데 최악의경우 (100000+1)*100000/2만큼이 걸린다.

지우고 땡기고 지우고 땡기고

 

그래서 Road를 저장할땐 set을 사용하고 연결된 개수에 대한 dict를 만들고 , 연결점이 1개인것들만 큐에 추가하는 방식으로 바꿧는데 visit을 안지우고 테스트를 했다

 

한 5번 제출해도 계속 시간초과가 나길래 내가 생각을 잘못했나 이게 트리가 아닌가 시간복잡도를 잘못알고있나 라이브러리부터 다 살펴보고 해도 도저히 결론이 안나서 아는 형한테 물어도 보고 맞왜틀을 오지게 시전하고 있었는데 처음부터 다시 봐야겠다하고 코드를 한줄한줄 다시 읽어보는데 있으면 안되는 코드가 있더라

? 하면서 코드를 지우고 제출하니까 통과했다

 

한번 실수를 한건 왜이렇게 잘 안보이는걸까

물론 이것도 실력이고 경험이겠지만 진짜 자괴감이 든다

 

제기랄

#알려주려고 푼 문젠데 import를 사용하지 말아달라고 해서 안씀. 본래풀땐 road, wait에 defaultdict, deque를 사용

def solution(n, lighthouse):
    arr = [0 for _ in range(n+1)]            #연결점 개수 관리
    road = [set() for _ in range(n+1)]       #선분 관리
    for i, j in lighthouse:
        road[i].add(j)
        road[j].add(i)
        arr[i] += 1
        arr[j] += 1
    answer = 0
    wait = []
    for i in range(1, n+1):                  #말단노드를 wait에 추가
        if arr[i] == 1:                     
            wait.append(i)
    while wait:                              #wait리스트를 큐처럼 사용하며 말단노드의 부모노드 불 켜주기
        i = wait.pop()
        if arr[i] == 1:                      #말단노드여도 다른것이 켜지면서 0이 될 수 있어 한번 체크
            light = tuple(road[i])[0]
            answer += 1
            for k in road[light]:            
                arr[k] -= 1                  #연결점 -1 해주기
                road[k].remove(light)        #킨 전등은 Road에서 제거해주기
                if arr[k] == 1:              #말단노드라면 wait에 추가
                    wait.append(k)         
            arr[light] = 0                   #킨 노드는 제거
    return answer