forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path3.java
More file actions
104 lines (86 loc) ยท 3.03 KB
/
3.java
File metadata and controls
104 lines (86 loc) ยท 3.03 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.util.*;
class Virus implements Comparable<Virus> {
private int index;
private int second;
private int x;
private int y;
public Virus(int index, int second, int x, int y) {
this.index = index;
this.second = second;
this.x = x;
this.y = y;
}
public int getIndex() {
return this.index;
}
public int getSecond() {
return this.second;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
// ์ ๋ ฌ ๊ธฐ์ค์ '๋ฒํธ๊ฐ ๋ฎ์ ์์'
@Override
public int compareTo(Virus other) {
if (this.index < other.index) {
return -1;
}
return 1;
}
}
public class Main {
public static int n, k;
// ์ ์ฒด ๋ณด๋ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฐฐ์ด
public static int[][] graph = new int[200][200];
public static ArrayList<Virus> viruses = new ArrayList<Virus>();
// ๋ฐ์ด๋ฌ์ค๊ฐ ํผ์ ธ๋๊ฐ ์ ์๋ 4๊ฐ์ง์ ์์น
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = sc.nextInt();
// ํด๋น ์์น์ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ
if (graph[i][j] != 0) {
// (๋ฐ์ด๋ฌ์ค ์ข
๋ฅ, ์๊ฐ, ์์น X, ์์น Y) ์ฝ์
viruses.add(new Virus(graph[i][j], 0, i, j));
}
}
}
// ์ ๋ ฌ ์ดํ์ ํ๋ก ์ฎ๊ธฐ๊ธฐ (๋ฎ์ ๋ฒํธ์ ๋ฐ์ด๋ฌ์ค๊ฐ ๋จผ์ ์ฆ์ํ๋ฏ๋ก)
Collections.sort(viruses);
Queue<Virus> q = new LinkedList<Virus>();
for (int i = 0; i < viruses.size(); i++) {
q.offer(viruses.get(i));
}
int targetS = sc.nextInt();
int targetX = sc.nextInt();
int targetY = sc.nextInt();
// ๋๋น ์ฐ์ ํ์(BFS) ์งํ
while (!q.isEmpty()) {
Virus virus = q.poll();
// ์ ํํ second๋งํผ ์ด๊ฐ ์ง๋๊ฑฐ๋, ํ๊ฐ ๋น ๋๊น์ง ๋ฐ๋ณต
if (virus.getSecond() == targetS) break;
// ํ์ฌ ๋
ธ๋์์ ์ฃผ๋ณ 4๊ฐ์ง ์์น๋ฅผ ๊ฐ๊ฐ ํ์ธ
for (int i = 0; i < 4; i++) {
int nx = virus.getX() + dx[i];
int ny = virus.getY() + dy[i];
// ํด๋น ์์น๋ก ์ด๋ํ ์ ์๋ ๊ฒฝ์ฐ
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
// ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์์น๋ผ๋ฉด, ๊ทธ ์์น์ ๋ฐ์ด๋ฌ์ค ๋ฃ๊ธฐ
if (graph[nx][ny] == 0) {
graph[nx][ny] = virus.getIndex();
q.offer(new Virus(virus.getIndex(), virus.getSecond() + 1, nx, ny));
}
}
}
}
System.out.println(graph[targetX - 1][targetY - 1]);
}
}