-
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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 dicdef solution(n, computers):cnt = 0if n == 1:return 1else: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 1if len(idx) == 1:cnt += 1else:dic[comId] = idxif dic:flag = Truewhile flag:cnt += 1dic = cal(dic, list(dic.keys())[0], [])if not dic:flag = Falsereturn 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 dicelse:cal(dic, queue[0], invited, queue)def solution(n, computers):cnt = 0if n == 1:return 1else: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 1if len(idxs) == 1:cnt += 1else:dic[comId] = idxsif dic:flag = Truewhile flag:cnt += 1dic = cal(dic, list(dic.keys())[0], [], [])if not dic:flag = Falsereturn 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=0def cal(dic, idx, invited, nodeNum):invited.append(idx)queue = list(set(dic[idx]) - set(invited))if len(invited) == nodeNum:returndel dic[idx]for k, v in dic.items(): #value에 방문한 노드를 가지고 있으면 삭제if idx in v:v.remove(idx)if len(dic[queue[0]]) == 0:global cntcnt += 1else:cal(dic, queue[0], invited, nodeNum)def solution(n, computers):global cntif n == 1:return 1else: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 1if len(idxs) == 0:cnt += 1else:dic[comId] = idxsif dic:flag = Truewhile 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 = Falsereturn 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.. 그래도 다른 코테할때보다 혼자 해보려고 노력 오랫동안한거 칭찬해,,
결국 남의 코드를 봤다....
def dfs(computers, n):if not computers[n][n]:return Falsecomputers[n][n] = 0for i in range(len(computers)):if computers[n][i]:dfs(computers, i)return Truedef solution(n, computers):answer = 0for i in range(n):if computers[i][i] and dfs(computers, i):answer += 1return 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
위지원데이터 엔지니어로 근무 중에 있으며 데이터와 관련된 일을 모두 좋아합니다!. 특히 ETL 부분에 관심이 가장 크며 데이터를 빛이나게 가공하는 일을 좋아한답니다 ✨
'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