[Python/파이썬] 백준 2606 : 바이러스

아시겠지만, 간단하게 1번 노드와 연결된 노드의 갯수만 세면 되는 문제입니다.

구구절절 잡다한 설명은 치우고 바로 시작합시다.

 

우선 생각해야 할 것들이 뭐가 있을까요?

바로 1번과 직접적으로든 간접적으로든 연결이 되어있지 않다면 그건 확인할 필요가 없다는 걸 생각해야죠!

그리고, 1번과 관계가 있는 노드는 모두 카운트 해야합니다. 근데 또 생각해보면 쉽더라고요.

왜냐면 그냥 1번부터 시작했으니까 visited 된 (방문 처리 된) 것들을 세보면 되지 않을까요?

 

생각은 다 했으니까..

어떻게 구현을 해볼까 생각을 해봐야죠.

근데 dfs를 할 때, graph라는 list를 만들어서 했었습니다. 그래서 연관된 것들을 계속 찾아갔죠.

그러니까 dfs가 완성이 되었고요.. 그러면 저희는 그냥 graph[1]번을 보고 거기에 저장된 노드들만 타고타고 가서 검색해보면 되겠습니다. 

 

그럼 그냥 dfs(1) 넣고 시작하는 거에요. 위에 말한 것들을 생각하면서 바로 아래 코드를 훑어보면 이해가 될 겁니다.

computer = int(input())
network = int(input())

# for를 computer+1로 함으로써 1 ~ computer 활용
# 자세한 설명 1260번 참고
## 아래에도 써둘게요!
graph = [[] for _ in range(computer+1)]

# 방문 여부를 기록할 visited
visited = [0] * (computer+1)

# 아래는 graph에 연결된 간선들을 표시하기 위한 작업입니다.
## 노드 1,2가 서로 연결되어 있다면 graph[1] 엔 [2]가 추가가 되고요,
## graph[2]엔 [1]이 추가가 됩니다.
for _ in range(network):
    x, y = map(int, input().split())
    graph[x] += [y]
    graph[y] += [x]

# 간단한 dfs 재귀문
def dfs(v):
	# 방문 체크 해주고
    visited[v] = 1
    # graph[v]에 연결된 노드를 다 확인해볼겁니다.
    for i in graph[v]:
    	# 만약에.. 노드 i가 방문처리가 안되어 있다면 재귀 들어가는 겁니다! 
        if visited[i] == 0:
            dfs(i)
            
# 문제에서 1번부터 시작한다고 했죠
dfs(1)

# 1은 빼고 출력
print(sum(visited)-1)

 

이해가 안 될만한 부분들은 뭐가 있을까요? 저는 개인적으로 처음에

for _ in range(network):
    x, y = map(int, input().split())
    graph[x] += [y]
    graph[y] += [x]

이 부분에서 개쩐다 라고 생각했습니다.

너무 간편하더라고요.. 아시는 분도 많겠지만 전 스스로 항상 초보라고 생각하기도 하고 그게 맞으니까...ㅎㅎ

 

1 4

2 4

3 1

 

이 입력으로 들어오면

 

graph[1] = [4]

grpah[4] = [1]

 

graph[2] = [4]

graph[4] = [1,2]

 

graph[3] = [1]

graph[1] = [4,3]

 

이런 식으로 해당 노드와 연결된 다른 노드들이 추가가 됩니다.

그럼 위의 세개의 입력만으로 그냥 코드가 진행된다고 생각하고 가봅시다.

 

1. dfs(1) 을 받으면 vistied[1] 은 방문처리가 됩니다.
2. graph[1] 은 [4,3] 으로 되어있습니다. 근데 4번 노드는 아직 방문하지 않았으니 dfs(4)가 작동합니다.
3. visited[4] 는 방문처리가 되고, graph[4]에 있는 [1,2]를 봅니다. 그런데 visited[1]은 1이니 넘어가고, visited[2]는 아직 0이니 다시 dfs(2)를 돌려줍니다.
4. visited[2] 를 방문처리 하고, graph[2] 에 연결된 것을 봅시다. 4인데 이건 이미 1이니 코드가 끝나고 그 전의 for문으로 갑니다.. 근데 for문도 끝이 났네요. 그럼 2번에서 한 dfs(4)를 넘어가게 되고, 3을 보게 되겠죠!
5. visited[3] 은 아직 방문이 안됐습니다. dfs(3)으로 혼내줍니다.
6. 이제 1번부터 4번까지 모든 노드가 방문 처리가 되었네요! 그런데 1번 컴퓨터를 통해 감염된 컴퓨터의 개수를 세는 것이니 2,3,4번 컴퓨터 총 3개.. 즉 3을 출력해주면 됩니다.

뭐 아무튼 위와 같이 동작합니다. 이해가 된다면 다행이지만... 저는 되니까 넘어가겠습니다. 감사합니다 :)

 

---

BFS로도 할 수 있어요!

def bfs(v):
    queue = deque()
    queue.append(v)
    while queue:
        popv = queue.popleft()
        visited[popv] = 1
        for i in graph[popv]:
            if visited[i] == 0:
                visited[i] = 1
                queue.append(i)

dfs 코드 대신 이거 넣으시면 됩니다~