보름달빵
2025. 6. 26. 16:33
문제
https://www.acmicpc.net/problem/7576
풀이과정
이 문제는 익은 토마토 옆에 있는 안익은 토마토가 하루가 지나면 익는다고 하였을때, 상자 안에 있는 모든 토마토가 익는데 걸리는 "최소 날짜" 를 구하는 문제이다. 익은 토마토를 기준으로 상하좌우로 파도처럼 퍼져나가며 주변 토마토의 상태를 바꾸면 되기 때문에 BFS로 문제를 푸는 것이 적당해 보인다.
그런데 이 문제에서 주의할 것은 이미 모두 익은 토마토가 주어진 경우에는 0, 토마토가 모두 익지는 않은 경우 -1을 출력해야한다는 것이다.
따라서 위의 두 경우에 유의하며 출력값이 나올 수 있도록 코드를 작성해보자.
static int n,m; // 상자의 정보
static int[] dx= new int[]{-1,1,0,0};
static int[] dy= new int[]{0,0,-1,1};
static boolean[][] visited; // 방문 배열- 상자의 크기를 표현하는 n,m
- 상하좌우의 값을 구할때 사용할 dx,dy를 static 변수로 선언해준다.
- visited 라는 방문 배열을 통해, 한번 익었다고 체크한 토마토를 다시 확인하지 않도록 한다.
Main
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken()); // 열
n = Integer.parseInt(st.nextToken()); // 행
// 방문 배열 생성
visited = new boolean[n][m];
// 토마토 상자 생성
int [][] arr = new int[n][m];
for(int i=0;i<n;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<m;j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(bfs(arr));
}
- 첫번째줄에 상자의 크기를 나타내는 M,N이 주어진다. 이때 M은 가로길이, N은 세로길이이다.
- M,N의 크기에 맞게 상자 배열과 방문 배열을 초기화해준다.
- 이후 반복문을 통해 상자의 정보를 배열에 저장한다.
bfs
static int bfs(int [][] temp)
- arr 배열을 static 변수로 선언하면 bfs 함수를 호출할때 어떤 매개변수를 넘겨줘야할지 잘 모르겠다.
- 그래서 그냥 매개변수를 배열로 설정하여 static 변수를 사용하지 않았다.
- 또한 bfs함수 속에서 구한 최소날짜(count) 값을 리턴해주도록 리턴값은 int형으로 한다.
bfs 코드
static int bfs(int [][] temp){
boolean flag=false;
Queue<tomato> queue = new LinkedList<>();
// 배열을 탐색하며 익은 토마토를 찾아서 큐에 넣기(시작점)
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j] && temp[i][j]==1){
visited[i][j]=true;
queue.add(new tomato(i, j));
}
}
}
int count=-1; // 최소 날짜
while(!queue.isEmpty()){
int size = queue.size();
count++; // 큐가 빌때 까지 count값 증가 시키기
for(int i=0;i<size;i++){
tomato curr = queue.poll();
// 현재 토마토와 인접한 토마토 확인하기
for(int j=0;j<4;j++){
int nx = curr.x + dx[j];
int ny= curr.y + dy[j];
if(nx>=0&&nx<n && ny>=0&& ny<m&& !visited[nx][ny] && temp[nx][ny]==0){
visited[nx][ny]=true;
temp[nx][ny]=1;
queue.add(new tomato(nx, ny));
}
}
}
}
// 익지 않은 토마토가 있는지 확인하기
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(temp[i][j]==0) {
flag=true;
break; // 0인 값을 찾는 즉시 반복문 종료
}
}
}
return (flag)? -1:count;
}- 위에는 전체 코드이다. 하나씩 코드를 확인해보자.
bfs 코드 설명
Queue<tomato> queue = new LinkedList<>();
// 배열을 탐색하며 익은 토마토를 찾아서 큐에 넣기(시작점)
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j] && temp[i][j]==1){
visited[i][j]=true;
queue.add(new tomato(i, j));
}
}
}
int count=-1; // 최소 날짜
while(!queue.isEmpty()){
int size = queue.size();
count++; // 큐가 빌때 까지 count값 증가 시키기
for(int i=0;i<size;i++){
tomato curr = queue.poll();
// 현재 토마토와 인접한 토마토 확인하기
for(int j=0;j<4;j++){
int nx = curr.x + dx[j];
int ny= curr.y + dy[j];
if(nx>=0&&nx<n && ny>=0&& ny<m&& !visited[nx][ny] && temp[nx][ny]==0){
visited[nx][ny]=true;
temp[nx][ny]=1;
queue.add(new tomato(nx, ny));
}
}
}
}
- 이 코드는 일반적인 BFS 형태를 가진 코드이다.
- 먼저 처음 배열에서 익은 토마토들의 정보를 찾아서 큐에 넣어준다.
- 이후 큐에서 하나씩 노드(토마토)를 꺼내면서 상하좌우에서 익지않은 토마토를 찾아서 상태변경 && 방문처리를 한 후 다시 큐에 넣는다. ( 일반적인 bfs 논리 )
- 주의할 것은 최소 날짜를 의미하는 count 변수의 초깃값이 -1 이라는 것이다. count=0 로 시작하면 원래 구해야하는 최솟값에서 +1 인 값이 구해지기 때문에 0 이 아닌 -1로 초기화 해두자.
문제의 출력 예시에서 "이미 모두 익은 토마토가 주어진 경우에는 0, 토마토가 모두 익지는 않은 경우 -1을 출력해야한다는 것이다. " 라는 조건이 있었다.
- 이미 모두 익은 토마토가 주어졌다는 것은 배열의 값이 1로 채워져있다는 뜻이다.(-1은 있거나 없거나) 이 경우 위의 while 코드를 이용할 경우 출력값이 0이 나오기 때문에 별다른 코드를 추가해 줄 필요가 없다.
- 하지만 토마토가 모두는 익지 않은 경우에는 조건을 생각해 볼 필요가 있다.
입력 예시 1 (익힐 수 없는 고립된 토마토가 있는 경우)
3 3
1 -1 0
-1 -1 -1
0 -1 1
출력 예시 3
-1
입력 예시 2 (최소 크기, 한 칸만 있을 때 아직 안 익은 경우)
1 1
0
출력 예시 5
-1
위의 두 예시처럼 고립된 토마토가 있거나, 아직 안 익은 토마토들만 있다면 상자 안의 토마토들은 익을 수 없을 것이다.
이 경우에는 -1을 출력해줘야한다. 그래서 처음에는 이 조건들을 가진 토마토 상자를 어떻게 구분해서 코드로 작성할지 고민 했었다.
하지만 반대로 생각해보면, bfs 코드를 실행하고 나면 상자의 토마토들의 상태가 안익은 상태(배열의 값이 0)에서 익은 상태(배열의 값이 1)로 바뀌기 때문에 bfs 코드를 수행하고 나서도 배열안에 익지 않은 토마토가 남아있다면, 모든 토마토가 익을 수는 없는 상태 인것이다.
따라서 아래와 같이 bfs 코드를 수행하고 나서 배열안에 익지않은 토마토가 있는지 확인하고, 익지 않은 토마토가 존재한다면 탐색을 멈추고 -1을 출력하도록 해주었다.
boolean flag=false;
// 익지 않은 토마토가 있는지 확인하기
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(temp[i][j]==0) {
flag=true;
break; // 0인 값을 찾는 즉시 반복문 종료
}
}
}
return (flag)? -1:count;
전체 코드
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Q12_토마토 {
static int n,m; // 상자의 정보
static int[] dx= new int[]{-1,1,0,0};
static int [] dy= new int[]{0,0,-1,1};
static boolean[][] visited; // 방문 배열
static int bfs(int [][] temp){
boolean flag=false;
Queue<tomato> queue = new LinkedList<>();
// 배열을 탐색하며 익은 토마토를 찾아서 큐에 넣기(시작점)
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j] && temp[i][j]==1){
visited[i][j]=true;
queue.add(new tomato(i, j));
}
}
}
int count=-1; // 최소 날짜
while(!queue.isEmpty()){
int size = queue.size();
count++; // 큐가 빌때 까지 count값 증가 시키기
for(int i=0;i<size;i++){
tomato curr = queue.poll();
// 현재 토마토와 인접한 토마토 확인하기
for(int j=0;j<4;j++){
int nx = curr.x + dx[j];
int ny= curr.y + dy[j];
if(nx>=0&&nx<n && ny>=0&& ny<m&& !visited[nx][ny] && temp[nx][ny]==0){
visited[nx][ny]=true;
temp[nx][ny]=1;
queue.add(new tomato(nx, ny));
}
}
}
}
// 익지 않은 토마토가 있는지 확인하기
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(temp[i][j]==0) {
flag=true;
break; // 0인 값을 찾는 즉시 반복문 종료
}
}
}
return (flag)? -1:count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken()); // 열
n = Integer.parseInt(st.nextToken()); // 행
// 방문 배열 생성
visited = new boolean[n][m];
// 토마토 상자 생성
int [][] arr = new int[n][m];
for(int i=0;i<n;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<m;j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(bfs(arr));
}
public static class tomato {
int x;
int y;
tomato(int x, int y){
this.x = x;
this.y = y;
}
}
}