• [코테 연습] 네트워크 Python

    2020. 6. 16. 17:14

    by. 위지원

    문제 설명

    네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

    컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

    제한사항

    • 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
    • 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
    • i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
    • computer[i][i]는 항상 1입니다.

    이웃이 없으면 visted를 비우고 다음 노드 탐색

     

     

    처음엔 아래와 같이 작성했다.  방문한 노드는 그래프상에서 지워버리고 재귀가 끝났다면 한 네트워크가 생성된 것이니까 +1

     

    테스트 케이스를 무려 9개나 돌렸다 ....

    def cal(dic, idx, invited):
    value = dic[idx]
    invited.append(idx)
    del dic[idx]
    print("current node:",idx)
    print("invited:", invited)
    print("queue:", value,"\n")
    if dic:
    value = list(set(value) - set(invited))
    for v in value:
    cal(dic, v, invited)
    return dic
    def solution(n, computers):
    cnt = 0
    if n == 1:
    return 1
    else:
    dic = {}
    for comId in range(len(computers)): # comId:선택된 노드
    idx = [i for i, ele in enumerate(computers[comId]) if ele == 1]
    if len(idx) == n:
    return 1
    if len(idx) == 1:
    cnt += 1
    else:
    dic[comId] = idx
    if dic:
    flag = True
    while flag:
    cnt += 1
    dic = cal(dic, list(dic.keys())[0], [])
    if not dic:
    flag = False
    return cnt

     

    테스트 1
    입력값 3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
    기댓값 2
    실행 결과 테스트를 통과하였습니다.
    테스트 2
    입력값 3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 3
    입력값 4, [[1, 0, 0, 1], [0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1]]
    기댓값 3
    실행 결과 테스트를 통과하였습니다.
    테스트 4
    입력값 9, [[1, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 0, 0, 0, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0, 1]]
    기댓값 4
    실행 결과 테스트를 통과하였습니다.
    테스트 5
    입력값 9, [[1, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 1]]
    기댓값 9
    실행 결과 테스트를 통과하였습니다.
    테스트 6
    입력값 4, [[1, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [1, 1, 0, 1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 7
    입력값 4, [[1, 1, 1, 1], [1, 1, 1, 0], [1, 1, 1, 0], [1, 0, 0, 1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 8
    입력값 〉 1, [[1]]
    기댓값 〉 1
    실행 결과 〉 테스트를 통과하였습니다.
    테스트 9
    입력값 〉 3, [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    기댓값 〉 3
    실행 결과 〉 테스트를 통과하였습니다.

     

    오홋 ^>^오호홋 9개나 통과했으니 그렇다면 이번 코딩은 무난히 통과하겠구마이 이정도면

     

    테스트 1 통과 (0.05ms, 10.8MB)
    테스트 2 통과 (0.05ms, 10.8MB)
    테스트 3 〉 실패 (런타임 에러)
    테스트 4 〉 실패 (런타임 에러)
    테스트 5 통과 (0.04ms, 10.9MB)
    테스트 6 〉 실패 (런타임 에러)
    테스트 7 〉 실패 (런타임 에러)
    테스트 8 〉 실패 (런타임 에러)
    테스트 9 〉 실패 (런타임 에러)
    테스트 10 〉 실패 (런타임 에러)
    테스트 11 〉 실패 (런타임 에러)
    테스트 12 〉 실패 (런타임 에러)
    테스트 13 〉 실패 (런타임 에러)

    응 아니야~ 런타임이면 뭔가 idx 찾는데에 문제가 생기는 것같은데 ,,

     

    남의 코드를 보고 하는것은 이제 그만두고 싶어... 코드를 바꿔봤다. queue 즉 위에서 value였던 값을 가지고 돌아다니게 해보자. 그리고 디버깅하다보니까 for v in value 코드가 쓸때없이 반복되고있었기때문에 for문도 제거했다. 이 for문에서 value의 v를 가지고 하니까 이미 dic에선 없어진 값인데 그걸 접근하려해서 런타임 에러가 뜨는 것 같았다. 

    def cal(dic, idx, invited, queue):
    print(dic)
    print("idx", idx)
    queue = dic[idx]
    invited.append(idx)
    del dic[idx]
    print("current node:", idx)
    print("invited:", invited)
    queue = list(set(queue) - set(invited))
    print("queue:", queue, "\n")
    if not queue:
    return dic
    else:
    cal(dic, queue[0], invited, queue)
    def solution(n, computers):
    cnt = 0
    if n == 1:
    return 1
    else:
    dic = {}
    for comId in range(len(computers)): # comId:선택된 노드
    idxs = [i for i, ele in enumerate(computers[comId]) if ele == 1]
    if len(idxs) == n:
    return 1
    if len(idxs) == 1:
    cnt += 1
    else:
    dic[comId] = idxs
    if dic:
    flag = True
    while flag:
    cnt += 1
    dic = cal(dic, list(dic.keys())[0], [], [])
    if not dic:
    flag = False
    return cnt
    테스트 1 통과 (0.07ms, 10.8MB)
    테스트 2 통과 (0.07ms, 10.8MB)
    테스트 3 통과 (0.11ms, 10.8MB)
    테스트 4 〉 실패 (0.28ms, 10.8MB)
    테스트 5 통과 (0.03ms, 10.8MB)
    테스트 6 통과 (1.26ms, 10.8MB)
    테스트 7 〉 실패 (0.25ms, 10.8MB)
    테스트 8 통과 (0.62ms, 10.9MB)
    테스트 9 통과 (0.16ms, 10.8MB)
    테스트 10 통과 (0.74ms, 10.8MB)
    테스트 11 통과 (3.71ms, 14MB)
    테스트 12 통과 (2.96ms, 12.8MB)
    테스트 13 통과 (0.34ms, 11MB)

     

    와 2개 빼고 통과했다.

     

    근데 이번엔 내가 임의로 작성한 테스트 케이스를 통과 못한다.

     

    테스트 5
    입력값 9, [[1, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 0, 0, 0, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0, 1]]
    기댓값 4
    실행 결과 실행한 결괏값 2이(가) 기댓값 4와(과) 다릅니다.

    차라리 이게 낫지.. 후,, 디버깅하러 간다

     

     

    얘가 안된다. 

     

    invited를 가지고 다니지 말고 전역변수로 설정했다.

    a-b-i

    연결됨을 한번 확인 한다음에

    e가 a랑 연결된것을 나중에 확인하게 되어서 카운트를 한번 더 해버린다..

    음,, 좋지않아,, 

     

    다시 invited를 가지고 다니는걸로 ,,

    아 그럼 방문노드를 value로 갖는 경우에 모든 dic에서 제거해버려야겠다. 

     

    그리고 본인과 본인은 항상 1이기때문에 이 부분을 추가로 고려안해도되게 코드를 변경하였다.

    cnt=0
    def cal(dic, idx, invited, nodeNum):
    invited.append(idx)
    queue = list(set(dic[idx]) - set(invited))
    if len(invited) == nodeNum:
    return
    del dic[idx]
    for k, v in dic.items(): #value에 방문한 노드를 가지고 있으면 삭제
    if idx in v:
    v.remove(idx)
    if len(dic[queue[0]]) == 0:
    global cnt
    cnt += 1
    else:
    cal(dic, queue[0], invited, nodeNum)
    def solution(n, computers):
    global cnt
    if n == 1:
    return 1
    else:
    dic = {}
    for comId in range(len(computers)): # comId:선택된 노드
    idxs = [i for i, ele in enumerate(computers[comId]) if ele == 1 and comId != i] # 자기 자신은 이웃노드에서 제외
    if len(idxs) == n-1:
    return 1
    if len(idxs) == 0:
    cnt += 1
    else:
    dic[comId] = idxs
    if dic:
    flag = True
    while flag:
    cal(dic, list(dic.keys())[0], [], n) #첫번째 노드부터 탐색
    dic = dic = {k: v for k, v in dic.items() if len(v) >0}
    if not dic:
    flag = False
    return cnt

     

    테스트 1
    입력값 3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
    기댓값 2
    실행 결과 테스트를 통과하였습니다.
    테스트 2
    입력값 3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 3
    입력값 9, [[1, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 0, 0, 0, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0, 1]]
    기댓값 4
    실행 결과 테스트를 통과하였습니다.
    테스트 4
    입력값 4, [[1, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [1, 1, 0, 1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 5
    입력값 4, [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]]
    기댓값 3
    실행 결과 테스트를 통과하였습니다.
    테스트 6
    입력값 3, [[1, 0, 0], [0, 1, 1], [0, 1, 1]]
    기댓값 2
    실행 결과 테스트를 통과하였습니다.
    테스트 7
    입력값 6, [[1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 1, 1]]
    기댓값 4
    실행 결과 테스트를 통과하였습니다.
    테스트 8
    입력값 5, [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]]
    기댓값 3
    실행 결과 테스트를 통과하였습니다.
    테스트 9
    입력값 4, [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1], [0, 0, 1, 1]]
    기댓값 2
    실행 결과 테스트를 통과하였습니다.
    테스트 10
    입력값 4, [[1, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [1, 1, 0, 1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 11
    입력값 4, [[1, 1, 1, 1], [1, 1, 1, 0], [1, 1, 1, 0], [1, 0, 0, 1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 12
    입력값 1, [[1]]
    기댓값 1
    실행 결과 테스트를 통과하였습니다.
    테스트 13
    입력값 3, [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    기댓값 3
    실행 결과 테스트를 통과하였습니다.

    테스트 결과 (~˘▾˘)~

    13개 중 13개 성공

     

    테스트 1 통과 (0.06ms, 10.7MB)
    테스트 2 통과 (0.05ms, 10.7MB)
    테스트 3 〉 실패 (0.31ms, 10.8MB)
    테스트 4 〉 실패 (0.23ms, 10.7MB)
    테스트 5 통과 (0.04ms, 10.7MB)
    테스트 6 〉 실패 (0.51ms, 10.8MB)
    테스트 7 통과 (0.07ms, 10.9MB)
    테스트 8 〉 실패 (0.38ms, 10.9MB)
    테스트 9 〉 실패 (0.32ms, 10.9MB)
    테스트 10 〉 실패 (0.31ms, 10.8MB)
    테스트 11 〉 실패 (1.19ms, 14MB)
    테스트 12 〉 실패 (0.92ms, 12.8MB)
    테스트 13 〉 실패 (0.52ms, 11MB)

     

    gg.. 그래도 다른 코테할때보다 혼자 해보려고 노력 오랫동안한거 칭찬해,,

     

    결국 남의 코드를 봤다.... 

    https://mungto.tistory.com/52

     

    네트워크 C++(dfs/bfs)[프로그래머스]

    ※ 저의 풀이가 무조건적인 정답은 아닙니다. 다른 코드가 좀더 효율적이고 좋을 수 있습니다. 다른사람들의 풀이는 언제나 참고만 하시기 바랍니다. 문제 주소입니다. https://programmers.co.kr/learn/c

    mungto.tistory.com

    def dfs(computers, n):
    if not computers[n][n]:
    return False
    computers[n][n] = 0
    for i in range(len(computers)):
    if computers[n][i]:
    dfs(computers, i)
    return True
    def solution(n, computers):
    answer = 0
    for i in range(n):
    if computers[i][i] and dfs(computers, i):
    answer += 1
    return answer

    어찌 이렇게 천재같이 푸는거지

     

    1. dfs를 이용하여 true false를 이용한다.. 

    2. invited 배열따위는 필요없다. 바로 0으로 set해서 방문을 표시했다.

    3. dfs 재귀를 통해서 모든 재귀가 끝나는 경우 true를 반환해서 computer[i][i]일 때의 경로가 끝났음을 알리고 answer를 증가시켰다.. 와,, , 워오이ㅏ우,,,

    ㅠㅠ......

     

    이문제를 union-find라는 알고리즘을 통해 풀 수 있다고 한다.  union-find는 처음 들어보는 알고리즘인데, 

    시간이 되면 공부해봐야겠다.

     

    https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

     

    [알고리즘] Union-Find 알고리즘 - Heee's Development Blog

    Step by step goes a long way.

    gmlwjd9405.github.io

     

     

    profile
    위지원

    데이터 엔지니어로 근무 중에 있으며 데이터와 관련된 일을 모두 좋아합니다!. 특히 ETL 부분에 관심이 가장 크며 데이터를 빛이나게 가공하는 일을 좋아한답니다 ✨

    '2020년 > 코테' 카테고리의 다른 글