백준 python 1260번 DFS -BFS / 2606번 바이러스 / 2667번 단지번호

백준 python 1260번 DFS -BFS

 

입력

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

출력

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

Python

from collections import  deque n, m, v = map(int, input().split()) graph = [[] for _ in range(n + 1)] for i in range(m):     a, b = map(int, input().split())     graph[a].append(b)     graph[b].append(a)     graph[a].sort()     graph[b].sort() visited = [False] * (n + 1) def Dfs(graph, v, visited):     visited[v] = True     print(v, end=' ')     for i in graph[v]:         if not visited[i]:             Dfs(graph, i, visited) def Bfs(graph, v, visited):     visited = [False] * (n + 1)     queue = deque([v])     visited[v] = True     while queue:         pop = queue.popleft()         print(pop, end=' ')         for i in graph[pop]:             if not visited[i]:                 queue.append(i)                 visited[i] = True Dfs(graph, v, visited) print() Bfs(graph, v, visited)

 

 

백준 Python 2606번 바이러스

 

입력

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

출력

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

 

 

반응형

Python

from collections import deque n = int(input()); #컴퓨터 수 graph = [[] for _ in range(n + 1)] e = int(input()); #연결된 선 수 for i in range(e):     a, b = map(int, input().split())     graph[a].append(b)     graph[b].append(a)     graph[a].sort()     graph[b].sort() visited = [False] * (n + 1) def bfs(graph, start, visited):     result = 0     queue = deque([start])     visited[start] = True     while queue:         pop = queue.popleft()         for e in graph[pop]:             if not visited[e]:                 queue.append(e)                 visited[e] = True                 result += 1     print(result) bfs(graph, 1, visited)

 

 

백준 2667번 단지번호붙이기

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

Python

n = int(input()) graph = [list(map(int, input())) for _ in range(n)] def dfs(x, y, house_count):     if x <= -1 or x >= n or y <= -1 or y >= n:         return False     if graph[x][y] == 1:         graph[x][y] = house_count         dfs(x - 1, y, house_count)         dfs(x, y - 1, house_count)         dfs(x + 1, y, house_count)         dfs(x, y + 1, house_count)         return True     return False result = 0 for i in range(n):     for j in range(n):         if dfs(i, j, result + 2):             result += 1 house_count = [0] * result for i in range(n):     for j in range(n):         if graph[i][j] != 0:             house_count[graph[i][j] - 2] += 1 house_count.sort() print(result) for i in range(len(house_count)):     print(house_count[i])