백준 알고리즘 2606 바이러스 / 파이썬 (Python)
https://www.acmicpc.net/problem/2606
N = int(input())
P = int(input())
graph = [[0]*(N+1) for _ in range(N+1)]
done = [] # 바이러스가 완료된 애들을 넣어주는구나
for _ in range(P):
x, y = map(int, input().split())
graph[x][y], graph[y][x] = 1,1
def dfs(v):
done.append(v)
for k in range(1, N+1):
if (k not in done) and (graph[v][k] == 1):
dfs(k)
return (len(done) - 1)
print(dfs(1))
N = int(input())
P = int(input())
graph = [[0]*(N+1) for _ in range(N+1)]
전체 컴퓨터 수인 N 값과
총 연결값인 P값의 입력값을 받는다.
그 후
graph를 만든다. False, True 식의 인접행렬을 0과 1로 나타낸 것이다.
만들어진 graph는 리스트안에
[0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0],
[0 0 0 0 0 0 0 0],
. . . . .
이렇게 만들어진다.
for _ in range(P):
x, y = map(int, input().split())
graph[x][y], graph[y][x] = 1,1
연결된 컴퓨터의 입력값을 받는다.
입력값을 받을 때 마다, 만난 것들은 감염된 것들이니, 감염된 것들은,
위에서 만든 graph 리스트에 0을 1로 바꾸어 표기해준다.
이걸 좀 쉽게 이야기하면, 0~7까지, 각각 만나는 지점을 1로 바꿔준다고 생각하면 쉽다.
ex) 1, 2가 들어온 경우.
0 1 2 3 4 5 6 7
0 [0 0 0 0 0 0 0 0]
1 [0 0 1 0 0 0 0 0]
2 [0 1 0 0 0 0 0 0]
3 . . . . .
이렇게 (1,2) 가 만나는 지점과 (2,1)이 만나는 지점이 1로 바뀌었다. 즉 감염되었다.
def dfs(v):
done.append(v)
for k in range(1, N+1):
if (k not in done) and (graph[v][k] == 1):
# 1.2번째는 감염이 됨
dfs(k) #재귀함수를 통해 2
# 그럼 done에 2를 더하고
return (len(done) - 1)
print(dfs(1))
제일 끝까지 내려가 탐색하는 DFS의 방식을 활용한다. 함수명은 아무렇게나 해도 상관없다.
dfs(v) 함수에 v값이 들어오면
v값은 위에서 정한 done 리스트에 저장해준다.
done은 감염된 컴퓨터 넘버를 저장해주는 리스트다.
그 후 for문을 통해
(1~8) 즉 1부터 7까지 전체 컴퓨터 수를 반복하여 감염이 되었는지 안되었는지 확인한다.
if
만약 done( 감염된 컴퓨터 ) 리스트에 없는데 graph에서 만나는 지점이 0이 아니라 1인 경우,
이 경우는 감염된 컴퓨터 리스트인 done에는 없지만 감염된 컴퓨터 이므로,
재귀를 이용해 다시 dfs로 보내고, done에 그 숫자를 추가한다.
이런 식으로 계속 재귀를 통해 1~7까지 모든 만나는 지점을 검사하고,
1인 경우는 done에 추가하여 done 리스트를 채운다.
for문과 if문을 다 통과한 후
done의 길이에서 1을 빼고 리턴해준다.
1을 빼는 이유는 처음에 감염을 퍼뜨리는 컴퓨터를 done에 포함시켰기 때문에 그 길이에서 뺴준다.
'Back > Algorithm' 카테고리의 다른 글
Python 백준 알고리즘 2839 설탕배달 파이썬 (0) | 2021.03.12 |
---|---|
백준 알고리즘 1316 그룹단어 체크 파이썬 (0) | 2021.03.12 |
Python 백준 1874 스택수열 알고리즘 (0) | 2021.03.10 |
Python 백준 4949 균형잡힌세상 / 스택 알고리즘 (0) | 2021.03.10 |
Python 병합정렬 알고리즘 (0) | 2021.03.10 |