https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
예제 입력 1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
예제 출력 1
8
예제 입력 2
6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
예제 출력 2
-1
예제 입력 3
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
예제 출력 3
6
예제 입력 4
5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0
예제 출력 4
14
예제 입력 5
2 2
1 -1
-1 1
예제 출력 5
0
[문제 풀이]
처음 작성했던 코드는 문제는 잘 해결되는데 메모리 초과가 났다.
큐에 <1,2>, <3,2> 가 들어있다면 두 노드 전부 <2,2>를 방문 가능하다. 따라서 따로 check 해주지 않으면 queue에 <2,2>가 2번 들어가게 되어 메모리 초과가 난다.
1번째 코드는 arraylist에 다음에 익을 토마토를 넣어주고 bfs가 한번 종료되고 나면 arraylist에 존재하는 위치의 토마토를 1로 변경해주었다.
2번째 코드는 temp 배열을 선언해서 temp를 bfs 안에서 변경시키고 bfs가 종료하고 나면 map을 temp로 변경해주었다. 해당 과정을 통해 arraylist에 동일한 값이 있는지 없는지를 검사할 필요는 없어졌지만, 같은 값이 queue에 계속 들어가 메모리 초과를 해결할 수는 없었다.
3번째 코드는 시간 초과가 났다. check배열을 선언해 한번 큐에 들어갔던 위치의 토마토는 다시 들어가지 않도록 설정했더니 메모리 초과는 해결할 수 있었다. 그러나 모든 토마토를 계속 탐색해야 하다보니 시간 초과가 나게 되었다.
마지막 코드는 처음 입력받을 때부터 익은 토마토를 queue에 넣고, queue에 존재하는 토마토에 대해서만 상, 하, 좌, 우 토마토를 확인하여 익지 않은 토마토이면 next라는 큐에 넣어준다. next 큐에 들어있는 위치의 토마토는 다음 bfs 탐색 시 익게 되는 토마토이고, bfs가 종료하고 나면 next큐에 들어있는 토마토를 꺼내 queue에 넣어주고 다음 bfs 탐색 대상이 된다. count는 익은 토마토의 총 개수이다. 총 익어야 하는 토마토의 개수는 M*N - (토마토가 들어있지 않은 칸의 개수)이고, 입력 받을 때부터 값이 1 또는 -1이면 count를 1 증가시킨 값으로 변경하고, bfs를 통해 변경시킨 최종 count가 M*N이면 모든 토마토가 익은 것으로 간주한다.
[코드 - 메모리 초과1]
import java.util.*;
class Node{
int row;
int col;
public Node(int row, int col) {
this.row = row;
this.col = col;
}
}
public class Main{
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int day=0;
static boolean[][] v;
static int M, N;
static int[][] map;
static Queue<Node> queue = new LinkedList<>();
static int count = 0;
static ArrayList<Node> al = new ArrayList<>();
public static void bfs() {
while(!queue.isEmpty()) {
Node node = queue.poll();
for(int i=0;i<4;i++) {
int nx = node.row + dx[i];
int ny = node.col + dy[i];
if(nx>=0&&ny>=0&&nx<N&&ny<M) {
if(!v[nx][ny]) {
Node next = new Node(nx, ny);
if(map[nx][ny]==1&&map[node.row][node.col]==0) {
boolean notin = true;
for(Node n:al) {
if(node.row==n.row && node.col==n.col) {
notin = false;
break;
}
}
if(notin)
al.add(node);
v[node.row][node.col]=true;
}
else if(map[nx][ny]==0&&map[node.row][node.col]==1) {
al.add(next);
v[nx][ny]=true;
}
v[node.row][node.col]=true;
queue.add(next);
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M =sc.nextInt();
N = sc.nextInt();
map = new int[N][M];
v = 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 || map[i][j]==-1)
count++;
}
}
Node start = new Node(0,0);
while(count<M*N) {
queue.add(start);
bfs();
day++;
for(int i=0;i<al.size();i++) {
Node n = al.get(i);
map[n.row][n.col] = 1;
}
if(al.size()==0) {
day= -1;
break;
}
count+=al.size();
v = new boolean[N][M];
al.clear();
}
System.out.println(day);
}
}
[코드 - 메모리 초과2]
import java.util.*;
class Node{
int row;
int col;
public Node(int row, int col) {
this.row = row;
this.col = col;
}
}
public class Main{
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int day=0;
static boolean[][] v;
static int M, N;
static int[][] map, temp;
static Queue<Node> queue = new LinkedList<>();
static int count = 0;
public static void bfs() {
while(!queue.isEmpty()) {
Node node = queue.poll();
v[node.row][node.col]=true;
for(int i=0;i<4;i++) {
int nx = node.row + dx[i];
int ny = node.col + dy[i];
if(nx>=0&&ny>=0&&nx<N&&ny<M) {
if(!v[nx][ny]) {
Node next = new Node(nx, ny);
if(map[nx][ny]==1&&map[node.row][node.col]==0) {
if(temp[node.row][node.col]==0) {
count++;
temp[node.row][node.col]=1;
}
}
else if(map[nx][ny]==0&&map[node.row][node.col]==1) {
if(temp[nx][ny]==0) {
temp[nx][ny]=1;
count++;
}
v[nx][ny]=true;
}
queue.add(next);
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M =sc.nextInt();
N = sc.nextInt();
map = new int[N][M];
temp= new int[N][M];
v = new boolean[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
map[i][j] = sc.nextInt();
temp[i][j] = map[i][j];
if(map[i][j] == 1 || map[i][j]==-1)
count++;
}
}
Node start = new Node(0,0);
int before = count;
while(count<M*N) {
queue.add(start);
bfs();
day++;
if(count-before==0) {
day= -1;
break;
}
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
map[i][j] = temp[i][j];
}
}
v = new boolean[N][M];
before = count;
}
System.out.println(day);
}
}
[코드 - 시간 초과]
import java.util.*;
class Node{
int row;
int col;
public Node(int row, int col) {
this.row = row;
this.col = col;
}
}
public class Main{
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int day=0;
static boolean[][] v;
static int M, N;
static int[][] map;
static Queue<Node> queue = new LinkedList<>();
static Queue<Node> next = new LinkedList<>();
static int count = 0;
static ArrayList<Node> al = new ArrayList<>();
static int[][] check;
public static void bfs() {
while(!queue.isEmpty()) {
Node node = queue.poll();
for(int i=0;i<4;i++) {
int nx = node.row + dx[i];
int ny = node.col + dy[i];
if(nx>=0&&ny>=0&&nx<N&&ny<M) {
if(!v[nx][ny]&&map[node.row][node.col]==1&&map[nx][ny]==0) {
next.add(new Node(nx,ny));
v[nx][ny]=true;
}
if(check[nx][ny]!=1) {
queue.add(new Node(nx,ny));
check[nx][ny]=1;
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M =sc.nextInt();
N = sc.nextInt();
map = new int[N][M];
v = 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 || map[i][j]==-1)
count++;
}
}
Node start = new Node(0,0);
while(count<M*N) {
check = new int[N][M];
check[0][0]=1;
queue.add(start);
bfs();
day++;
if(next.size()==0) {
day= -1;
break;
}
count+=next.size();
while(!next.isEmpty()) {
Node tomato = next.poll();
map[tomato.row][tomato.col]=1;
}
v = new boolean[N][M];
}
System.out.println(day);
}
}
[코드 - 최종 코드]
import java.util.*;
class Node{
int row;
int col;
public Node(int row, int col) {
this.row = row;
this.col = col;
}
}
public class Main{
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int day=0;
static boolean[][] v;
static int M, N;
static int[][] map;
static Queue<Node> queue = new LinkedList<>();
static Queue<Node> next = new LinkedList<>();
static int count = 0;
static ArrayList<Node> al = new ArrayList<>();
static int[][] check;
public static void bfs() {
while(!queue.isEmpty()) {
Node node = queue.poll();
for(int i=0;i<4;i++) {
int nx = node.row + dx[i];
int ny = node.col + dy[i];
if(nx>=0&&ny>=0&&nx<N&&ny<M) {
if(!v[nx][ny]&&map[nx][ny]==0) {
next.add(new Node(nx,ny));
v[nx][ny]=true;
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M =sc.nextInt();
N = sc.nextInt();
map = new int[N][M];
v = 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) {
queue.add(new Node(i,j));
count++;
}
if(map[i][j]==-1)
count++;
}
}
while(count<M*N) {
bfs();
if(next.size()==0) {
day = -1;
break;
}
count+=next.size();
day++;
while(!next.isEmpty()) {
queue.add(next.poll());
}
}
System.out.println(day);
}
}
'Algorithm > 백준' 카테고리의 다른 글
| [BOJ] 2178: 미로 탐색(JAVA) (0) | 2021.10.04 |
|---|---|
| [BOJ] 2606: 바이러스(JAVA) (0) | 2021.10.04 |
| [BOJ] 1991: 트리 순회(JAVA) (0) | 2021.10.01 |
| [BOJ] 14725: 개미굴(JAVA) (0) | 2021.09.28 |
| [BOJ] 1260: DFS와 BFS(JAVA) (0) | 2021.09.27 |