[백준/1119] 그래프 (Python)

Problem : https://www.acmicpc.net/problem/1119

1119번: 그래프

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:10:!4

 

---

 

문제 설명

 

N개의 도시가 있고, 몇몇 도시들이 양방향 도로로 연결되어 있는 나라가 있다. 은진이는 이나라의 도로 몇 개를 수정해서 모든 도시가 서로 연결되어 있게 하려고 한다. 이때, 도로를 수정하는 회수를 최소로 하려고 한다. 도로를 수정하는 방법은 다음과 같다.

 

• A와 B가 연결되어 있고, C와 D가 연결되어 있으면서, A와 C, A와 D, B와 C, B와 D가 연결되어 있지 않은 4개의 도시 A, B, C, D를 선택한다.
• A와 B를 연결하는 도로와 C와 D를 연결하는 도로를 없앤다.
• A와 C, B와 D를 연결하거나 A와 D, B와 C를 연결한다.

 

다음 그림을 살펴보자.

위와 같은 도로가 있을 때 이것을 다음에 보이는 둘 중에 하나로 바꿀 수 있다.

 

N이 주어지고, 각 도로의 정보가 주어진다. 이때, 몇 개의 도로를 수정해야 하는지 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

첫째 줄에 N이 주어진다 N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 도로의 정보가 주어진다. 인접행렬형식으로 표현되어 있으며 예제를 참고하자. g[i][j] = g[j][i]이고, g[i][i] = N이다.

 

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

 

입력 예시

 

5
NYYNN
YNYNN
YYNNN
NNNNY
NNNYN

 

출력 예시

 

1

 

 

---

 

풀이

 

 

어떤 부분 그래프에 속한 노드의 개수를 n, 그리고 간선의 개수를 e라고 두자. 간선의 개수 e는 최소 n-1임이 보장되며(트리 구조를 생각하자!), 그 이상의 간선들(즉 그래프의 연결성을 해치지 않으면서 제거 가능한 간선들)은 잉여 간선들이라고 볼 수 있다.

 

N개의 모든 노드는 이러한 부분 그래프의 집합으로 볼 수 있고, 우리의 목표는 이 부분 그래프를 전부 잇는 것이다. 어떤 부분 그래프와 다른 부분 그래프는 이 잉여 간선 하나를 소모함으로써 서로 이어줄 수 있다.

 

• 어떤 부분 그래프의 잉여 간선 하나와
• 다른 부분 그래프의 간선 하나를(잉여 간선일 필요 x)
• 위 방식대로 서로 바꾸어 잇게 되면...
• 잉여 간선 하나가 줄어들고 두 그래프의 연결성이 보장된다.

 

즉 부분 그래프가 G개가 있고, 잉여 간선의 개수가 G-1개 이상이라면 G-1번의 수정으로 연결 가능하다!

단 불가능한 경우를 고려해 주어야 한다. 간선 하나를 최소로 보유하고 있어야 되므로, 부분 그래프에 속하는 노드 개수는 무조건 1 이상이여야 한다. 단, N = 1인 경우 즉 처음부터 노드가 1개인 경우는 그 자체로 정답이 된다

 

이 부분 그래프의 개수, 각 그래프의 노드 개수와 간선 개수 n, e는 그래프 탐색 알고리즘을 토대로 전부 구현 가능하다.

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
maps = [input().strip() for _ in range(N)]

if N == 1 :
  print(0)
  exit()

visited = [False]*N
edge_list = list()

def dfs(node) :
  q = [ node ]
  visited[node] = True
  edges, nodes = 0, 0

  while q :
    node = q.pop()
    nodes += 1
    for i in range(N) :
      if maps[node][i] == 'N' :
        continue
      edges += 1
      if not visited[i] :
        visited[i] = True
        q.append(i)
  edge_list.append((nodes, edges // 2))

for i in range(N) :
  if not visited[i] :
    dfs(i)

enable = True
cnt = 0
for nodes, edges in edge_list :
  if nodes == 1 :
    enable = False
    break
  cnt += edges - nodes + 1

print(len(edge_list) - 1 if enable and cnt >= len(edge_list)-1 else -1)

풀이 완료!