불!4179

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

처음에는 불을 한칸 확장 시키고

지훈을 BFS로 가장 가까운 외곽경로를 찾은뒤에 한칸만 이동

하도록 반복하면 되지 않나 싶었다 그래서 만들었더니 틀리다고 한다

생각해보니 위와 같은 경우 J는 위로 가려고 할것이고(BFS로 찾으면 위가 최단경로니까) 그리고 그림처럼 결국 불에 갇혀 죽게된다
첨부터 오른쪽으로 가면 탈출 가능하다.

그래서 한참 고민하고 방법을 바꿨다
불도 한칸씩 확장하고 J도 한칸씩 확장하는 방식이다. 지훈을 먼저 확장시키고 그 다음에 불이 확장되면서 뒤덮게 된다

저렇게 J를 확장하면 결국 오른쪽으로 쭉 가서 외곽에 닿게 된다
생각의 방향은 맞는것 같다
근데 시간초과가 나온다 더이상 줄일 수 있는 방법을 못찾았다
코드는 다음과 같다. 이걸 개선해서 푸는게 가능할지 모르겠다.

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

class Pos
{
    int r;
    int c;

    public Pos() {
    }

    public Pos(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main
{
    static int testcode = 0;

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

        String[] input = br.readLine().split(" ");

        int R = Integer.parseInt(input[0]);
        int C = Integer.parseInt(input[1]);

        int [][] miro = new int[R][C];

        Pos ji = null;
        for(int i = 0; i < R; ++i)
        {
            input = br.readLine().split("");
            for(int j = 0; j < C; ++j)
            {
                if(input[j].equals("."))
                    miro[i][j] = 0;
                else if(input[j].equals("J"))
                {
                    miro[i][j] = 1;
                    ji = new Pos(i, j);
                }
                else if(input[j].equals("F"))
                    miro[i][j] = 2;
                else if(input[j].equals("#"))
                {
                    miro[i][j] = 9;
                }

            }
        }

        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        boolean[][] visit = new boolean[R][C];

        Pos exit = null;
        if(ji.r == 0 || ji.r == R-1 || ji.c == 0 || ji.c == C-1)
        {
            exit = new Pos(ji.r, ji.c);
        }

        int count = 0;
        while(exit == null && count < R*C)
        {
            //J 확산
            boolean noGo = true;
            for(int i = 0; i < R; ++i)
            {
                for (int j = 0; j < C; ++j)
                {
                    if(miro[i][j] == 1 && visit[i][j] == false)
                    {
                        exit = bfs(new Pos(i, j), R, C,miro, visit, dir, 1);
                        noGo = false;
                    }
                }
                if(exit != null)
                    break;
            }

            count++;

            if(noGo)
                break;

            if(exit != null)
                break;

            //for(int i = 0; i < R; ++i)
            //    Arrays.fill(visit[i], false);

            //F 확산
            for(int i = 0; i < R; ++i)
            {
                for(int j = 0; j < C; ++j)
                {
                    if(miro[i][j] == 2 && visit[i][j] == false)
                    {
                        bfs(new Pos(i, j), R, C,miro, visit, dir, 2);
                    }
                }
            }

            for(int i = 0; i < R; ++i)
                Arrays.fill(visit[i], false);

        }

        if(exit != null)
        {
            System.out.println(count+1);
        }
        else
            System.out.println("IMPOSSIBLE");

        System.out.println(testcode);
    }

    private static Pos bfs(Pos start, int R, int C, int[][] miro, boolean[][] visit, int[][] dir, int object)
    {
        Queue<Pos> que = new LinkedList<>();

        que.add(start);
        visit[start.r][start.c] = true;

        Pos exit = null;

        while(que.isEmpty() == false && exit == null)
        {
            Pos cur = que.poll();

            for(int i = 0; i < 4; ++i)
            {
                int r = cur.r + dir[i][0];
                int c = cur.c + dir[i][1];

                if(r < 0 || r >= R || c < 0 || c >= C)
                    continue;

                if(object == 1 && miro[r][c] != 0)
                    continue;

                if(object == 2 && miro[r][c] == 9)
                    continue;

                if(object == 2 && miro[r][c] == 1)
                {}
                else
                {
                    if(visit[r][c] == true)
                        continue;
                }

                //if(object == 1)
                //    testcode++;

                que.add(new Pos(r, c));
                miro[r][c] = object;
                visit[r][c] = true;

                if(r == 0 || r == R-1 || c == 0 || c == C-1)
                {
                    exit = new Pos(r, c);
                    break;
                }

            }
            break;
        }

        if(exit == null)
            return null;

        return exit;
    }
}

더 이상 이 문제에서 시간을 지체할 수 없기에 풀이를 보게 되었다
다른 사람의 풀이를 보니 불을 먼저 퍼트리고 J도 퍼트리고 비교하면 된단다
주황색 숫자는 불이 확장될때 이동거리. (불 시작지점은 2,2)
초록 숫자는 J가 확장 될때 이동거리이다 (J 시작지점은 4,4)
보라색으로 표시된 부분을 보면 J가 불보다 먼저 도착하는 외곽인것을 알 수 있다. 그 중에 가장 작은것은 4이다

이해했으니 다시 짜봐야지 하....

불이 여러개일 경우 확장될때 이동거리를 어떻게 기록해야할까
일단 불 하나를 맵에 전부 확장시키면서 기록한다
그 다음 불을 기록할때 이전 기록보다 작을때만 기록한다
파란색 불을 퍼트리고

주황색 불을 퍼트리면 다음과 같아 질것이다

음 그냥 불을 전부 동시에 한칸씩 BFS로 퍼트려도 같은 결과가 나온다 이게더 최적화가 되어 있다

예외처리 하고 있는중
1.불이 아예 없는 경우도 있다
2.어떤 곳은 벽으로 완전히 막혀있는 경우도 있다

겨우 겨우 풀었다;;

시간복잡도는 2R*C
200만

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

class Pos
{
    int r;
    int c;

