[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)7576번, 토마토

문제 링크

7576번: 토마토

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 0은 익지 않은 토마토, 1은 익은 토마토, -1은 토마토가 존재하지 않는다.

2. 1에 인접한 0인 칸들은 익게된다.

3. 모든 토마토가 익으면 최소 날짜를 출력하고 익지 못하면 -1을 결과로 출력해야 합니다.

 

저는 BFS(너비우선탐색)을 이용하여 문제를 해결하였습니다.

창고의 익은 토마토를 기준으로 상, 하, 좌, 우로 탐색을 진행하여 탐색이 끝났을 때 모든 토마토가 익었는지 확인합니다.

상, 하, 좌, 우로 탐색하기 위해서

 

dx[] = {-1, 1, 0, 0}

 

dy[] = {0, 0, -1, 1}

 

두 가지 배열을 사용하여 상, 하, 좌, 우로 넓이 탐색을 진행하였습니다.

check배열을 통해서 창고에 해당 지점을 탐색했는지를 확인하였습니다.

예제입력1에서 창고를 BFS로 진행하는 과정을 보여드리겠습니다.(빨간색은 탐색 완료 지점)

0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	1

(3,5)좌표를 탐색하겠습니다.

저는 상, 하, 좌, 우 순으로 깊이탐색을 진행합니다.

'상'

3 + dx[0] = 3 + (-1) = 2

5 + dy[0] = 5 + 0 =  5

해당 지점은 0으로써 익지 않은 토마토로 접근 가능

'하'

3 + dx[1] = 3 + 1 = 4

50 + dy[1] = 5 + 0 = 5

창고의 범위를 벗어나기 때문에 탐색이 되지 않습니다.

'좌'

3 + dx[2] = 3 + 0 = 3

5 + dy[2] = 5 + -1 = 4

해당 지점은 0으로써 익지 않은 토마토로 접근 가능

'우'

3 + dx[3] = 3 + 0 = 3

5 + dy[3] = 5 + 1 = 6

지도의 범위를 벗어나기 때문에 탐색이 되지 않습니다.

다음 (2,5)와 (3,4)에 상,하,좌,우 범위탐색을 이어나가면

0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	1
0	0	0	0	1	1

(2,5)에서는 '하','우'는 조건에 불만족하기 때문에 '상','좌'를 탐색합니다.

(3,4)에서는 '상','하','우'는 조건에 불만족하기 때문에 '좌'를 탐색합니다.

0	0	0	0	0	0
0	0	0	0	0	1
0	0	0	0	1	1
0	0	0	1	1	1

이 과정을 반복하면 결과적는

1	1	1	1	1	1
1	1	1	1	1	1
1	1	1	1	1	1
1	1	1	1	1	1

 

범위 탐색을 각 단계마다 1일로 계산하여 BFS가 끝나면 창고에 값이 0이 존재하는지 확인하고 0이 존재하지 않는다면 몇 일동안 범위 탐색을 하였는지를 계산하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 창고의 토마토 관련 값을 배열에 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 상, 하, 좌, 우 순으로 탐색을 진행합니다.

3. BFS종료시 창고에 토마토가 모두 1이 되있으면 범위 탐색 횟수를 출력하고 0이 존재하면 -1을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 창고의 값을 저장하였습니다.
• 좌표를 저장하는 생성자 coordinate를 만들었습니다.
• BFS로 창고를 탐색하는 bfs 함수를 만들었습니다.
• 창고에 모든 토마토가 익었는지 확인하는 isFull 함수를 만들었습니다.
• BufferedWriter에 모두 익었으면 최소 기간, 익지 않았다면 -1을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs은 check[], dx[],dy[],box[][]와 Queue를 통해 땅을 상,하,좌,우로 탐색하였습니다.
• isFull은 2중 반복문을 통해 창고의 토마토가 모두 익었는지 확인하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//-------좌표 생성자---------
	public static class coordinate{
		int x,y;
		public coordinate(int x, int y) {
			this.x = x;
			this.y = y;
		}
		public int getX() {
			return x;
		}
		public int getY() {
			return y;
		}
	}
	public static int N,M;
	public static int[][] box;	//창고 값 저장 배열
	public static boolean[][] check;	//창고 지점 탐색 확인 배열
	public static int[] dx = {-1, 1, 0, 0};		//상,하,좌,우 X 변경값
	public static int[] dy = {0, 0, -1, 1};		//상,하,좌,우 Y 변경값
   	 //BFS에 사용될 큐
	public static Queue<coordinate> queue = new LinkedList<coordinate>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화----------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	box = new int[M][N];
    	check = new boolean[M][N];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<N;j++) {
    			int num = Integer.parseInt(st.nextToken());
    			if(num == 1)
    				queue.add(new coordinate(i, j));
    			else if(num == -1) {
			/*
                    	입력값이 -1일 때 탐색하지 못하는 지점으로
                    	check를 true로 변경해주었으며
                    	마지막에 창고에 모든 토마토가 익었는지 확인하기 때문에
                   	값을 1로 저장하도록 하였습니다.
                    	*/
    				num=1;
    				check[i][j] = true;
    			}
    			box[i][j] = num;
    		}
    	}
    	int result = bfs();		//BFS 함수 실행
    	if(isFull()) {		//모든 토마토가 익었을 때
    		bw.write(result + "\n");	//최소 기간 BufferedWriter 저장
    	}else		//익지않은 토마토가 존재할 때
    		bw.write("-1");		//-1을 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();

    }
    //--------BFS를 통한 창고 탐색함수-------
    public static int bfs() {
    	int count = -1;
        /*
        count를 -1로 초기화한 이유는
        창고의 처음 토마토는 하루가 지나서 익은 것이 아닌
        처음부터 익어져 있기 때문에
        첫 날의 탐색은 넘어가고 다음부터 +1을 하였습니다.
        */
    	while(!queue.isEmpty()) {		//BFS 탐색
    		int size = queue.size();
    		for(int i=0;i<size;i++) {
        		coordinate temp = queue.poll();
        		int x = temp.getX();
        		int y = temp.getY();
        		check[x][y] = true;
        		for(int j=0;j<4;j++) {
        			int tempX = x + dx[j];		//상,하,좌,우 X값 변경
        			int tempY = y + dy[j];		//상,하,좌,우 Y값 변경
        			if(tempX>=0 && tempX<M && tempY>=0 && tempY<N) {
        				if(!check[tempX][tempY] && box[tempX][tempY]==0) {
                        			//익지않은 인접한 토마토 찾을 경우
        					queue.add(new coordinate(tempX, tempY));
        					box[tempX][tempY] = 1;
        				}
        			}
        		}
    		}
    		count++;
    	}
    	return count;
    }
    //-------창고에 토마토가 다 익었는지 확인하는 함수------
    public static boolean isFull() {
    	for(int i=0;i<M;i++) {
    		for(int j=0;j<N;j++) {
        		if(box[i][j]!=1)
        			return false;
    		}
    	}
    	return true;
    }
}