Java 알고리즘 BFS 토마토 문제 풀이

오늘은 BFS를 활용하여 토마토 문제를 풀어보려 합니다. 토마토 문제는 근방에 익은 토마토가 있다면 하루가 지나 같이 익게 되고, 모든 토마토가 다 익을 때까지의 날짜 수를 구하는 문제입니다😄

 

BFS 토마토

 

개요

문제 설명

 

입·출력

예시

 

이 문제의 핵심은 BFS 알고리즘을 활용과 Queue의 원리, 여러 시작점에서 동시다발적으로 여러개의 토마토가 익는 부분, 상자의 상하좌우 확인 방법, 익은 토마토를 체크 총 5가지가 되겠네요😀

 

TomatoPoint📙

class TomatoPoint {
    public int x,y;
    TomatoPoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

TomatoPoint 클래스는 상자판에서 행,열을 입력할 때 사용합니다. 근방에 익은 토마토에 의해 해당 토마토가 익을 때 큐에 쌓이고, 또 해당 토마토가 다른 토마토를 익게 할 때 큐에서 빠지는 로직이 형성이 될 텐데, 그때 현재 토마토의 위치를 파악할 때 사용할 예정입니다. 자세한 설명은 하단에서 할게요😄

 

Setting📘

public class Tomato {
    static int[] dx = {-1, 0 ,1 ,0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board, date;
    static int n, m;
    static Queue<TomatoPoint> Q = new LinkedList<>();
    
    public static void main(String[] args) {
        Tomato T = new Tomato();
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt(); // 열
        n = sc.nextInt(); // 행
        board = new int[n][m];
        date = new int[n][m];
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                board[i][j] = sc.nextInt();
                if(board[i][j] == 1) {
                    Q.offer(new TomatoPoint(i, j));
                }
            }
        }
        T.BFS();
    }
}

static으로 선언된 dx, dy는 각각 상자판에서 세로, 가로축을 의미하며 상하좌우 4방향을 바라볼 때 사용됩니다. 이 부분은 하단 BFS 함수에서 설명드릴게요.

 

이중배열인 board는 토마토가 담기는 상자판을 의미하고, date는 인근 토마토에 의해 변한 날짜를 담습니다. 예시로 A,B,C 토마토가 일렬로 있고 A가 익은 토마토라고 가정했을 때, date 배열에 A 위치에는 0, B 위치에는 1, C 위치에는 2가 입력됩니다(한번 이동할 때마다 하루가 지난다고 가정하는 것이기 때문에)

 

int n과 m은 각각 행과 열을 뜻합니다. 주의할 점은 행은 세로축, 열은 가로축이기 때문에 배열을 선언할 때 사이즈를 반대로 넣어주어야 합니다. 마지막으로 Queue도 static으로 선언하였는데, 이전 미로 찾기에서는 BFS 함수 안에서 선언하였지만 이번 문제는 시작점이 여러 군대이기 때문에 main에서 상자판이 1로 된(= 토마토가 익은 곳) 곳을 모두 큐에 쌓아야 하기 때문에 전역으로 쓰기 위해서 static으로 선언하였습니다.

---

main을 보면 Scanner를 이용하여 각각의 값들을 입력 받고, 이중배열인 board와 date는 판을 의미하기 때문에 행(n), 열(m) 사이즈만큼 선언하여 줍니다.

 

반복문을 통해 상자판을 만들고 이전에 언급했듯이, 이미 익은 토마토를 의미하는 1인 곳들을 Q에 쌓아줍니다. 이후에 BFS 함수를 실행시킵니다.

 

📌 예제를 보면 1인 곳(토마토가 익은 곳)은 2군대로 설정되어 있기 때문에 맨 처음 Queue에는 (1,2)와 (3,5)가 들어가 있습니다.

 

BFS📒

public void BFS() {
    while(!Q.isEmpty()) {
        TomatoPoint tmp = Q.poll();
        for(int i = 0; i < 4; ++i) {
            int nx = tmp.x + dx[i];
            int ny = tmp.y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m
                    && board[nx][ny] ==0) {
                board[nx][ny] = 1;
                Q.offer(new TomatoPoint(nx, ny));
                date[nx][ny] = date[tmp.x][tmp.y] + 1;
            }
        }
    }
}

BFS 함수는 while문을 이용하여 구현됩니다. 현재 Q에는 2가지 시작점이 들어가 있기 때문에 따로 인자값을 받아서 넣어줄 필요가 없습니다.

 

while문은 Queue가 비어있을 때까지 돌아가는데 첫 번째 값을 Q에서 꺼내 tmp라는 변수에 담아주었습니다. 그리고 반복문을 통해 4가지 상하좌우 방향을 확인합니다.

 

