28630번 - Починка цепочки
(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
박한별은 여러 개의 철사 고리로 이루어진 체인을 가지고 있었는데, 오랫동안 서랍에서 나뒹굴고 있던 나머지 완전히 엉켜 버렸다. 박한별은 은하에게 체인을 고쳐 달라고 부탁하려고 한다.
각 고리에는 1번부터 n번까지의 번호가 붙어 있으며 처음에는 모두 닫혀 있다. 서로 다른 두 고리는 연결되어 있거나 연결되지 않은 상태일 수 있다. 은하는 두 가지의 작업을 할 수 있다.
모든 작업이 끝난 뒤에는 모든 고리가 닫힌 상태여야 한다.
박한별은 1번 고리와 2번 고리, 2번 고리와 3번 고리, ..., n-1번 고리와 n번 고리를 연결하려고 한다. 즉, 모든 1 ≤ i < n에 대해 i번 고리와 i+1번 고리가 연결되어야 한다. 이 이외에 어떤 고리 쌍도 연결되어서는 안 된다.
은하가 체인을 고치기 위해 수행해야 하는 최소 작업 횟수를 구하는 프로그램을 작성하여라.
첫째 줄에 고리의 개수 n과 처음에 연결되어 있는 고리 쌍의 개수 m이 공백으로 구분되어 주어진다. (1 ≤ n ≤ 40, 0 ≤ m ≤ n(n-1)/2)
다음 줄부터 m개의 줄에 걸쳐 연결된 고리의 정보가 주어진다. 이 중 i번째 줄에는 서로 연결된 고리의 번호를 나타내는 두 정수 ai, bi가 공백으로 구분되어 주어진다. (1 ≤ ai, bi ≤ n; ai ≠ bi)
고리 쌍은 순서를 구분하지 않으며, 같은 고리 쌍이 여러 번 주어지지 않는다.
문제의 정답을 한 줄로 출력한다.
예제 입력 1에서는 우선 3번 고리를 풀어서 나머지 모든 고리에서 분리한 뒤, 다시 납땜하면서 2번 고리와만 연결하면 된다.
예제 입력 2에서는 우선 2번 고리를 푼 뒤 1번과 3번 고리와 연결한다. 그 다음에는 4번 고리를 푼 뒤 3번과 5번 고리와 연결하면 된다.
댓글을 작성하려면 로그인해야 합니다.
dlaud5379 9달 전
(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
박한별은 여러 개의 철사 고리로 이루어진 체인을 가지고 있었는데, 오랫동안 서랍에서 나뒹굴고 있던 나머지 완전히 엉켜 버렸다. 박한별은 은하에게 체인을 고쳐 달라고 부탁하려고 한다.
각 고리에는 1번부터 n번까지의 번호가 붙어 있으며 처음에는 모두 닫혀 있다. 서로 다른 두 고리는 연결되어 있거나 연결되지 않은 상태일 수 있다. 은하는 두 가지의 작업을 할 수 있다.
모든 작업이 끝난 뒤에는 모든 고리가 닫힌 상태여야 한다.
박한별은 1번 고리와 2번 고리, 2번 고리와 3번 고리, ..., n-1번 고리와 n번 고리를 연결하려고 한다. 즉, 모든 1 ≤ i < n에 대해 i번 고리와 i+1번 고리가 연결되어야 한다. 이 이외에 어떤 고리 쌍도 연결되어서는 안 된다.
은하가 체인을 고치기 위해 수행해야 하는 최소 작업 횟수를 구하는 프로그램을 작성하여라.
입력
첫째 줄에 고리의 개수 n과 처음에 연결되어 있는 고리 쌍의 개수 m이 공백으로 구분되어 주어진다. (1 ≤ n ≤ 40, 0 ≤ m ≤ n(n-1)/2)
다음 줄부터 m개의 줄에 걸쳐 연결된 고리의 정보가 주어진다. 이 중 i번째 줄에는 서로 연결된 고리의 번호를 나타내는 두 정수 ai, bi가 공백으로 구분되어 주어진다. (1 ≤ ai, bi ≤ n; ai ≠ bi)
고리 쌍은 순서를 구분하지 않으며, 같은 고리 쌍이 여러 번 주어지지 않는다.
출력
문제의 정답을 한 줄로 출력한다.
노트
예제 입력 1에서는 우선 3번 고리를 풀어서 나머지 모든 고리에서 분리한 뒤, 다시 납땜하면서 2번 고리와만 연결하면 된다.
예제 입력 2에서는 우선 2번 고리를 푼 뒤 1번과 3번 고리와 연결한다. 그 다음에는 4번 고리를 푼 뒤 3번과 5번 고리와 연결하면 된다.