[SWEA] #1259 - 금속막대

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN 

SW Expert Academy

 

💡 문제

---

[설명]

아래 그림에서 수나사의 굵기는 3을 암나사의 굵기는 4를 나타내고 있다.

이와 같은 원형 금속 막대를 연결하기 위해서는 수나사의 굵기와 암나사의 굵기가 서로 일치해야 하며, 연결은 +로 표현한다.

수나사와 암나사의 크기가 서로 다른 여러 개의 원형 금속 막대를 가장 많이 연결하려고 한다.

어떤 순서로 연결해야 가장 많이 연결하는지를 찾는 프로그램을 작성하시오.

 

💡 아이디어

---

 

테스트 케이스를 보면 예외 없이 모든 나사가 하나로 이어지는 것을 알 수 있다.

즉, 최대 길이는 금속 막대의 개수와 같아야 한다.

그렇기 위해 모든 금속 막대를 시작점으로 두고 완전 탐색을 통해 최대 길이의 정렬을 만들 수 있다. 

 

💡 소스코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//수나사와 암나사의 굵기를 저장하는 class
class Screw {
	int male;
	int female;

	Screw(int male, int female) {
		this.male = male;
		this.female = female;
	}
}

public class P_1259 {
	static int N;// 나사 쌍의 개수
	static ArrayList<Screw> screw;// 쌍을 저장할 ArrayList
	static Queue<Screw> result;// 결과를 저장할 Queue

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("P1259_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer sz;
		StringBuilder sb;

		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			sb = new StringBuilder();

			//입력 및 초기화
			N = Integer.parseInt(br.readLine());
			screw = new ArrayList<Screw>();
			result = new LinkedList<Screw>();

			sz = new StringTokenizer(br.readLine());

			//쌍 입력받고 저장
			for (int i = 0; i < N; i++) {
				int male = Integer.parseInt(sz.nextToken());
				int female = Integer.parseInt(sz.nextToken());
				screw.add(new Screw(male, female));
			}

			//쌍의 처음부터 solve() method 호출
			for (Screw i : screw) {
				solve(i);
				if (result.size() == N)//결과를 저장하는 Queue의 size가 N이랑 같으면
					break;//정렬이 완료됐다는 의미이므로 break
				else
					result.clear();
			}

			//출력
			sb.append("#" + TC + " ");
			while (!result.isEmpty()) {
				Screw i = result.poll();
				sb.append(i.male + " " + i.female + " ");
			}
			bw.write(String.valueOf(sb + "\n"));
		}
		br.close();
		bw.flush();
		bw.close();
	}

	public static void solve(Screw i) {
		result.add(i);//일단 결과를 저장하는 곳에 추가하고

		for (Screw j : screw) {
			if (i.female == j.male)//i의 암나사와 같은 굵기를 가지는 수나사가 있으면
				solve(j);//재귀호출
		}
	}
}

 

💡 결과

---

문제를 가장 빨리 푼 사람은 68ms였다.

문제를 푼 방법은 DFS로 로직은 비슷한데 시간의 차이가 많이 나는 이유는 아직 분석을 못 했다.

다음에 여유가 된다면 그분의 방법을 한 번 분석해봐야겠다.