View
[SWEA] 1247λ²: μ΅μ κ²½λ‘(Java)
μ± μ½λ κ°μ 2022. 8. 30. 21:40λ¬Έμ
μΌμ±μ μμ μλΉμ€ κΈ°μ¬μΈ κΉλ리λ νμ¬μμ μΆλ°νμ¬ λμ₯κ³ λ°°λ¬μ μν΄ Nλͺ μ κ³ κ°μ λ°©λ¬Ένκ³ μμ μ μ§μ λμκ°λ €νλ€.
νμ¬μ μ§μ μμΉ, κ·Έλ¦¬κ³ κ° κ³ κ°μ μμΉλ μ΄μ°¨μ μ μ μ’ν (x, y)λ‘ μ£Όμ΄μ§κ³ (0 β€ x β€ 100, 0 β€ y β€ 100)
λ μμΉ (x1, y1)μ (x2, y2) μ¬μ΄μ 거리λ |x1-x2| + |y1-y2|μΌλ‘ κ³μ°λλ€.
μ¬κΈ°μ |x|λ xμ μ λκ°μ μλ―Ένλ©° |3| = |-3| = 3μ΄λ€. νμ¬μ μ’ν, μ§μ μ’ν, κ³ κ°λ€μ μ’νλ λͺ¨λ λ€λ₯΄λ€.
νμ¬μμ μΆλ°νμ¬ Nλͺ μ κ³ κ°μ λͺ¨λ λ°©λ¬Ένκ³ μ§μΌλ‘ λμμ€λ κ²½λ‘ μ€ κ°μ₯ 짧μ κ²μ μ°ΎμΌλ € νλ€.
νμ¬μ μ§μ μ’νκ° μ£Όμ΄μ§κ³ , 2λͺ μμ 10λͺ μ¬μ΄μ κ³ κ° μ’νκ° μ£Όμ΄μ§ λ,
νμ¬μμ μΆλ°ν΄μ μ΄λ€μ
λͺ¨λ λ°©λ¬Ένκ³
μ§μ λμκ°λ κ²½λ‘ μ€ μ΄ μ΄λκ±°λ¦¬κ° κ°μ₯ 짧μ κ²½λ‘λ₯Ό μ°Ύλ νλ‘κ·Έλ¨μ μμ±νλΌ.
μ¬λ¬λΆμ νλ‘κ·Έλ¨μ κ°μ₯ 짧μ κ²½λ‘μ μ΄λκ±°λ¦¬λ§ λ°νλ©΄ λλ€.
μ΄ λ¬Έμ λ κ°μ₯ 짧μ κ²½λ‘λ₯Ό βν¨μ¨μ μΌλ‘β μ°Ύλ κ²μ΄ λͺ©μ μ΄ μλλ€.
μ¬λ¬λΆμ λͺ¨λ κ°λ₯ν κ²½λ‘λ₯Ό μ΄ν΄μ ν΄λ₯Ό μ°Ύμλ μ’λ€.
λͺ¨λ κ²½μ°λ₯Ό 체κ³μ μΌλ‘ λ°μ§ μ μμΌλ©΄ μ λ΅μ λ§μΆ μ μλ€.
[μ μ½μ¬ν]
κ³ κ°μ μ Nμ 2β€Nβ€10 μ΄λ€.
κ·Έλ¦¬κ³ νμ¬μ μ’ν, μ§μ μ’νλ₯Ό ν¬ν¨ν λͺ¨λ N+2κ°μ μ’νλ μλ‘ λ€λ₯Έ μμΉμ μμΌλ©° μ’νμ κ°μ 0μ΄μ 100 μ΄νμ μ μλ‘ μ΄λ£¨μ΄μ§λ€.
[μ λ ₯]
κ°μ₯ 첫μ€μ μ 체 ν μ€νΈμΌμ΄μ€μ μμ΄λ€.
μ΄ν, λ μ€μ ν μ€νΈ μΌμ΄μ€ νλμ©μ΄ μ°¨λ‘λ‘ μ£Όμ΄μ§λ€.
κ° ν μ€νΈ μΌμ΄μ€μ 첫째 μ€μλ κ³ κ°μ μ Nμ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€μλ νμ¬μ μ’ν,μ§μ μ’ν, Nλͺ μ κ³ κ°μ μ’νκ° μ°¨λ‘λ‘ λμ΄λλ€.
μ’νλ (x,y)μμΌλ‘ ꡬμ±λλλ° μ λ ₯μμλ xμ yκ° κ³΅λ°±μΌλ‘ ꡬλΆλμ΄ μ 곡λλ€.
[μΆλ ₯]
μ΄ 10μ€μ 10κ°μ ν μ€νΈ μΌμ΄μ€ κ°κ°μ λν λ΅μ μΆλ ₯νλ€.
κ° μ€μ β#xβλ‘ μμνκ³ κ³΅λ°±μ νλ λ λ€μ μ΅λ¨ κ²½λ‘μ μ΄λ거리λ₯Ό κΈ°λ‘νλ€. μ¬κΈ°μ xλ ν μ€νΈ μΌμ΄μ€μ λ²νΈλ€.
μμ μ λ ₯ 1
10
5
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
10
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
...
μμ μΆλ ₯ 1
#1 200
#2 304
#3 366
...
π€¦ββοΈ My Solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class SW_1247 {
static int T, N, comY, comX, homeX, homeY, min;
static int[][] cust; // κ³ κ°μ μ 보
// μμ΄, μ‘°ν©, λΆλΆμ§ν© -> μκΈ° μμ€μΌλ‘ λμ΄μμ΄μΌν¨
static int[] tgt;
static boolean[] select;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int t = 1; t < T; t++) {
min = Integer.MAX_VALUE;
N = Integer.parseInt(br.readLine());// κ³ κ°μ
cust = new int[N][2];
select = new boolean[N];
tgt = new int[N]; //
StringTokenizer st = new StringTokenizer(br.readLine());
comY = Integer.parseInt(st.nextToken());
comX = Integer.parseInt(st.nextToken());
homeY = Integer.parseInt(st.nextToken());
homeX = Integer.parseInt(st.nextToken());
// Nκ° κ³ κ°μ λν μ 보
for (int i = 0; i < N; i++) { // y:0 x:1
cust[i][0] = Integer.parseInt(st.nextToken()); // yμ’ν
cust[i][1] = Integer.parseInt(st.nextToken()); // xμ’ν
}
// μμ΄
perm(0); // 0:tatμ 맨 μλΆν° μ±μ°κ² λ€
System.out.println("#" + t + " " + min);
}
}
static void perm(int tgtIdx) {
// κΈ°μ 쑰건
if (tgtIdx == N) {
// compete code
// νμ¬ μμ΄μ κ²½μ°μ μκ° νλ μμ±λ μν
// 거리κ³μ° ν μ΅μκ°μΈμ§ νμΈ, κ°±μ
// νμ¬ -> 첫 λ²μ§Έ κ³ κ°
int sum = distance(comY, comX, cust[tgt[0]][0], cust[tgt[0]][1]);
// 첫 λ²μ§Έ κ³ κ° -> λ§μ§λ§ κ³ κ°
for (int i = 0; i < N - 1; i++) {
sum += distance(cust[tgt[i]][0], cust[tgt[i]][1], cust[tgt[i + 1]][0], cust[tgt[i + 1]][1]);
}
// λ§μ§λ§ κ³ κ° -> μ§
sum += distance(cust[tgt[N - 1]][0], cust[tgt[N - 1]][1], homeY, homeX);
min = Math.min(min, sum);
return;
}
// src(cust)μ Nκ°μ κ³ κ° μ€ νλμ© μ νν΄ κ°λ κ³Όμ μ κ±°μΉλ€
// λ¨ μ΄λ―Έ μ΄μ μ μ νν κ³ κ°μ μ μΈν¨
for (int i = 0; i < N; i++) {
if (select[i])
continue; // μ΄λ―Έ μ νλ κ³ κ°μ΄λ©΄ μ€ν΅
select[i] = true;
tgt[tgtIdx] = i;// νμ¬ tgrIdxμ리μ iλ₯Ό μ ννμΌλ λ€μ μ리λ₯Ό 보λ¬κ°λ€
perm(tgtIdx + 1);
select[i] = false; // λ€μ λλλ €μ€λ€
}
}
static int distance(int y1, int x1, int y2, int x2) {
return Math.abs(y1 - y2) + Math.abs(x1 - x2);
}
}
'μκ³ λ¦¬μ¦ > μ½λ©ν μ€νΈ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BJ] 1987λ²: μνλ²³(Java) (0) | 2022.08.30 |
---|---|
[BJ] 1206: DFSμ BFS(Java) (0) | 2022.08.30 |
[BJ] 3109: λΉ΅μ§(Java) (0) | 2022.08.30 |
[μ μ¬] 1828: λμ₯κ³ (Java) (0) | 2022.08.30 |
[BJ] 1541λ²: μμ΄λ²λ¦° κ΄νΈ(Java) (0) | 2022.08.30 |