[BOJ] 2660.νμ₯ λ½κΈ° (Java, BFS)
by λλΆλ
2660λ²: νμ₯λ½κΈ°
μ λ ₯μ 첫째 μ€μλ νμμ μκ° μλ€. λ¨, νμμ μλ 50λͺ μ λμ§ μλλ€. λμ§Έ μ€ μ΄νλ‘λ ν μ€μ λ κ°μ νμλ²νΈκ° μλλ°, μ΄κ²μ λ νμμ΄ μλ‘ μΉκ΅¬μμ λνλΈλ€. νμλ²νΈλ 1λΆν°
www.acmicpc.net
λ¬Έμ λ₯Ό μ²μ λ΄€μ λ μ΄ν΄κ° κ°μ§ μμμ μ 리νμ΅λλ€. λ¬Έμ μ€λͺ
μ μ μ΄λ κ² νμκΉ ππ
λ¬Έμ μ΄ν΄νκΈ°
- νμ₯μ μ μκ° κ°μ₯ μ μ μ¬λμ΄ λ©λλ€.
- μ μ κ³μ° λ°©λ²μ λ€μκ³Ό κ°μ΅λλ€.
1μ : Aνμμ΄ Bνμκ³Ό μΉκ΅¬ κ΄κ³ (A-B)
2μ : Aνμμ΄ Bνμκ³Ό μΉκ΅¬ κ΄κ³μ΄λ©΄μ, Bνμμ μΉκ΅¬μΈ Cνμκ³Όλ μΉκ΅¬ κ΄κ³ (A-B-C)
3μ : Aνμμ΄ Bνμκ³Ό μΉκ΅¬ κ΄κ³μ΄λ©΄μ, Bνμμ μΉκ΅¬μΈ Cνμκ³Όλ μΉκ΅¬ κ΄κ³μ΄λ©΄μ, Cνμμ μΉκ΅¬μΈ Dνμκ³Όλ μΉκ΅¬ κ΄κ³ (A-B-C-D)
…
μ΄λ° μμΌλ‘ κ΄κ³μλ μ¬λμ΄ λ§μμ§ μλ‘ μ μλ μ μ 컀μ§λλ€.
⇒ νμμ΄ κ°μ§ μ μλ μ μ μ€ κ°μ₯ ν° μ μλ₯Ό νμμ μ μλ‘ κ°μ§λλ€. - νμ μλ 50λͺ μ λμ§ μμ΅λλ€.
- μ λ ₯ : 첫째 μ€ νμ μ, λμ§Έ μ€λΆν° νμλ€ μΉκ΅¬ κ΄κ³, λ§μ§λ§ μ€μ -1 λ κ°
- μΆλ ₯ : 첫째 μ€ νμ₯ ν보 μ μμ ν보 μ, λμ§Έ μ€ νμ₯ ν보 μ€λ¦μ°¨μ
μμ μ΄ν΄λ³΄κΈ°
μμ μ μ£Όμ΄μ§ 5λͺ μ νμλ€μ κ΄κ³λ μλμ κ°μ΅λλ€.
κ° κ΄κ³μ λν΄ μ μλ‘ λνλ΄λ΄ μλ€.
1 | 2 | 3 | 4 | 5 | |
1 | 0 | 1 | 2 | 2 | 3 |
2 | 1 | 0 | 1 | 1 | 2 |
3 | 2 | 1 | 0 | 1 | 1 |
4 | 2 | 1 | 1 | 0 | 1 |
5 | 3 | 2 | 1 | 1 | 0 |
λ°μ μ μμ μ΅κ³ μ μλ₯Ό κ³μ°ν΄λ³΄λ©΄ μλμ κ°μ΅λλ€.
1 | 2 | 3 | 4 | 5 |
3 | 2 | 2 | 2 | 3 |
μ¬κΈ°μ κ°μ₯ μμ μ μλ 2μ μ΄λ―λ‘, νμ₯ ν보 μ μλ 2μ μ΄ λ©λλ€. κ·Έλ¦¬κ³ νμ₯ ν보λ 2, 3, 4λ‘ 3λͺ μ λλ€.
λ°λΌμ μλμ κ°μ΄ μΆλ ₯λ©λλ€.
2 3 2 3 4 |
λ¬Έμ νμ΄λ³΄κΈ°
μ¬κΈ°μλ λλΉ μ°μ νμμΌλ‘ νμ΄λ³Ό μμ (νλ‘μ΄λ-μμ λ‘λ ν μ μμ)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int memberNum = input.nextInt() + 1; // νμ λ²νΈκ° 1λ²λΆν° μμνλ―λ‘ memberNum μ 1κ° λλ €μ€λ€!
boolean[][] memberRelations = new boolean[memberNum][memberNum];
while (true) {
int i = input.nextInt();
int j = input.nextInt();
if (i == -1 && j == -1) break;
memberRelations[i][j] = true;
memberRelations[j][i] = true;
}
solution(memberNum, memberRelations);
}
private static void solution(int memberNum, boolean[][] memberRelations) {
List<Integer> candidates = new ArrayList<>();
int minScore = Integer.MAX_VALUE;
// κ° λ©€λ² μ μ κ³μ°
for (int i = 1; i < memberNum; i++) {
int[] scores = new int[memberNum];
Arrays.fill(scores, -1);
Queue<Integer> nextMembers = new LinkedList<>();
nextMembers.add(i);
scores[i] = 0;
while (!nextMembers.isEmpty()) {
int member = nextMembers.poll();
for (int j = 1; j < memberNum; j++) {
if (memberRelations[member][j] && scores[j] < 0) {
nextMembers.add(j);
scores[j] = scores[member] + 1;
}
}
}
int score = Arrays.stream(scores).max().getAsInt();
if (score > minScore) continue;
if (score < minScore) {
minScore = score;
candidates = new ArrayList<>();
}
candidates.add(i);
}
Collections.sort(candidates);
// κ²°κ³Ό μΆλ ₯
System.out.println(minScore + " " + candidates.size());
candidates.forEach(candidate -> System.out.print(candidate + " "));
}
}
'Algorithm > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] 2016.λ―Έν μ£Όμ νκΈ° (0) | 2022.06.13 |
---|---|
[BOJ] 2615.μ€λͺ© (Java) (0) | 2022.04.21 |
[BOJ] 1759.μνΈλ§λ€κΈ° (Java) (0) | 2021.06.20 |
[BOJ] 12094.Aμ B (Java) (0) | 2021.06.10 |
[BOJ] 10159.μ μΈ (Java) (0) | 2021.05.02 |
λΈλ‘κ·Έμ μ 보
λλΆλμ Devlog
λλΆλ