2022-07-23 @이영훈
접근 방법
그래프 탐색 문제입니다. 1번 노드와 간선으로 연결된 노드 수를 구하는 문제입니다. 그래프 탐색은 DFS(Depth First Search), BFS(Breadth First Search)로 할 수 있습니다.
저는 이 문제에서 DFS를 사용하여 문제를 풀었습니다.
방문한 노드 수를 count 변수로 두고 def dfs(graph, visited, start_node) 내에서 global count 로 접근하여 count += 1을 할수도 있지만 코드가 우아하지 않다고 생각했습니다. visited 배열에서 True 갯수에서 1을 제외한 수를 반환하였습니다.
파이썬 코드
import sys
input = sys.stdin.readline
nodes = int(input())
edges = int(input())
visited = [False] * (nodes + 1)
visited[1] = True
graph = [[0] * (nodes + 1) for _ in range(nodes + 1)]
for _ in range(edges):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
def dfs(graph, visited, start_node):
for i in range(len(graph[0])):
if graph[start_node][i] == 1 and visited[i] is False:
visited[i] = True
dfs(graph, visited, i)
dfs(graph, visited, 1)
first_node_visited_count = 1
print(visited.count(True) - first_node_visited_count)
Python
복사