백준 문제 풀이 : 2178 미로탐색 7576 토마토

이번에 BFS 문제를 풀면서 가장 크게 느낀것은 BFS 와 DFS 모두를 능숙히 사용할 수 있어야하고, 문제에 따라서 어떤 방법을 써야하는지 잘 고민해봐야한다는 것!

1. 2178 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

이 문제는 DFS 가 아닌 BFS 로 풀어야하는 문제였다.

나는 그것도 모르고 DFS 로 풀었었는데 당연히 시간 초과가 나왔다ㅠ 생각해보니 최소 도착 거리(시간?) 인 만큼 BFS 로 푸는게 맞다 싶어서 얼른 코드를 뜯어고쳤다.

 

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/2178
public class Quiz_2178_bfs {
    static int[][] maze; // 미로
    static int[][] dis; // 시작점부터 도착점까지의 거리
    static int[] dx = {-1, 0, 1, 0}; // 좌 우
    static int[] dy = {0, 1, 0, -1}; // 상 하

    static int n, m;

    public static void findExit(int x, int y){
        Queue<Point> q = new LinkedList<Point>();
        q.offer(new Point(x, y)); // x, y 좌표를 갖는 point 를 queue 에 넣는다

        while (!q.isEmpty()) {
            Point now = q.poll(); // queue 의 가장 앞에 것을 빼서 now 변수에 저장

            for(int i=0; i<4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                // nx ny 는 모두 0 모다 크고, 각각 n 과 m 보다 작아야한다
                // 동시에 maze[nx][ny] 가 1 이여야만 갈 수 있다
                if(nx >0 && ny >0 && nx <= n && ny <= m && maze[nx][ny] == 1){
                    maze[nx][ny] = 0; // 방문했음을 확인하기 위해 0 으로 변경
                    q.offer(new Point(nx, ny)); // 방문한 좌표를 queue 에 저장
                    dis[nx][ny] = dis[now.x][now.y] +1; // 방문한 곳까지의 거리는 현재 좌표까지의 거리+1
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input); // String 을 나누기 위한 StringTokenizer
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        //System.out.println(n + " : " + m);

        maze = new int[n+1][m+1]; // 미로는 1,1 부터 시작임으로 n+1, m+1 만큼의 크기로 선언
        dis = new int[n+1][m+1]; // 거리는 미로와 동일한 크기로 선언

        for(int i=1; i<=n; i++){

            char[] ch = br.readLine().toCharArray(); // 입력받은 미로의 값들을 char 배열로 저장
            //System.out.println(Arrays.toString(ch));
            //System.out.println(maze.length);
            //System.out.println(maze[i].length);

            for(int j=0; j<ch.length; j++){
                maze[i][j+1] = (int)ch[j] - 48; // char 배열에서 하나씩 꺼내서 int 로 변환하여 int 형 maze 배열에 저장
                //maze[i][j] = 1;
            }
//            System.out.println("");
//            System.out.println(Arrays.toString(maze[i]));
        }

        // 미로에서 시작점은 1,1 => 따라서 1,1 은 항상!! 방문한 상태임
        // 따라서 dis[1][1] 에서의 시작 거리(값)는 1
        maze[1][1] = 0;
        dis[1][1] = 1;
        findExit(1, 1);

        System.out.println(dis[n][m]);
    }
}

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

 

이상해서 2번이나 돌렸는데...

---

2. 7576 토마토

이 문제는 사실 미로 문제와 거의 코드가 비슷하다

사실 처음에 내가 문제를 이해를 못해서...놓친 부분들이 많았다.

- 첫째로 값이 1인 토마토 하나가 익은 후 다른 값이 1인 토마토가 익는 것이 아니라, 1인 토마토는 동시에! 다음날이 되면 옆에 토마토를 동시에! 익게 만든다는 것이다 => 이상하게 이 부분이 헷갈려서...

-  둘째로 토마토가 하나라도 익지 못하는 경우 와 모든 토마토가 이미 익어져 있는 경우를 잘 구분해야한다. 사실 다 풀어놓고 이 부분이 도저히 생각이 안나서 많이 고민했었다.

package baekJoon;

import java.io.IOException;
import java.util.*;

// https://www.acmicpc.net/problem/7576
public class Quiz_7576 {
    static int[] dx = {1, -1, 0, 0}; // 좌 우
    static int[] dy = {0, 0, 1, -1}; // 상하
    static int[][] tomato; // 토마토 배열
    static int n, m; // 토마토 열, 행
    static Queue<PointTomato> q = new LinkedList<PointTomato>();
    static int result = Integer.MIN_VALUE;

    static void findDay() {
        while(!q.isEmpty()){ // queue 에 내용이 없을때까지 반복
            PointTomato now = q.poll(); // queue 의 가장 앞에 것을 꺼내서 저장
            int day = now.day; // 현재 날짜
            int nowX = now.x; // x 좌표
            int nowY = now.y; // y 좌표

            for(int i=0; i<4; i++){
                int nx = nowX + dx[i]; // 현재 좌표에서 dx 만큼 움직인 x
                int ny = nowY + dy[i]; // 현재 좌표에서 dy 만큼 움직인 y

//                System.out.println("nx : "+nx);
//                System.out.println("n : "+n );

                // nx ny 는 각각 0보다 크거나 같고, n 과 m 보다 작아야함
                // 또한 값이 0인 토마토만 익을 수 있음 => 방문 가능
                if(nx >=0 && ny >= 0 && nx < n && ny<m && tomato[nx][ny] == 0 ){
                    tomato[nx][ny] = 1; // 토마토가 익음 => 방문
                    q.offer(new PointTomato(nx, ny, day+1)); // queue 에 nx, ny, 현재 날짜 +1
                    result = Math.max(result, day+1); // 결과 값에 result 와 현재 날짜 +1 중 큰 값을 비교

                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        m = scan.nextInt();
        n = scan.nextInt();

        tomato = new int[n][m]; // 토마토 배열
        boolean flag = false; // 익어야하는 토마토가 있는지 확인하기 위한 flag

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                int toma = scan.nextInt();
                tomato[i][j] = toma; // 배열에서 하나를 꺼내서 저장

                if(toma == 1){
                    // 하나를 꺼냈을 때 1이면 queue 에 넣기 => 왜냐하면 배열의 위치가 어디던 상관없이
                    // 익은 토마토 인 1부터 시작해서 다른 토마토가 익어야 함으로
                    q.add(new PointTomato(i, j, 0));
                }else if(toma==0){
                    // 만약 0이 하나라도 tomato 배열에 들어왔다면 익을 수 있는 토마토가 있는 것임으로
                    // flag 를 true 로
                    flag = true;
                }
            }
        }
        findDay();

        if(flag){ // flag 가 true 인 경우 익을 수 있는 토마토가 하나라도 있는 것임으로 최대 일 수 꼐산
            result = Math.max(result, new PointTomato().day);
        }else{
            // flag 가 false 인 경우 1 과 -1 만 들어가 있는 상태, 따라서 모든 토마토가 익은 토마토!!
            // 따라서 결과값은 0
            result = 0;
        }

        // 만약 메서드 실행후에도 tomato 배열안에 0이 하나라도 있는 경우 => 익을 수 있는 토마토가 남아있는 경우
        // 토마토가 모두 익지 못하는 상황임으로 결과값은 -1
       for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if (tomato[i][j] == 0) {
                    result = -1;
                    break;
                }
            }
        }


        System.out.println(result);
    }
}

class PointTomato {
    int x, y;
    int day = 1;
    PointTomato(){};
    PointTomato(int x, int y, int day) {
        this.x = x;
        this.y = y;
        this.day = day;
    }
}