[Python] 2606번 바이러스

✏️ 문제

 

문제 파악

처음 바이러스에 걸린 컴퓨터와 인접된 모든 컴퓨터를 돌아야 하므로 BFS가 아닌 DFS를 사용해서 풀어야 한다.

 

# 1
graph = [[0] * (c+1)] * (c+1) 
graph[1][2] = 1

print(graph)
# [[0, 0, 1, 0],
#  [0, 0, 1, 0],
#  [0, 0, 1, 0],
#  [0, 0, 1, 0]]

# 2
graph = [[0] * (c+1) for _ in range(c+1)]
graph[1][2] = 1

print(graph)
# [[0, 0, 0, 0],
#  [0, 0, 1, 0],
#  [0, 0, 0, 0],
#  [0, 0, 0, 0]]

 

처음 graph 2차원 배열을 초기화할 때 # 1 과 같이했는데 원하는 값이 계속 안나왔다. 

 

찾아보니 # 1 과 같이 초기화하면 [0] * (c + 1)이라는 리스트를 한 번만 생성한 후 그 리스트를 c + 1번 복제해서 graph의 각 행으로 사용한다.  이럴 경우 각 행이 독립적인 리스트가 아니라 같은 리스트 객체의 참조가 돼서 하나의 행을 수정하면 모든 행이 동일하게 변경된다고 한다.

 

# 2 와 같은 경우 [0] * (c + 1)이라는 리스트를 c + 1번 생성하고 그 각각을 graph의 각 행으로 사용한다. 그래서 각 행은 독립적으로 생성된 리스트이기 때문에 한 행의 값을 변경해도 다른 행에는 영향을 미치지 않게 된다고 한다.

 

내가 원하는 건 # 2 와 같은 경우이므로 2차원 배열을 초기화 시킬 때 # 1 이 아닌 # 2 처럼 해야한다!

 

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

c = int(input())
n = int(input())

visited = [0] * (c+1)
graph = [[0] * (c+1) for _ in range(c+1)]

for i in range(n):
  x, y = map(int, input().split())
  graph[x][y] = 1
  graph[y][x] = 1
  
def dfs(v):
  visited[v] = 1

  for i in range(1, c+1):
    if visited[i] == 0 and graph[v][i] == 1:
      dfs(i)

dfs(1)
print(visited.count(1) - 1) # 시작인 컴퓨터는 개수에서 빼므로 -1

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS