[코드트리] DFS/BFS - 그래프 탐색

김멉덥·2024년 3월 19일
0

알고리즘 공부

목록 보기
128/171
post-thumbnail
post-custom-banner

코드트리 학습하기 - 알고리즘 입문 : DFS/BFS

Code

N, M = map(int, input().split())        # N, M 입력받기
nodes = [list(map(int, input().split())) for _ in range(M)]     # 연결된 두 정점 입력받기

# 각 노드의 시작점, 끝점 구분해서 따로 담아두기
start_points = []
end_points = []
for i in range(len(nodes)):
    start_points.append(nodes[i][0])
    end_points.append(nodes[i][1])

# 2차원 배열 만들기
matrix = [[0 for _ in range(N)] for _ in range(N)]

for start, end in zip(start_points, end_points):
    matrix[start-1][end-1] = 1
    matrix[end-1][start-1] = 1

# print(matrix)

# 방문한 노드 체크
visited = [False for _ in range(N)]

# dfs 재귀
def dfs(node):
    for curr_node in range(N):
        if(matrix[node][curr_node] and not visited[curr_node]):
            visited[curr_node] = True
            # print(visited)
            # print((node+1, curr_node+1))
            dfs(curr_node)

# 1이 루트노드로 시작
root_node = 0
visited[root_node] = True
dfs(root_node)

count = 0
for i in range(1, len(visited)):
    if(visited[i]):
        count += 1
print(count)

풀이 및 해설

  • 재귀로 루트노드부터 시작해서 하나씩 방문처리하면서 dfs로 방문하기

정답 코드

# 변수 선언 및 입력
n, m = tuple(map(int, input().split()))

#index를 1번 부터 사용하기 위해 n+1만큼 할당합니다.
graph = [
    [0 for _ in range(n + 1)]
    for _ in range(n + 1)
]

visited = [False for _ in range(n + 1)]
vertex_cnt = 0

def dfs(vertex):
    global vertex_cnt
    
    # 해당 정점에서 이어져있는 모든 정점을 탐색해줍니다.
    for curr_v in range(1, n + 1):
        # 아직 간선이 존재하고 방문한 적이 없는 정점에 대해서만 탐색을 진행합니다.
        if graph[vertex][curr_v] and not visited[curr_v]:
            visited[curr_v] = True
            vertex_cnt += 1
            dfs(curr_v)
    

for i in range(m):
    v1, v2 = tuple(map(int, input().split()))

    # 각 정점이 서로 이동이 가능한 양방향 그래프이기 때문에
    # 각 정점에 대한 간선을 각각 저장해줍니다.
    graph[v1][v2] = 1
    graph[v2][v1] = 1

visited[1] = True
dfs(1)

print(vertex_cnt)
profile
데굴데굴 뚝딱뚝딱 개발기록
post-custom-banner

0개의 댓글