99클럽 코테 스터디 8일차 TIL - DFS&BFS (백준2644- 촌수계산)

https://www.acmicpc.net/problem/2644

• 오늘의 학습 키워드 : DFS & BFS
• 공부한 내용 
  
  

  예제1

  

  예제2

  • DFS로 푼 경우
    

    import sys
    
    # 입력 처리
    n = int(sys.stdin.readline().strip())  # 총 사람의 수
    a, b = map(int, sys.stdin.readline().strip().split())  # 촌수를 계산할 두 사람
    m = int(sys.stdin.readline().strip())  # 관계의 수
    graph = [[] for _ in range(n + 1)]  # 각 사람의 관계를 나타내는 인접 리스트
    
    # 관계 정보 입력
    for i in range(m):
        x, y = map(int, sys.stdin.readline().strip().split())
        graph[x].append(y)
        graph[y].append(x)  # 무향 그래프이므로 양쪽 모두 연결
    
    # 방문 배열 초기화 (-1은 방문하지 않았음을 의미)
    visited = [-1] * (n + 1)
    visited[a] = 0  # 시작 노드는 거리 0으로 설정
    
    # DFS 함수 정의
    def dfs(start, graph, visited):
        for i in graph[start]:  # 현재 노드에 연결된 모든 노드를 순회
            if visited[i] == -1:  # 방문하지 않은 노드라면
                visited[i] = visited[start] + 1  # 현재 노드까지의 거리 +1로 설정
                dfs(i, graph, visited)  # 재귀적으로 DFS 수행
    
    # DFS 실행
    dfs(a, graph, visited)
    
    # 결과 출력: 목표 노드까지의 거리 출력 (연결되지 않았으면 -1)
    print(visited[b])

  • BFS로 푼 경우
    

    import sys
    from collections import deque
    
    # 입력 처리
    n = int(sys.stdin.readline().strip())  # 총 사람의 수
    a, b = map(int, sys.stdin.readline().strip().split())  # 촌수를 계산할 두 사람
    m = int(sys.stdin.readline().strip())  # 관계의 수
    graph = [[] for _ in range(n + 1)]  # 각 사람의 관계를 나타내는 인접 리스트
    
    # 관계 정보 입력
    for i in range(m):
        x, y = map(int, sys.stdin.readline().strip().split())
        graph[x].append(y)
        graph[y].append(x)  # 무향 그래프이므로 양쪽 모두 연결
    
    # BFS 함수 정의
    def bfs(start, graph, end):
        visited = [-1] * (n + 1)  # 방문 배열: 방문하지 않은 노드는 -1
        queue = deque([start])  # 탐색을 시작할 노드를 큐에 추가
        visited[start] = 0  # 시작 노드는 거리 0으로 초기화
        
        # 큐가 빌 때까지 반복
        while queue:
            node = queue.popleft()  # 큐의 첫 번째 노드를 꺼냄
            
            # 현재 노드와 연결된 노드를 탐색
            for i in graph[node]:
                if visited[i] == -1:  # 아직 방문하지 않은 노드일 경우
                    visited[i] = visited[node] + 1  # 부모 노드 거리 +1
                    queue.append(i)  # 큐에 추가하여 다음 탐색에 사용
        
        return visited[end]  # 목표 노드의 거리 반환 (방문하지 않았으면 -1 반환)
    
    # BFS 실행 및 결과 출력
    print(bfs(a, graph, b))

• 오늘의 회고
  • 이건.. 전형적인 dfs, bfs 문제여서 생각보다 쉽게 끝나서 약간 좀 허무해서 이거 정리하고.. 챌린저 문제를 한번 더 풀어볼까 한다.
  • 오늘은 다른 공부는 하기 싫으니깐,, DFS BFS만 풀었다는 것에 만족하고 챌린저 끄적이러 간다 🫠
  • ㅎㅎ.. 챌린저 문제 설명 : https://coooco.tistory.com/190