문제 링크
< 문제 이해 >
- 네트워크 - 컴퓨터들이 연결된 형태
- n = 컴퓨터 개수 ( 0 ~ 200 )
- computers = 각 컴퓨터마다 다른 컴퓨터와의 연결에 대한 정보가 담긴 2차원 배열
- 0~n-1로 표현
- computers[i][j] : i번 컴퓨터와 j번 컴퓨터가 연결
- computers[i][i] = 1 : 항상 고정
- return : 네크워크 개수
< 문제 핵심 >
-
dfs, bfs 모두 가능
- 저는 dfs 선택
-
각 노드(컴퓨터)를 방문했는지 파악
-
방문한 경우
- 기준노드 설정
- dfs 함수를 만들어서 기준노드에서 쭉 연결된 노드들을 탐색 후
- 기준노드로부터 연결된 모든 노드들로 만들어진 네트워크를 하나 찾았으므로 cnt+=1
- 이 과정을 모든 노드들이 방문될때까지 반복
-
방문 안한 경우
continue
-
-
dfs 함수
- 기준노드인 자기자신은 computers[i][i] = 1라 문제에 제시가 되어있음으로 방문처리를 필수로 해줘야합니다.
- 인접 노드들을 탐색하여 존재하고 처음 방문한 상태라면 다시 재귀를 이용해 인접 노드들의 인접 노드가 있는지를 꼬리를 물어 확인해야 합니다.
- 끝까지 탐색 후 빠져나갑니다.
-
네트워크 개수
- 최종 cnt를 마지막에 리턴
< 문제 아이디어 >
- 없음
< 코드 >
1. dfs 사용
def dfs(n,computers,visited,v) :
visited[v] = True
for e in range(n) :
if computers[v][e] == 1 and visited[e] == False :
dfs(n,computers,visited,e)
def solution(n, computers):
visited = [False]*n
cnt = 0
while False in visited :
for v in range(n) :
if visited[v] == True :
continue
elif visited[v] == False:
dfs(n,computers,visited,v)
cnt += 1
return cnt
print(solution(3,[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))
print(solution(3,[[1, 1, 0], [1, 1, 1], [0, 1, 1]]))< 구현 방식 >
( 사용한 메소드, 라이브러리 등 원리 )
1. dfs 사용
1. visited
- 각 노드들이 방문했는지 안했는지를 파악하기 위함
- 처음에 모든 노드들을 False인 상태로 초기화
- while 반복문을 이용하여 모든 노드들을 방문할때까지 탐색
2. dfs 함수
- 방문하지 않았던 노드를 기준노드로 잡고 그 기준노드의 상태를 True로 변경 후, 인접 노드들의 존재 여부를 파악
- computers[v][e] == 1 and visited[e] == False를 한 이유는 computers[v][e] == 1 이 상태가 인접 노드가 있다는 의미고, visited[e] == False 이것은 기준노드인 나를 제외하기 위함입니다.
- 계속 기준노드에서 인접노드들을 찾아 한 우물만 파는 것이므로 dfs 방식이라고 말할 수 있습니다. ( 재귀를 사용 )
3. cnt 더하기
- 모든 과정이 끝난 후 하나의 네트워크가 생성되는 것이므로 cnt+=1 해줍니다.
< 결과 >
1. dfs 사용
:D