Problem : https://www.acmicpc.net/problem/1119
1119번: 그래프
N개의 도시가 있고, 몇몇 도시들이 양방향 도로로 연결되어 있는 나라가 있다. 은진이는 이나라의 도로 몇 개를 수정해서 모든 도시가 서로 연결되어 있게 하려고 한다. 이때, 도로를 수정하는
www.acmicpc.net
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)
풀이 완료!