    public Pos() {
    }

    public Pos(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main
{
    static int testcode = 0;

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

        String[] input = br.readLine().split(" ");

        int R = Integer.parseInt(input[0]);
        int C = Integer.parseInt(input[1]);

        int [][] jmiro = new int[R][C];
        int [][] fmiro = new int[R][C];

        Queue<Pos> ji = new LinkedList<>();
        Queue<Pos> fire = new LinkedList<>();
        for(int i = 0; i < R; ++i)
        {
            input = br.readLine().split("");
            for(int j = 0; j < C; ++j)
            {
                if(input[j].equals("."))
                {
                    jmiro[i][j] = 0;
                    fmiro[i][j] = 0;
                }
                else if(input[j].equals("J"))
                {
                    jmiro[i][j] = 1;
                    ji.add(new Pos(i, j));
                }
                else if(input[j].equals("F"))
                {
                    fmiro[i][j] = 1;
                    fire.add(new Pos(i, j));
                }
                else if(input[j].equals("#"))
                {
                    jmiro[i][j] = -1;
                    fmiro[i][j] = -1;
                }

            }
        }

        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        boolean[][] visit = new boolean[R][C];

        //J 확산

        bfs(ji, R, C,jmiro, visit, dir);


        for(int i = 0; i < R; ++i)
            Arrays.fill(visit[i], false);

        //F 확산

        bfs(fire, R, C,fmiro, visit, dir);

        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < R; ++i)
        {
            if(i == 0|| i == R-1)//윗변, 아랫변
            {
                for(int j = 0; j < C; ++j)
                {
                    if(jmiro[i][j] == -1 || jmiro[i][j] == 0)//벽은 갈 수 없는곳. 0 인곳은 완전히 막힌곳
                        continue;

                    if(fmiro[i][j] == 0 || (jmiro[i][j] < fmiro[i][j]))
                    {
                        ans = Math.min(ans, jmiro[i][j]);
                    }
                }
            }
            else
            {

                if(jmiro[i][0] != -1 && jmiro[i][0] != 0)//벽은 갈 수 없는곳. 0 인곳은 완전히 막힌곳
                {
                    if(fmiro[i][0] == 0 || (jmiro[i][0] < fmiro[i][0]))
                        ans = Math.min(ans, jmiro[i][0]);
                }

                if(jmiro[i][C-1] != -1 && jmiro[i][C-1] != 0)//벽은 갈 수 없는곳. 0 인곳은 완전히 막힌곳
                {
                    if(fmiro[i][C-1] == 0 || (jmiro[i][C-1] < fmiro[i][C-1]))
                        ans = Math.min(ans, jmiro[i][C-1]);
                }

            }

        }

        if(ans == Integer.MAX_VALUE)
            System.out.println("IMPOSSIBLE");
        else
            System.out.println(ans);

            //System.out.println(testcode);
    }

    private static void bfs(Queue<Pos> que, int R, int C, int[][] miro, boolean[][] visit, int[][] dir)
    {
        for(Pos element: que)
        {
            visit[element.r][element.c] = true;
        }

        while(que.isEmpty() == false)
        {
            Pos cur = que.poll();

            for(int i = 0; i < 4; ++i)
            {
                int r = cur.r + dir[i][0];
                int c = cur.c + dir[i][1];

                if(r < 0 || r >= R || c < 0 || c >= C)
                    continue;

                if(miro[r][c] != 0)
                    continue;

                if(visit[r][c] == true)
                    continue;

                que.add(new Pos(r, c));
                miro[r][c] = miro[cur.r][cur.c] + 1;
                visit[r][c] = true;

                //testcode++;
            }

        }

    }
}