[BOJ/백준] 18231 파괴된 도시

# 18231 파괴된 도시






N,M = map(int,input().split())

graph = {i:[] for i in range(N+1)}

for _ in range(M):
    node1,node2 = map(int,input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

destory_cnt = int(input())
destroy_citys = list(map(int,input().split()))
result = []
destroyed = []
for destroy_city in destroy_citys:
    temp = [destroy_city]
    for city in graph[destroy_city]:
        if city not in destroy_citys:
            break
        else:
            temp.append(city)
    else:
        result.append(destroy_city)
        destroyed.extend(temp)
    if len(set(destroyed)) == destory_cnt:
        print(len(result))
        result.sort()
        print(' '.join(list(map(str,result))))
        break
else:
    print(-1)

이 문제는 여러가지 경우의 답이 나올수 있으나, 정답이 되는 1개만 출력하면 된다.

 

기본 원리는 이렇다. 그래프라는 딕셔너리에 양방향으로 노드를 전부 저장해놓는다.

 

그리고 파괴된 도시 목록을 입력을 받아, for문을 돌리는데, 만약 파괴된 도시 중 하나의 인접 노드들 중에 파괴된 노드들이 하나도 없으면 for문을 중지하고, 나온다. 그렇지 않을경우는 해당 도시는 파괴가 시작된 도시로 볼 수 있으므로, 결과목록에 넣어준다.

또한 해당 도시로 폭파된 도시 목록도 별도의 리스트에 저장해준다.

 

이렇게 반복을 해주면서, 별도로 저장해놓은 폭파된 도시목록을 set을 해줬을때의 길이가, 전체 파괴된 도시수와 동일하다면 for문을 중지하고, 결과를 보여준다.

 

위의 해당사항이 하나도 없을 시에는 -1을 출력해주면 된다.