[알고리즘] 백준 7576 토마토 -bfs, dfs-

 

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

7576번: 토마토

 

 

 

예제입력도 다 맞는데 제출에서 70%대쯤에서 계속 틀렸다고 떠서 삽질 좀 했다... (반례를 찾을 수 도 없고)

=> 출력쪽에 실수가 있었다. 

그리고 행열 관련해서 한 부분을 거꾸로 for문 돌리는 실수도 했었다. (왜 이렇게 실수를 많이할까)

결국 해결하긴 했지만 시간을 많이 잡아먹은 것 같다. 

 

기존 입력 예제말고 내가 추가해본 입력 예제는 다음과 같다.

2 2
-1 -1
-1 -1

 

2 2

0 0

0 0

 

문제의 특징은 이전 단계 문제인 미로탐색처럼 BFS 탐색을 하며 인접배열로 이동할 경우 이전 값의 +1 하는 것은 똑같은데 미리 익은 토마토의 위치를 Queue에 넣어주어야 했습니다.

그리고 토마토가 다 안익는 경우나 못익는 경우 같은 특이 케이스를 처리해줘야 했습니다.

https://youngest-programming.tistory.com/195?category=873090

[알고리즘] 백준 2178 미로 탐색 -bfs, dfs-

 

 

 

다음과 같이 문제를 해결했습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

    private static int[][] map;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};
    private static Queue<Point> queue = new LinkedList<>();
    private static TreeSet<Integer> resultTreeSet = new TreeSet<>();
    private static int N;
    private static int M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 열(2차원) 6
        M = sc.nextInt(); // 행(1차원) 4

        map = new int[M + 2][N + 2];

        //맵 세팅
        for (int i = 1; i < M + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1) {
                    queue.offer(new Point(i, j));
                }
            }
        }

        //모두 들어있지 않은 칸이거나 0인 경우
        if (queue.isEmpty()) {
            System.out.println(-1);
            return;
        }

        //바깥쪽 멥은 -1로 세팅 (사방히막힌 경우 구하기위해)
        for (int i = 0; i < N + 2; i++) {
            map[0][i] = -1;
            map[M + 1][i] = -1;
        }
        for (int i = 0; i < M + 2; i++) {
            map[i][0] = -1;
            map[i][N + 1] = -1;
        }

        //순차적 탐색
        bfs();

        //결과
        for (int i = 1; i < M + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                if (map[i][j] == 0) { //익지못한 토마토있는 경우
                    System.out.println(-1);
                    return;
                }
            }
        }
        if (resultTreeSet.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(resultTreeSet.last() - 1);
        }

    }


    private static void bfs() {
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];

                //익지않은 토마토만 탐색
                if (map[x2][y2] == 0) {
                    queue.offer(new Point(x2, y2));
                    if (i == 0) { //왼쪽으로 이동한 상태
                        map[x2][y2] = map[x2 + 1][y2] + 1;
                    } else if (i == 1) {//상단으로 이동한 상태
                        map[x2][y2] = map[x2][y2 + 1] + 1;
                    } else if (i == 2) {//오른쪽으로 이동한 상태
                        map[x2][y2] = map[x2 - 1][y2] + 1;
                    } else {//밑으로 이동한 상태
                        map[x2][y2] = map[x2][y2 - 1] + 1;
                    }
                    resultTreeSet.add(map[x2][y2]);
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

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

 

 

 

 

[2020-09-18 복습]

위에 코드에서 쓸데 없는 동서남북에 대한 if 문하고 이상한 부분이 많더라고요... 저떈 왜저렇게 풀었지..?(지금코드가 좋은건아니지만연 ㅎㅎ)

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;

/*
*
* 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
*/
public class Main {

    private static int N; //1차원
    private static int M; //2차원
    private static int[][] map;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};
    private static TreeSet<Integer> resultTreeSet = new TreeSet();
    private static Queue<Point> queue = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        map = new int[N + 2][M + 2];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1) {
                    queue.offer(new Point(i, j));
                }
            }
        }
        for (int i = 0; i < N + 2; i++) {
            map[i][0] = -1;
            map[i][M + 1] = -1;
        }
        //바깥쪽 -1세팅
        for (int i = 0; i < M + 2; i++) {
            map[0][i] = -1;
            map[N + 1][i] = -1;
        }
        //탐색
        bfs();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 0) { //익지 못하는 상황
                    System.out.println(-1);
                    return;
                }
            }
        }
        if (resultTreeSet.isEmpty()) { // 모드 토마토가 익어있는 상태
            System.out.println(0);
        } else {
            System.out.println(resultTreeSet.pollLast() - 1);
        }
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if (map[x2][y2] == 0) {
                    map[x2][y2] = map[point.x][point.y] + 1;
                    resultTreeSet.add(map[x2][y2]);
                    queue.offer(new Point(x2, y2));
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

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


}