99클럽 코테스터디 18일차 TIL - 백준 27971, 프로그래머스 전력망을 둘로 나누기

1. 문제: https://www.acmicpc.net/problem/27971

해당 문제는 다음과 같은 근거로 BFS로 풀이했다.

- 처음에는 강아지가 0마리임 --> N마리로 가기 위한 최소한의 행동횟수 : BFS

- 인덱스가 0부터 N까지 존재하는 배열을 그래프로 가정하고, 각 요소에 도착할 때마다 행동횟수를 +1 하는 방식으로 설계한다.

 

✅ 풀이

from collections import deque
# n: 키우길 원하는 강아지의 수
# m: 닫힌구간의 갯수
n, m, a, b = map(int, input().split())
visited = [-1] * (n+1)    # 1) -1을 선언함으로써 방문여부와 거리를 모두 판단할 수 있도록 함
for _ in range(m):
  l, r = map(int, input().split())
  for i in range(l, r+1):   # 2) 닫힌구간은 방문하지 않아야하는 곳이므로 먼저 방문처리 함
    visited[i] = 0

q = deque([0])
visited[0] = 0
while q:
  dogs = q.popleft()

  for c in [a, b]:
    sum = dogs + c    # 기존에 가지고있던 강아지에 A 생성 마법 혹은 B 생성마법 수행하여 강아지 생성
    if 1 <= sum <= n and visited[sum] == -1:   # 합이 n 이내에 있으면서 방문거리를 계산한 적이 없는 경우
      q.append(sum)
      visited[sum] = visited[dogs] + 1   # 방문처리 및 행동횟수 갱신

print(visited[n] if visited[n] > 0 else -1)  # n마리의 강아지를 만들 수 없다면 -1 출력

 

1) 방문 여부와 최소 행동 횟수를 모두 의미하는 visited 배열을 -1로 초기화하고, -1은 방문하지 않았음을 의미한다.

2) 닫힌 구간을 건너뛰어서 A마법과 B마법을 통해 강아지를 생성해야하므로, 먼저 방문처리함으로써 그래프 탐색에서 필터링될 수 있도록 한다.

3) BFS를 실행하되, 방문처리할 때 마법을 하나씩 수행했다는 의미이므로 +1 을 통해 행동횟수를 갱신한다.

4) 목표치였던 n 마리의 행동횟수에 해당하는 visited[n]이 음수라면 A, B 마법을 통해 n 마리의 강아지를 가질 수 없음을 의미하므로 -1을 출력하고, 그게 아니라면 최소의 행동횟수를 출력한다.

 

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

해당 문제를 풀 때 막혔던 부분은 다음과 같다.

1) 전선들 중 하나를 끊는다 --> 어떻게 끊지?

2) 두 전력망으로 분리하는데, 각 전력망마다 가지고 있는 송전탑의 갯수를 최대한 비슷하게 맞추고자 한다 --> 비슷하게 맞춘다는게 무슨 의미?

 

고민하다가 풀이를 찾아보니 다음과 같았다.

1) 전선들 중 하나를 끊는다

- 예를들어 연결리스트로 트리 형태를 표현한다고 할 때, a와 b의 연결관계를 끊는다고 하면 a 인덱스에 해당하는 리스트에서 b 제거, 양방향이므로 b 인덱스에 해당하는 리스트에서 a를 제거하는 방식이다.

- 주의할 점은, 문제에서 "전선들 중 하나를 끊어서 2개의 전력망으로 나눈다고 할 때, 송전탑의 갯수의 최소값"을 구하는 것이므로

모든 끊을 수 있는 케이스를 대상으로 탐색을 진행해야하므로, 끊었다가 다시 붙여야 한다는 점이다. (복원)

 

2) 각 전력망마다 가지고 있는 송전탑의 갯수를 최대한 비슷하게 맞춘다

- 이는 두 전력망의 송전탑의 갯수의 차이가 최소로 한다는 뜻이다.

- 즉 두 전력망이 가지고 있는 송전탑의 갯수 차이를 return하는 것이 목적이므로 차이가 최소일 때의 차이를 return 하면 된다.

 

def solution(n, wires):
    graph = [[] for _ in range(n+1)]   # 연결관계를 저장할 배열
    answer = 1e9   # 최소값을 비교해야하므로 최대로 설정함
    
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)   # 양방향 그래프
        
    def dfs(v):
        visited[v] = True
        count = 1
        
        for node in graph[v]:
            if not visited[node]:
                count += dfs(node)
                
        return count     # 방문한 노드 (송전탑의 갯수) 반환
                
    for a, b in wires:
        graph[a].remove(b)   # 전선들 중 하나를 끊어낸다
        graph[b].remove(a)   # 양방향이기 때문에 양쪽 모두 끊어내야함
        
        visited = [False] * (n+1)
        cnt_a = dfs(a)        # 송전탑의 갯수
        cnt_b = n - cnt_a     # 네트워크를 2개로 분할하는 것이므로, 다른 전력망은 전체 n개의 송전탑에서 위에서 나눈 송전탑의 갯수를 뺀것과 같다
        
        answer = min(answer, abs(cnt_b - cnt_a))
        # 두 전력망의 송전탑의 갯수의 차이가 최소인 값을 구하는것이 목적
        
        graph[a].append(b)   # 위에서 끊어냈고, 모든 끊을 수 있는 케이스를 파악해야하므로 다시 붙이기 작업 (복원)
        graph[b].append(a)
    
    return answer