글 읽기 - 4179 불! 질문 있습니다

sheepbomb 5년 전 0

큐 두개를 활용해 불을 먼저 퍼트리고 , 그다음에 사람을 움직이게 하였습니다.

클리어 조건은 맵의 최외곽이면서 동시에 불 혹은 X가 안쳐져 있는 곳이므로 해당 조건에 클리어 시키는 방법으로 짰습니다.

다만 불을 또하나의 벽이라고 생각하여 불을 퍼트릴때 Map에다가 벽이랑 같은 값을 넣었는데 이것이 혹시나 문제를 일으키나요?

도움 부탁드리겠습니다

package com.algoFactory.baekjoonAlgo;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class a_4179 {
    private static int[][] Map;
    private static int[][] Visited;
    private static int[] directionX = {-1,0,1,0};
    private static int[] directionY = {0,1,0,-1};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Map = new int[N][M];
        Visited = new int[N][M];
        int result = 0;
        Queue<Point> userPosition = new LinkedList<>();
        Queue<Point> firePosition = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            String string = new String(br.readLine());
            for (int j = 0; j < M; j++) {
                char ch = string.charAt(j);
                if (ch=='#')    Map[i][j] = -1;
                else if (ch == 'J') {
                    userPosition.add(new Point(i,j));
                    Visited[i][j] = 1;
                }
                else if (ch == 'F'){
                    firePosition.add(new Point(i,j));
                    Map[i][j] = -1;
                }else   Map[i][j] = 0;
            }
        }

        while (!userPosition.isEmpty()){
            int userQueueSize = userPosition.size();
            int fireQueueSize = firePosition.size();

            while (fireQueueSize!=0){    //불 퍼트리기
                Point point = firePosition.poll();
                fireQueueSize--;
                for (int i = 0; i < directionX.length; i++) {
                    int nextX = point.x + directionX[i];
                    int nextY = point.y + directionY[i];
                            if (nextX >=0 && nextX < N && nextY >=0 && nextY < M){    //불은 Map의 inbound안에만 있으면됨.
                                if (Map[nextX][nextY]!=-1){
                                    Map[nextX][nextY] = -1;
                                    firePosition.add(new Point(nextX,nextY));
                        }
                    }
                }
            }

            while (userQueueSize!=0){    //사람 퍼트리기
                Point point = userPosition.poll();
                userQueueSize--;
                for (int i = 0; i < directionX.length; i++) {
                    int nextX = point.x + directionX[i];
                    int nextY = point.y + directionY[i];
                    if (nextX >0 && nextX < N-1 && nextY >0 && nextY < M-1){    //positioning inner wall
                        if (Map[nextX][nextY]!=-1 && Visited[nextX][nextY] != 1){   //Not wall , Not visited
                            Visited[nextX][nextY] = 1;
                            userPosition.add(new Point(nextX,nextY));
                        }
                    }else if (Map[nextX][nextY]!=-1){    //사람의 다음 포지션이 맵의 외곽이면서 불 or 벽이 아니면 출력하고 종료.
                        result++;
                        System.out.println(result);
                        return;
                    }
                }
            }
            result++;    //사람을 한번 퍼트릴때마다 가지수를 1씩 증가
        }
        if (userPosition.isEmpty()){
            System.out.println("IMPOSSIBLE");
        }

    }

    private static class Point{
        int x,y;

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

sheepbomb 5년 전 0

문제 이해를 잘못했네요.

맵의 외곽에 위치한 다고 탈출이 아니라 맵의 외곽에서 한턴 더나아가야 해결하는 방법으로 해결했습니다.

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

문제

문제

출처

ICPC

4179 불! 질문 있습니다

sheepbomb 5년 전 0

sheepbomb 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말