프로그래머스 네트워크 문제 풀이/코드, 파이썬, BFS! LV3같지 않은 LV3문제

전체 코드가 궁금한 분은 아래 링크 눌러주세요 ㅎㅅㅎ

GitHub - Rhyankwon/algorithms

 

 

문제 설명 ㄱㄱ

코딩테스트 연습 - 네트워크

컴터들이 여러개가 있는데.. 연결 돼있는것도있고 안돼있는 것도 있다고 한다. 컴터가 A, B, C가 있을때 A-B연결돼있고 B-C연결돼있으면 이걸 하나의 네트워크라고 보는데, 이 때 주어진 컴퓨터들의 연결상태를 보고 총 몇개의 네트워크가 있는지 찾으면 되는 문제이다.

 

 

풀이 ㄱㄱ

1. for문을 통해서 모든 컴퓨터를 확인한다.

2. 한번 확인한 컴퓨터는 다시 확인 안하도록 체크

3. 각 컴퓨터와 연결된 컴퓨터들을 stack에 넣고 확인표시.

3-1. 해당 stack에 있는 모든 컴퓨터들이 연결돼있는 컴퓨터를 다시 확인

4. stack에 더이상 남은 컴퓨터가 없으면 1번으로 가서, 아직 확인 안한 컴퓨터가 있는 경우 해당 컴퓨터부터 다시 확인

5. 1번 과정(다른 컴퓨터에 연결되서 확인하는게 아닌 처음 컴퓨터를 선택하는 경우)마다 네트워크수 +1

 

    for i in range(n):
        if visited[i] == 1: #이미 방문한 경우 패스
            continue
        visited[i] = 1
        answer += 1 #아니면 네트워크 1개추가
        
        stack = collections.deque()
        stack.append(i)
        
        while stack:
            cur = stack.popleft()
            for j, com in enumerate(computers[cur]):
                if com == 1 and visited[j] == 0:
                    visited[j] = 1
                    stack.append(j)

이런 느낌.. 이 아니라 사실상 거의 전체코드를 갖다놓은거라.. ㅋㅋㅋㅋ이렇게 풀면 된다. 집중만 잘 하면 쉽게 풀 수 있는 bfs문제인듯?

 

 

---------------------------잡설---------------------------

 

나는 쉽게 풀었지만 왜 LV3인지는 알겠음. 이런 문제가 흔하게 있는데, 그 중 가장 흔한건 아무래도 블럭들이 주어질 때 그 색깔별로 구분해서 (1, 2, 3.. 이렇게 숫자가 써있는 경우) 총 몇개의 그룹인지 찾거나 그런거..이다. 그런것들이 LV2라면 이건 솔직히 LV3감은 되긴한다. 다만 나는 원래 프로그래머스LV3를 잘 푸는 편이 아닌데 이건 30분만에 푼듯?.. 이런거 제발 많이 나오면 좋겠다 실제 코테때 ,,