[python] 백준 2606번 "바이러스"(DFS/BFS)

문제

첫 번째 해결방법

- BFS 사용하기

먼저 1번 컴퓨터와 연결되어 있는지 여부를 좀 더 쉽게 파악하기 위해 그래프에 연결된 간선의 값들만 적지 않고 연결되지 않았을 때는 0, 연결되어 있는 경우 1을 입력한 후, 일반적인 bfs의 방법을 사용하여 해결 

from collections import deque
n = int(input())
m = int(input())
graph = [[0] * (n + 1) for _ in range(n + 1)]
visited = [0] * (n + 1)
for i in range(m):
    x,y = map(int,input().split())
    graph[x][y] = 1
    graph[y][x] = 1

def bfs(start_node, graph, visited):
    queue = deque([start_node])
    visited[start_node] = 1
    cnt = 0
    while queue:
        v = queue.popleft()
        for i in range(len(graph[v])):
            if not visited[i] and graph[v][i]:
                queue.append(i)
                visited[i] = 1
                cnt += 1

    return cnt
print(bfs(1, graph, visited))
print(visited)

1과 연결된 컴퓨터만 확인하면 되므로, 그래프를 전체 탐색할 필요 없이 그래프의 길이만큼만 탐색하여, 1과 연결되어있는지의 여부를 확인하여, 아직 방문하지 않았고, 1과 연결되어있다면, 큐에 붙여주고, 방문한 노드에도 1을 넣어주었다. 그 후, cnt 개수를 늘려서 총 갯수를 센 후 마지막에 cnt만 반환하도록 작성하였다.

 

from collections import deque
n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

for i in range(m):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def bfs(graph, v, visited):
    queue = deque([v])
    visited[v] = 1
    while queue:
        start = queue.popleft()
        for i in sorted(graph[start]):
            if not visited[i]:
                queue.append(i)
                visited[i] = 1
    return sum(visited)
print(bfs(graph,1,visited) - 1)

좀 더 단순하게 풀 수 있을 것 같아 일반적인 bfs와 같은 코드를 사용한 방법을 고민해보았다.

결국 탐색을 하게 되면 연결되어있는 노드들을 모두 알 수 있으므로 일반적인 코드를 사용하여 visited에 저장된 값들을 모두 더해 1을 빼주었다. visited에는 연결된 모든 정보들이 나오므로 1씩 넣어 모두 더해준 후 자기 자신은 포함하지 않아야 하므로 1을 뺀 후 출력하였다.

 

두 번째 해결방법

DFS 사용하기

n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

for i in range(m):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(graph, start_node, visited):
    visited[start_node] = 1
    for i in graph[start_node]:
        if not visited[i]:
            dfs(graph, i, visited)
    return sum(visited)

print(dfs(graph, 1, visited) - 1)

두 번째 BFS를 사용한 방법과 같은 방법을 사용하였다. 시간, 메모리를 제일 적게 사용하여 이 문제에서 가장 효율적인 방법이었다.