전력망을 둘로 나누기 [프로그래머스]

문제 넋두리

나는 문제를 set으로 풀려고 했다.

계획은 이랬다.

1. 특정 node(ex.wires[0][0]) 를 left set에 넣는다.
2. wires중 하나를 제거한다.
3. 잘라진(하나가 제거된) wires 배열을 루프돌면서 left set에 wire[0], wire[1]이 존재한다면 left에 추가 한다.
4. 루프가 끝난시점에 left에 담긴 node 와 그렇지 않은 node set 간의 갯수 차이를 리턴
5. 2-4번 (n-1)번 반복 하면서 차이가 제일 작은 값을 answer로 저장

그런데 자꾸 틀렸다. 틀린 이유를 못찾았는데

예상하기로는 left set에 담기는 조건이

wire[0] 이나, wire[1]이 left set에 존재하는지 여부 였는데,

(⇒ if wire[0] in left or wire[1] in left:)

만약 루프 중간에 (현재 left에는 존재하지 않지만 모든 노드를 연결해보니 left에 포함되는 선) 이 존재한다면

저 3번 로직은 fail이 될 것이다.

그래서 내가 취한 방법은 wires를 소팅하는 방법이였다.

(⇒ wires = sorted(wires, key=lambda x : x[0]))

이렇게 하면 node가 작은순으로 정렬이 되고 놓치는게 없을 줄 알았다.

(문제 조건에서도 "1 ≤ v1 < v2 ≤ n 입니다." 라고 나와있다.)

그런데 번번히 50점을 못넘었다. 놓치는게 있다는 말이다. 예외 사항이 있나 생각해보지만 난 잘 모르겠다.

 

위와 같이 v1 < v2 이면서, 소팅이 완료된 경우 놓칠 수 없다. (만약 [4,5]가 [2,5] 보다 앞에 있다면 놓칠수 있다)

뭔지는 모르겠지만 답이 안나온다면 전부 갈아 엎고 시작해야한다.

그래서 방법을 바꿨다.

1. 특정 node(ex.wires[0][0]) 를 left list에 넣는다.
2. wires중 하나를 제거한다.
3. 방문 표식 리스트를 만든다. visited = [0,0,0,,,,]
4. left list를 queue 처럼 사용하면서 bfs 형식으로 left list에 추가한다. 동시에 방문한 곳의 경우 visited를 채운다 (visited[node_num] = 1)
5. left list 의 첫번째를 계속 pop하면서 visited를 채운뒤 left list가 비워지면 반복종료
6. visited 0/1 로 나누어 개수차이를 비교한다
7. 2-6번을 각 다른 wire를 제거하면 (n-1)번 반복한다. 차이가 제일 적은 값을 answer로 저장

코드

def solution(n, wires):
    answer = 9999
    
    left_node = []
        
    for index in range(n):
        left_node.append(wires[0][0])
        test_wires = wires[0:index] + wires[index+1:]
        visited = []
        for index in range(n):
            visited.append(0)
            
        while len(left_node) != 0:
            node = left_node.pop(0)
            visited[node-1] = 1
            for wire in test_wires:
                if node in wire:
                    if visited[wire[0]-1] != 0:
                        pass
                    else:
                        visited[wire[0]-1] = 1
                        left_node.append(wire[0])
                    if visited[wire[1]-1] != 0:
                        pass
                    else:
                        visited[wire[1]-1] = 1
                        left_node.append(wire[1])
        
        left,right = [], []
        for i,visit in enumerate(visited):
            if visit == 1:
                left.append(i+1)
            else:
                right.append(i+1)
        
        if answer > abs(len(left)-len(right)):
            answer = abs(len(left)-len(right))
    return answer

 

을 코드로 만들면 저렇게 된다.

휴 아직 멀었구만...ㅋㅋ

 

문제는 여기

https://programmers.co.kr/learn/courses/30/lessons/86971#

코딩테스트 연습 - 9주차