🎀 본 게시물은 프로그래머스 연습문제 풀이 게시물입니다. 🎀

---

https://school.programmers.co.kr/learn/courses/30/lessons/86971

방법은 한 간선별로 잘라 보면서 잘려진 노드랑 연결된 노드를 다 세어 보는 방법이다. 하나랑 연결된 노드를 다 세어보는거는 역시 DFS,BFS가 떠오른다.

---

🚀 정답 ⭕

DFS

def DFS(start, graph, visited, check_link):
    cnt = 1
    visited[start]=True                                             # 일단 v 노드는 방문함
    for adj_v in graph[start]:                                      # v에 연결 되어있는 다른 노드
        if visited[adj_v] == False and check_link[start][adj_v]:    # 인접한 연결되어 있는 노드가 방문한 적없고 
            cnt += DFS(adj_v, graph, visited, check_link)
    return cnt                                                  # 인접 연결 노드들 다 카운트

def solution(n, wires):
    answer = float("inf") 
    
    # 끊은 간선인지 아닌지 체크하기 위한 리스트 
    check_link = [[True]*(n+1) for _ in range(n+1)] 
    graph = [[] for _ in range(n+1)]    # 송전탑 그래프 

    # 그래프 채우기 
    for a,b in wires:
        graph[a].append(b)
        graph[b].append(a)
    
    for a,b in wires:                               # 간선 정보를 다 확인하면서 
        visited = [False]*(n+1)                     # a, b 그룹의 붙어있는 송전탑 개수를 세기위해
        check_link[a][b] = False                    # a에서 b로 가는 간선을 끊어봄 
        cnt_a = DFS(a, graph, visited, check_link)  # 그때 a랑 붙어 있는 송전탑 개수 
        cnt_b = DFS(b, graph, visited, check_link)  # 그때 b랑 붙어 있는 송전탑 개수 
        check_link[a][b] = True                     # a와 b 사이 끊은 간선을 다시 붙임
        
        answer = min(answer, abs(cnt_a - cnt_b))
    
    return answer

n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
print(solution(n, wires))

다음은 BFS

from collections import deque

def BFS(start, graph, visited, check_link):
        q = deque([start])
        visited[start] = True
        cnt = 1
        while q:
            s = q.popleft()
            for adj_v in graph[s]:
                if visited[adj_v] == False and check_link[start][adj_v]: 
                    q.append(adj_v)
                    visited[adj_v] = True
                    cnt += 1
        return cnt

def solution(n, wires):
    answer = n
    
    # 끊은 간선인지 아닌지 체크하기 위한 리스트 
    check_link = [[True]*(n+1) for _ in range(n+1)]
    graph = [[] for _ in range(n+1)]    # 송전탑 그래프 

    # 그래프 채우기 
    for a,b in wires:
        graph[a].append(b)
        graph[b].append(a)
    
    for a,b in wires:                               # 간선 정보를 다 확인하면서 
        visited = [False]*(n+1)                     # a, b 그룹의 붙어있는 송전탑 개수를 세기위해
        check_link[a][b] = False                    # a에서 b로 가는 간선을 끊어봄 
        cnt_a = BFS(a, graph, visited, check_link)  # 그때 a랑 붙어 있는 송전탑 개수 
        cnt_b = BFS(b, graph, visited, check_link)  # 그때 b랑 붙어 있는 송전탑 개수 
        check_link[a][b] = True                     # a와 b 사이 끊은 간선을 다시 붙임
        
        answer = min(answer, abs(cnt_a - cnt_b))
    
    
    return answer

n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
print(solution(n, wires))

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기