예시로, 맨 처음 시작점 tmp는 (1,2)가 꺼내집니다. 그러면 int nx = (tmp.x = 1) + (dx[0] = -1) : 0이 됩니다. 마찬가지로 int ny = (tmp.y = 3) + (dy[0] = 0) : 3이 됩니다. 결과적으로 (0,3)을 바라본다는 뜻이고 tmp 관점에서 12시 방향을 바라보고 있다는 것입니다.

 

반복문을 순차적으로 돌려보시면 12시 방향, 3시 방향, 6시 방향, 9시 방향을 확인하는 것을 알 수 있습니다. 하지만 여기서 if 조건문을 보면 nx가 0 이상 n(행의 끝) 미만이어야 하는데, 이 부분은 상자판의 테두리 부분에서 상자 밖을 쳐다보지 않기 위해서 설정한 것입니다.

 

또한, board[nx][ny] == 0 이라는 조건은 인근에 있는 토마토가 0일 때 즉, 익지 않은 토마토일 때만 진행시켜야 하기 때문입니다. 이미 익은 토마토(1)나 비어 있는 곳(-1)은 확인할 필요가 없기 때문입니다.

 

if 조건문을 통과했다는 것은 성공적으로 익지 않은 토마토를 찾았다는 뜻입니다. 찾은 곳은 1로 세팅하여 토마토가 익었음을 표시해 주고, Q에 해당 토마토 좌표를 넣어줍니다.

 

마지막으로 date 이중배열에 현재 값보다 +1 한 숫자를 넣어줍니다. 이 부분은 맨 처음 date 배열은 0으로 초기화되어 있습니다. 시작점에서 안 익은 토마토를 발견했을 때 +1 하여 1을 넣어줍니다. 이 과정을 계속해서 반복하면 date 이중배열 안에 최댓값이 어딘가에 남게 됩니다. 그러면 그 부분이 전체 토마토가 익을 때까지 걸린 날짜입니다.

 

이해가 안 되신다면 board(상자 판), date(상자 판과 같은 크기의 날짜 체크 판)을 그리시고 예제 값을 넣어서 시뮬레이션을 직접 돌려보시는 것을 추천드립니다😄

 

출력📗

... // main 이어서
T.BFS();
boolean flag = true;
int result = Integer.MIN_VALUE;
for(int i = 0; i < n; ++i) {
    for(int j = 0; j < m; ++j) {
        if(board[i][j] == 0) {
            flag = false;
        }
    }
}
if(flag) {
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            result = Math.max(result, date[i][j]);
        }
    }
    System.out.println(result);
} else {
    System.out.println(-1);
}

출력 부분은 코드가 길어서 main을 분리하였습니다. 문제에서 출력은 만약 토마토가 끝내 익지 못하는 경우에는 -1을 출력하고, 맨 처음부터 모두 익은 토마토였다면 0을 출력, 이외에는 모든 토마토가 익기까지의 최소 날짜를 출력하라고 하였습니다.

 

boolean 타입의 flag 변수를 true로 설정하고 반복문을 통해 상자판에 모든 곳을 탐색합니다. if 조건문으로 0인 곳을 발견 즉, 토마토가 익지 못한 곳을 발견한다면 flag 변수를 false로 지정합니다.

 

하단에는 flag가 true일 때만 즉, 모든 토마토가 익었을 때의 경우입니다. 다시 반복문을 돌면서 이번에는 result 값에 date 배열에 있는 값들을 비교하여 최대 값을 매칭시킵니다. 

 

📌 여기서 포인트는 만약 처음부터 모든 토마토가 익어있는 상태라면 어차피 date 이중배열을 선언 시에 0으로 다 초기화되어 있는 상태이기 때문에 모든 상자를 비교하더라도 최댓값은 0으로 나옵니다. 즉, 문제 내용의 일부인 맨 처음부터 모두 익은 토마토였다면 0을 출력하는 부분을 해결함과 동시에 처음에 안 익은 토마토가 있을 경우도 같이 처리가 됩니다

 

else 부분에는 안 익은 토마토가 있다는 경우이기 때문에 -1을 출력해 주면 됩니다.

 

Result📔

테스트 결과

문제 입력에 맞게 입력하니 토마토가 모두 익는 최소 날짜인 4를 출력하는 것을 확인할 수 있었습니다.

 

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

지금까지 BFS를 활용해서 토마토 문제를 풀어보았습니다. 이전 포스팅 미로의 최단 경로와 상당히 유사하기 때문에 링크를 클릭하셔서 비교해 보는 것도 좋은 공부 방법이라고 생각이 드네요. 다음 포스팅에 뵐게요😊