23.03.08 파이썬 코딩 퀴즈#188 네트워크(프로그래머스 스쿨)

이번 문제는 네트워크 문제이다.

전달받은 computers 배열을 이해하려면 제한 사항을 잘 봐야 한다.

computers[i] 는 현재 i 컴퓨터가 연결된 정보를 보여주며, computers[i][i] 는 자기 자신이므로 언제나 1이다.

그리고 A <-> B 가 연결되어 있고, B<-> C 가 연결되어 있다면, 하나의 네트워크로 간주한다.

 

위 예시는 너무 간단하기 때문에 컴퓨터가 4대인 경우를 한번 살펴보자.

computers = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1,]] 이라고 가정하고 편하게 A,B,C,D 라고 생각해보자

A 컴퓨터의 경우 자기 자신을 제외한 B 와 연결되어 있다.

B 컴퓨터의 경우 자기 자신을 제외한 A 에 연결되어 있다.

C 컴퓨터는 D 에 연결되어 있으며 D 컴퓨터는 오직 C 에만 연결되어 있다.

따라서 이 경우라면 A와B, C와D가 각각의 네트워크를 구성하게 된다. (return 2)

 

전형적인 DFS, BFS 문제이다.

딱히 부연설명이 필요할까... 

한가지 주의할 점은 dfs()를 돌고 난 이후 탐색할 컴퓨터를 지정하는 것이다.

이때에는 visited 를 다시 확인하여 아직 확인하지 않은 컴퓨터를 찾아 그 index 값을 다시 사용해야 한다. (break로 한대만 찾아도 상관없다)