문제를 꼼꼼히 읽고, 조건을 먼저 파악한 뒤에 문제를 푸는 습관을 들여야겠다.
java.awt.Point가 궁금해서 Java Flatform에서 찾아서 요약한 결과 다음과 같았다.
========================================================
public class인 Point class는 Point2D를 상속받고, Serializable을 implements하는 클래스.
참고로 int형만 들어올 수 있으므로, 좌표 값을 받을 때만 사용하면 좋을 것 같다.
========================================================
문제는 간단히 요약하면 다음과 같다.
1. N x M의 2차원 토마토 상자가 있다.
2. 익은 토마토가 있거나, 덜 익은 토마토가 있거나, 없거나 세 가지 경우가 존재한다.
3. 익은 토마토의 상, 하, 좌, 우의 덜 익은 토마토는 익은 토마토로 진화한다.
4. 토마토는 저절로 익지 않고, 영향을 받아야만 익는다.
5. 모든 토마토가 익기 까지 걸리는 최소 일 수는 며칠인가?
(단, 상자의 일부 칸에는 토마토가 없을 수도 있다)
[Input]
1. 상자의 크기 M, N 을 입력 받는다.
2~ 상자 속 토마토 정보가 2차원 배열로 주어진다.
[Output]
익을 때까지 최소 날짜를 출력해야 한다.
처음부터 모든 토마토가 익은 경우 0을 출력한다.
토마토가 모두 익지 못하는 상황이면 -1을 출력한다.
위의 밑줄 친 칸이 이 문제의 핵심. 이것 때문에 100퍼에서 틀렸다는 질문이 많이 올라온다(나도 이거 때문에 틀렸다)
[How to Solve?]
1. 2차원 배열에 토마토 정보를 담는다.
2. 두 개의 큐를 이용한다.
3. 첫 번째 큐에는 맨 처음 토마토 정보를 입력 받을 때, 익은 토마토의 위치를 담는다.
4. 두 번째 큐에는 첫 번째 큐의 모든 토마토로 부터 영향을 받아 익어진 토마토들의 위치를 담는다.
5. 각각의 예외 조건을 삽입하여 BFS로 문제를 풀어준다.
[Code]
간단한 문제인데, 너무 오래걸렸다.
이 문제를 풀면서 얻은바가 있다면
C++의 pair<int,int> 는 JAVA에서 Point Class 로 사용가능
사용 방법은 다음과 같다.
==========================================================
1. java.awt.Point를 import
2. Queue<Point> A = new LinkedList<Point>(); 로 선언.
3. A.add(new Point(a,b))로 삽입 가능.
4. 여기서 주의! A.poll 해버리면 두 좌표 모두 빠져나가기 때문에 A.peek().x, A.peek().y로 값을 뽑아낸 뒤에 A.poll로 빼내준다.
==========================================================
java.awt.Point가 궁금해서 Java Flatform에서 찾아서 요약한 결과 다음과 같았다.
========================================================
public class인 Point class는 Point2D를 상속받고, Serializable을 implements하는 클래스.
참고로 int형만 들어올 수 있으므로, 좌표 값을 받을 때만 사용하면 좋을 것 같다.
========================================================
문제는 간단히 요약하면 다음과 같다.
1. N x M의 2차원 토마토 상자가 있다.
2. 익은 토마토가 있거나, 덜 익은 토마토가 있거나, 없거나 세 가지 경우가 존재한다.
3. 익은 토마토의 상, 하, 좌, 우의 덜 익은 토마토는 익은 토마토로 진화한다.
4. 토마토는 저절로 익지 않고, 영향을 받아야만 익는다.
5. 모든 토마토가 익기 까지 걸리는 최소 일 수는 며칠인가?
(단, 상자의 일부 칸에는 토마토가 없을 수도 있다)
[Input]
1. 상자의 크기 M, N 을 입력 받는다.
2~ 상자 속 토마토 정보가 2차원 배열로 주어진다.
[Output]
익을 때까지 최소 날짜를 출력해야 한다.
처음부터 모든 토마토가 익은 경우 0을 출력한다.
토마토가 모두 익지 못하는 상황이면 -1을 출력한다.
위의 밑줄 친 칸이 이 문제의 핵심. 이것 때문에 100퍼에서 틀렸다는 질문이 많이 올라온다(나도 이거 때문에 틀렸다)
[How to Solve?]
1. 2차원 배열에 토마토 정보를 담는다.
2. 두 개의 큐를 이용한다.
3. 첫 번째 큐에는 맨 처음 토마토 정보를 입력 받을 때, 익은 토마토의 위치를 담는다.
4. 두 번째 큐에는 첫 번째 큐의 모든 토마토로 부터 영향을 받아 익어진 토마토들의 위치를 담는다.
5. 각각의 예외 조건을 삽입하여 BFS로 문제를 풀어준다.
[Code]
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
|
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.awt.Point;
public class boj_7576_tomato {
private static int N, M; // N행 M열
private static int Map[][];
private static boolean visited[][];
private static char state;
private static int total;
private static int xx[] = { -1, 1, 0, 0 };
private static int yy[] = { 0, 0, -1, 1 };
private static Queue<Point> A = new LinkedList<Point>();
private static Queue<Point> B = new LinkedList<Point>();
public static void bfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + xx[i];
int ny = y + yy[i];
if (nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1)
continue;
if (visited[nx][ny])
continue;
if (Map[nx][ny] == 0) {
Map[nx][ny] = 1;
visited[nx][ny] = true;
if (state == 'A')
A.add(new Point(nx, ny));
else if (state == 'B')
B.add(new Point(nx, ny));
}
}
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
Map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Map[i][j] = sc.nextInt();
if (Map[i][j] == 1)
A.add(new Point(i, j));
}
}
while (!A.isEmpty() || !B.isEmpty()) {
if(A.size()==N*M) {
System.out.println(0);
return;
}
if (B.isEmpty()) {
while (!A.isEmpty()) { // A가 비워져 있지 않다면
state = 'B';
int x = A.peek().x;
int y = A.peek().y;
A.poll();
bfs(x, y);
}
}
else if (A.isEmpty()) {
while (!B.isEmpty()) { // B가 비워져 있지 않다면
state = 'A';
int x = B.peek().x;
int y = B.peek().y;
B.poll();
bfs(x, y);
}
}
total++;
}
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(Map[i][j]==0)
{
System.out.println("-1");
return;
}
}
}
System.out.println(total-1);
}
}
| cs |
댓글
댓글 쓰기