[코테 연습] 네트워크 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입니다.

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

저작자표시

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

[코테] 여행 경로 Python (1)	2020.06.19
[코테 연습] 단어 변환 Python (0)	2020.06.18
[코테 연습] 타겟 넘버 Python (0)	2020.06.09
[코테 연습] 포도주 시식 Python (0)	2020.05.29
[코테 연습] 정수 삼각형 Python (0)	2020.05.28

잠깐만요~! 읽으신김에 이런 글들은 어떠세요? 👀

맨 위로

데이터를 사랑하고 궁금해하는 기록쟁이입니다! 😉 Super Data Engineer가 되는 그날까지🏃‍♀️ 화이팅!

[코테 연습] 네트워크 Python

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

티스토리툴바

티스토리툴바