글 읽기 - 반례를 못찾겠습니다 ㅠㅠ

sodp5 4년 전 1

로직은 이렇습니다.

1. 상근이가 가장자리에 있는 경우 1을 출력합니다.

2. 불꽃을 사방으로 번지게 합니다. (벽 제외)

3. 상근이는 방문한적 없는 곳 (불붙은 곳, 자신이 지났던곳을 제거하기 위함) 과 벽을 제외한 사방으로 이동합니다.

4. 이동할 공간이 출구인 경우 +1 한 후 종료합니다.

제가 미처 발견하지 못한 반례가 무엇이 있을까요?ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }

    class Node {
        int y;
        int x;
        int hour;

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

    boolean[][] visit;
    int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int R;
    int Y;
    int X;

    int result = 0;

    String[][] map;

    int startY;
    int startX;

    ArrayList<Node> fireList = new ArrayList<>();
    ArrayList<Node> endList = new ArrayList<>();

    void solve() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            R = Integer.parseInt(br.readLine());
            for (int r = 0; r < R; r++) {
                String[] splits = br.readLine().split(" ");
                X = Integer.parseInt(splits[0]);
                Y = Integer.parseInt(splits[1]);

                visit = new boolean[Y][X];
                map = new String[Y][X];
                fireList.clear();
                endList.clear();

                result = 0;

                for (int y = 0; y < Y; y++) {
                    splits = br.readLine().split("");
                    for (int x = 0; x < X; x++) {
                        map[y][x] = splits[x];
                        if (map[y][x].equals("@")) {
                            startY = y;
                            startX = x;
                            visit[y][x] = true;
                        }

                        if ((y == Y - 1 || x == X - 1 || y == 0 || x == 0) && map[y][x].equals(".")) {
                            endList.add(new Node(y, x, 1));
                        }

                        if (map[y][x].equals("*")) {
                            fireList.add(new Node(y, x, 1));
                            visit[y][x] = true;
                        }
                    }
                }

                if (startY == Y - 1 || startY == 0 ||
                        startX == X - 1 || startX == 0) {
                    System.out.println(1);
                    continue;
                }

                Queue<Node> queue = new ArrayDeque<>(fireList);
                queue.offer(new Node(startY, startX, 1));

                while (!queue.isEmpty()) {
                    int size = queue.size();
                    for (int i = 0; i < size; i++) {
                        if (queue.isEmpty()) {
                            break;
                        }
                        Node item = queue.poll();
                        int newY;
                        int newX;

                        for (int k = 0; k < 4; k++) {
                            newY = item.y + direction[k][0];
                            newX = item.x + direction[k][1];

                            if (newY >= Y || newY < 0 || newX >= X || newX < 0 ||
                                    visit[newY][newX] || map[newY][newX].equals("#")) {
                                continue;
                            }

                            if (map[newY][newX].equals(".")) {
                                map[newY][newX] = map[item.y][item.x];

                                queue.offer(new Node(newY, newX, item.hour + 1));
                                visit[newY][newX] = true;

                                for (Node n : endList) {
                                    if (map[newY][newX].equals("@")) {
                                        if (newY == n.y && newX == n.x) {
                                            result = item.hour + 1;
                                            queue.clear();
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }


                if (result == 0) {
                    System.out.println("IMPOSSIBLE");
                } else {
                    System.out.println(result);
                }

            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

myeongbo123 4년 전 0

입력

1
12 5
############
#.#....@..##
#....#.#...#
.#..##...##.
.#..#####.#.

correct answer : 8

your answer : 9

x=0 또는 x=X-1지점 또는 y=0 또는 y=Y-1 지점에 도달해도 주위에 갈 수 있는 지점을 살피고 큐에 넣어버려서 생긴 문제 같습니다.목표 지점에 도착하면 바로 while문을 빠져나가도록 수정하면 될 거 같습니다. 또한 endList는 딱히 필요가 없는게 '@'가 x=0 또는 x=X-1지점 또는 y=0 또는 y=Y-1 지점에 도달하기만 하면 바로 걸린 시간 출력하면 되기 때문에 굳이 endList에 값들을 넣을 필요가 없습니다.

sodp5 4년 전 0

감사합니다! 해결했어요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못찾겠습니다 ㅠㅠ

sodp5 4년 전 1

myeongbo123 4년 전 0

myeongbo123 4년 전 2

sodp5 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말