📍문제
Sam과 Quorra는 격자 세계에 있는 비밀 기지 지도를 만들고자 하고 있습니다. 이 비밀 기지는 여러 개의 (가상) 사이트가 서로 연결된 구조를 가지고 있습니다. 이 두 명은 사이트의 수(n)를 알고 있지만, 사이트 간 연결에 대한 정보는 부족한 상황입니다.
다만, 기지에 있는 여러 프로그램들이 사이트 간 연결에 대한 몇 가지 정보를 제공할 수 있어서 Sam과 Quorra는 이를 기반으로 사이트 간 연결에 대한 정보를 모아야 합니다. 특히, 모든 사이트에서 다른 각각의 사이트 모두로 이동할 수 있는지 판단하기에 충분한 정보가 있는지 확인하고자 합니다.
여러분의 목표는 주어진 연결 정보들이 모든 사이트에서 모든 각각의 다른 사이트로 이동할 수 있는 경로가 있는지 확인할 수 있게끔 도움을 주는 것입니다.
여기서 연결은 양방향이므로, 만약 사이트 1과 사이트 2 간에 연결이 있다는 정보가 주어진다면, 사이트 1에서 사이트 2로 이동할 수 있을 뿐만 아니라 그 반대로도 가능합니다.
입력
테스트 데이터 파일의 첫 번째 줄에는 테스트 케이스의 수 (최대 50개)가 포함되어 있습니다.
그 다음으로는 각 테스트 케이스가 나옵니다.
각 테스트 케이스의 첫 번째 숫자는 사이트의 수 n (최대 100)입니다.
각 사이트들은 0부터 n-1까지 번호가 매겨지며 두 번째 숫자는 사이트 간 연결의 수 k (최대 200)입니다.
그 이후에는 k개의 숫자 쌍이 나열되며, 각 사이드 간의 연결을 나타냅니다.
이 연결들은 중복될 수 있으며, 더 나아가 자체 연결(즉, 사이트에서 자신으로의 연결)이 존재할 수도 있습니다.
출력
각 테스트 케이스에 대해, 모든 사이트에서 다른 모든 사이트로의 경로가 있는지 확인하고, 그에 따라 "Connected." 또는 "Not connected."를 출력해야 합니다.
📍아이디어
전형적인 그래프 탐색 문제.
해당 문제의 경우 DFS로 풀었다. (DFS로만 문제를 푸는 주간이기도 하고 그래서...)
데이터 셋으로 주는 시작점과 끝 점을 시작 포인트 배열과 끝 포인트 배열로 받는다.
그 후 그래프 배열을 따로 만들어서 위에서 받은 정보들을 기반으로 인접 리스트를 생성한다.
그 다음으로 인접리스트를 돌며 DFS 탐색을 진행한다.
DFS 탐색이 끝나면 위에서 생성해 놓은 visit 배열을 확인하는데, 이 때 모든 배열이 True이면 각 사이트가 다 연결되어 있다는 것이므로 Connected를, 아니면 Not connected를 출력하면 된다.
📍제출 코드
import sys
t = int(sys.stdin.readline().rstrip())
def dfs(n):
for node in graph[n]:
if not visit[node]:
visit[node] = True
dfs(node)
for _ in range(t):
raw = list(map(int, sys.stdin.readline().rstrip().split()))
n = raw[0]
k = raw[1]
graph = [[] for _ in range(n)]
visit = [False for _ in range(n)]
start_point = []
end_point = []
for i in range(2, len(raw)):
if i % 2 == 0:
end = raw[i]
end_point.append(end)
else:
start = raw[i]
start_point.append(start)
for start, end in zip(start_point, end_point):
graph[start].append(end)
graph[end].append(start)
dfs(0)
if all(visit):
print("Connected.")
else:
print("Not connected.")
