글 읽기 - 불먼저 탐색했고, 테스트케이스마다 초기화도 했다고 생각합니다. 고수님들 도와주세요

gksgml1830 1년 전 0

불이 퍼져가는 것을 먼저 구했고, 상근이의 이동을 구했습니다. (bfs)

매번(테스트케이스마다) 초기화도 했다고 생각합니다..!

https://www.acmicpc.net/board/...

해당 링크에 주어진 테스트 케이스를 시행했을 때 문제가 없었습니다.

어디서 잘못된 것인지 알 수 없어 질문 남깁니다..!

도움 부탁드립니다 !!

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

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


public class Main {
    static int T, w, h;
    static char[][] building;
    static boolean[][] visited, visited2;
    static int[][] dist, fireDist;
    static Queue<Position> queue = new LinkedList<>();
    static Queue<Position> queue2 = new LinkedList<>();
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

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

        for(int i=0; i<T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            building = new char[h][w];
            //방문기록 초기화
            visited = new boolean[h][w];
            visited2 = new boolean[h][w];
            //거리 초기화
            dist = new int[h][w];
            fireDist = new int[h][w];

            for(int j=0; j<h; j++) {
                String str = br.readLine();
                for(int k=0; k<w; k++) {
                    building[j][k] = str.charAt(k);
                    if(building[j][k] == '*') {
                        queue.add(new Position(j, k));
                        visited[j][k] = true;
                    }
                    if(building[j][k] == '@') {
                        queue2.add(new Position(j, k));
                        visited2[j][k] = true;
                    }
                }
            }

            //먼저 불이 퍼져가는 시간 구하기 
            moveFire();

            escape();

            //queue 초기화
            queue = new LinkedList<>();
            queue2 = new LinkedList<>();

        }

    }

    static void moveFire() {
        while(!queue.isEmpty()) {
            Position out = queue.poll();

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

                if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                else if(visited[nx][ny] || building[nx][ny] == '#') continue;
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                    fireDist[nx][ny] = fireDist[out.x][out.y] + 1;
                }
            }
        }
    }

    static void escape() { //불보다 늦게 도착할 때도 넘어가야쥐..
        boolean flag = false;

        while(!queue2.isEmpty()) {
            Position out = queue2.poll();

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

                if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
                    System.out.println(dist[out.x][out.y]+1);
                    flag = true;
                    return ;
                }
                else if(visited2[nx][ny] || building[nx][ny] == '#') continue;
                else if(fireDist[nx][ny] != 0 && fireDist[nx][ny] <= dist[out.x][out.y]+1) continue;
                else {
                    queue2.add(new Position(nx, ny));
                    visited2[nx][ny] = true;
                    dist[nx][ny] = dist[out.x][out.y] + 1;
                }
            }

        }

        if(!flag)
            System.out.println("IMPOSSIBLE");
        return ;

    }
    
}

gksgml1830 1년 전 0

104번째 줄에서 불을 만났을 때도 continue를 해주니 해결되었습니다 !

else if(visited2[nx][ny] || building[nx][ny] == '#') continue;

else if(visited2[nx][ny] || building[nx][ny] == '#' || building[nx][ny] == '*') continue;

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

문제

문제

출처

ICPC

불먼저 탐색했고, 테스트케이스마다 초기화도 했다고 생각합니다. 고수님들 도와주세요

gksgml1830 1년 전 0

gksgml1830 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말