코테 스터디: Week 3 01

이슬비·2022년 5월 10일

Coding Test

목록 보기

3/6

너무... 어렵다... level3... 나는 한 level -1정도 되는 것 같은데... dfs/bfs 개념을 모르니까 그냥 중첩 반복문으로 풀었는데 테스트 세트 3개 맞고 나머지 다 틀렸다 ^^

1. 문제

문제 읽으면서 아 쉽네 ~ 이랬다가 ^^... 탈탈 털려버렸다.
https://programmers.co.kr/learn/courses/30/lessons/43162

2. 풀이

1. 내 풀이: 실패

def solution(n, computers):
    answer = n
    for i in range(len(computers)-1):
        for j in range(i+1, len(computers[i])):
            if computers[i][j] == 1:
                answer -= 1
    return answer

print(solution(3, [[1,1,0],[1,1,0],[0,0,1]]))

일단 풀이를 보면, 일단 computer의 개수에서 1을 뺀 만큼 첫 번째 for문을 돌려준다. 왜 1을 빼냐면, 일단 이 테스트 케이스 기준으로 첫 번째, 두 번째에서 연결됐는지 판단이 되면 마지막은 자동적으로 정해지기 때문이다.

그 상태에서 i+1부터 computer[i]까지 두 번째 for문을 돌려준다. i+1인 이유는 i 이전의 값들은 그전 컴퓨터에서 다 판단이 되기 때문에 i+1부터 시작했다. 여기서 computer[i][j]가 1이면 연결되었다는 뜻, 즉 네트워크가 하나 줄어드니까 1을 빼준다.

예시 테스트 케이스에서는 완벽하게 작동하지만... 정답은 아니었다.

2. 다른 풀이

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1 #DFS로 최대한 컴퓨터들을 방문하고 빠져나오게 되면 그것이 하나의 네트워크.
    return answer

def DFS(n, computers, com, visited):
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1: #연결된 컴퓨터
            if visited[connect] == False:
                DFS(n, computers, connect, visited)

그래서 결국 정답을 봤다 ^^ 이 문제는 dfs/bfs 문제여서 대부분의 풀이가 dfs 혹은 bfs 함수를 정의해서 풀었다. 출처는 아래의 블로그이다.
(출처: https://velog.io/@timointhebush/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-DFS-BFS-Python)

그럼 한 번... 분석해보자. 일단 solution 함수부터!

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1 #DFS로 최대한 컴퓨터들을 방문하고 빠져나오게 되면 그것이 하나의 네트워크.
    return answer

일단 answer은 0으로, visited, 즉 연결됨을 판단했는지를 알 수 있도록 컴퓨터의 수만큼 False를 담고 있는 리스트를 만들어준다.

그리고 컴퓨터의 수만큼 for문을 돌린다. 이때 visited[com] == False이면, DFS 함수를 이용해 네트워크를 판단한다. 주석으로도 달려있듯이 DFS로 최대한 많은 컴퓨터들을 방문하고 빠져나오면 이제 그것이 하나의 네트워크가 되는 것이다!!!

그러한 과정을 각 컴퓨터마다 반복을 하고 answer을 반환해준다.

다음은 대망의 DFS.

def DFS(n, computers, com, visited):
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1: #연결된 컴퓨터
            if visited[connect] == False:
                DFS(n, computers, connect, visited)

일단 해당 컴퓨터를 한 번 방문했으니 해당 visited 값을 True로 반환해준다. 만약 이런 과정 없이 전부 다 DFS를 돌리면 오류가 날 뿐더러 시간 초과가 나지 않을까 생각한다.

그 후에 컴퓨터의 수만큼 for문을 돌려준다. connect도 com도 모두 숫자(컴퓨터)이다. 만약 두 값이 같은 게 아니고 (같은 컴퓨터가 아니고) computers[com][connect]가 1이면, 즉 컴퓨터가 연결되어 있으면 Visted[connect]가 False일 때 DFS를 한 번 더 돈다.

이 말은 한 번에 최대한 많은 컴퓨터를 탐색하기 위해 1번과 2번 컴퓨터가 연결되어 있으면(현재 1번 컴퓨터 기준으로 탐색 시) 또 그 속에서 2번 컴퓨터가 또 어떤 다른 컴퓨터와 연결되어있는지를 판단해주는 것이다.

DFS도 재귀함수 형식으로 해야하는구나 !!! 를 알게 되었다.