[Baekjoon] #1260 DFS와 BFS / #2606 바이러스

#1260 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 복사

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 복사

1 2 4 3
1 2 3 4

풀이

n, m, start = map(int, input().split())
arr = [[0]*(n+1) for _ in range(n+1)] 
# size를 n+1로 해야 index넘버 = 정점넘버로 편하게 사용할 수 있다. 0번 row, column은 쓰지 않음
visit = [0]*(n+1)
for i in range(m):
    n1, n2 = map(int, input().split())
    arr[n1][n2] = 1
    arr[n2][n1] = 1

def dfs(start):
    visit[start] = 1
    print(start, end=' ')
    for i in range(1, n+1):
        if arr[start][i]==1 and visit[i]==0:
            dfs(i)

def bfs(start):
    q = [start]
    visit[start] = 1

    while q:
        num = q.pop(0)
        print(num, end=' ')
        for i in range(1, n+1):
            if arr[num][i] == 1 and visit[i] == 0:
                q.append(i)
                visit[i] = 1

dfs(start)
print()
visit = [0]*(n+1)
bfs(start)

• 이어진 정점들의 관계를 ‘관계행렬’ arr로 표현한다.
  • 이 때, 정점넘버와 인덱스넘버를 일치시킴으로써 직관적으로 코딩하기 위하여 size를
• 탐색을 마친 정점을 표시하기 위한 1차원 배열 visit을 이용한다.
• DFS - 재귀함수로 구현
  • 시작정점과 연결이 되어있으면서(arr[start][i]==1)
  • 그 정점을 탐색하지 않았다면(visit[i]==0)
  • 해당 정점을 다시 파라메터로 하여 재귀함수를 실행
  • 이렇게 되면 시작정점과 연결된 가장 깊은 정점까지 먼저 탐색하게 된다.
  • 이후에 다시 (dfs(start))의 if문 밖의 for문으로 돌아와 다음에 연결된 정점들을 끝까지 탐색한다.
• BFS - 반복문으로 구현
• queue를 만들어 시작 정점을 pop한다.(탐색완료)
• 이후 그 정점과 연결되어 있으면서도 탐색하지 않은 정점들을 차례대로 queue에 담음
• queue에서 계속해서 첫번째 정점을 pop하고 그 정점과 연결된 다른 정점들을 queue에 담음
• 이렇게 되면 탐색순서가 자연스럽게 깊이가 동일한 정점들부터 차례차례 정해지게 된다.

#2606 바이러스

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1 복사

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 복사

4

풀이

n = int(input())
m = int(input())
arr = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    n1, n2 = map(int, input().split())
    arr[n1][n2] = 1
    arr[n2][n1] = 1
computer = [0]*(n+1)

def bfs(start):
    q = [start]
    computer[start] = 1
    cnt = 0

    while q:
        num = q.pop(0)
        for i in range(1, n+1):
            if arr[num][i] == 1 and computer[i] == 0:
                q.append(i)
                computer[i] = 1
                cnt += 1
    print(cnt)

bfs(1)

• 위의 bfs 구현 코드와 거의 동일한 흐름을 보인다.
  • 다만, 감염되는 컴퓨터 수를 카운트해야하므로 변수 cnt에 해당 값을 저장하여 반환한다.