문제 : boj2224
필요 알고리즘 개념
- 플로이드 와샬 (Floyd Warshall)
- O(N^3)이라 자주 못쓰지만, 쓸 수만 있으면 모든 정점에서 모든 정점으로의 최단경로 파악 혹은 길이 존재하는지 파악이 한방에 가능한 가장 강력한 탐색 알고리즘(대신 느림ㅋ) 플로이드 와샬을 쓸 수 있는 문제이다!! 구현도 엄청 간단하므로 플로이드 와샬을 써보자.
※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.
풀이
a => b 형태일 경우, a에서 b로 가는 간선을 연결하는 것으로 생각해보자. 그리고 a~z, A~Z를 모두 숫자로 변경하자. 이 때 변경방식은 A~Z를 0~25, a~z를 26~51로 하면 된다. 그래야 출력 시 순서대로 출력해주기가 편하다. 변경 방식은 코드의 atoi, itoa를 참고하자.
간선은 인접행렬로 표현할꺼다. boolean[][] arr에 대해, arr[a][b]가 true일 경우 a에서 b로 가는게 가능함을 나타낸다. 그럼 이제 로직은 다음과 같다.
1. 입력을 받으면서 a => b 형태일 경우 arr[a][b] = true로 한다.
2. 플루이드 와샬 알고리즘을 적용한다.
3. arr을 순회하면서 arr[a][b]가 true라면 출력해준다.
플로이드 와샬만 안다면 매우 간단한 로직임을 알 수 있다.
코드 : github
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
private int atoi(char c) {
if (c>='a') return c-'a'+26;
return c-'A';
}
private char itoa(int idx) {
if (idx<26) return (char)('A'+idx);
return (char)('a'+(idx-26));
}
private void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
boolean[][] arr = new boolean[52][52];
while (n-->0) {
String cur = br.readLine();
arr[atoi(cur.charAt(0))][atoi(cur.charAt(5))] = true;
}
for (int k = 0; k < 52; k++) {
for (int i = 0; i < 52; i++) {
for (int j = 0; j < 52; j++) {
if (i==j || i==k || k==j || arr[i][j]) continue;
if (arr[i][k] && arr[k][j]) arr[i][j] = true;
}
}
}
int cnt = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 52; i++) {
for (int j = 0; j < 52; j++) {
if (i == j || !arr[i][j]) continue;
cnt++;
sb.append(itoa(i)).append(' ').append('=').append('>').append(' ').append(itoa(j)).append('\n');
}
}
bw.write(String.valueOf(cnt));
bw.newLine();
bw.write(sb.toString());
bw.flush();
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
'PS > BOJ' 카테고리의 다른 글
[자바] 백준 1214 - 쿨한 물건 구매 (java) (2) | 2022.09.02 |
---|---|
[자바] 백준 25516 - 거리가 k이하인 트리 노드에서 사과 수확하기 (java) (0) | 2022.09.02 |
[자바] 백준 1647 - 도시 분할 계획 (java) (0) | 2022.09.02 |
[자바] 백준 17081 - RPG Extreme (java) (0) | 2022.09.01 |
[자바] 백준 5214 - 환승 (java) (0) | 2022.08.30 |
댓글