[백준] 불 4179 java - bfs

 

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

 

[첫번째 틀린 답안]

불과 지훈이가 동시에 움직이는 것이 이 문제의 포인트라고 할 수 있다.

동시간대에 불과 지훈이를 하나씩 움직여줘야 되는데

이를 어떻게 처리해야할지가 어려웠다..

처음에는 아래처럼 로직을 짰는데

생각해보니 아래 코드는 불의 위치가 지훈이보다 앞서있을 때에만 유효한 코드이다..

 

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

public class Main {
    static int R,C;
    static char[][] map;
    static boolean[][] visited;

    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    static void updateMap(int x, int y, char u){
        for(int i=0;i<4;i++){
            int nextX = x+dx[i];
            int nextY = y+dy[i];
            if(nextX>=0&&nextX<R && nextY>=0&&nextY<C){
                if(map[nextX][nextY] == '.')
                    map[nextX][nextY] = u;
            }
        }
    }

    static int bfs(int x, int y){
        int cnt = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y,0});

        while(!q.isEmpty()){
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];
            int count = now[2];
            for(int i=0;i<4;i++){
                int nextX = nowX+dx[i];
                int nextY = nowY+dy[i];
                if(nextX>=0&&nextX<R && nextY>=0&&nextY<C){
                    if(map[nextX][nextY]=='J' && !visited[nextX][nextY]) {
                        count++;
                        cnt = count;
                        q.add(new int[]{nextX, nextY, count});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
        return cnt;
    }

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

        map = new char[R][C];
        visited = new boolean[R][C];

        int startX=0,startY=0;
        for(int i=0;i<R;i++){
            String arr = br.readLine();
            for(int j=0;j<C;j++){
                map[i][j] = arr.charAt(j);
                if(map[i][j]=='J'){
                    startX=i;
                    startY=j;
                }

            }
        }

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++) {
                if(map[i][j]=='F') {
                    updateMap(i, j, 'F');
                }
                if(map[i][j]=='J')
                    updateMap(i,j,'J');
            }
        }

        boolean flag = false;
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(i==0||i==R-1||j==0||j==C-1){
                    if(map[i][j]=='J') {
                        flag = true;
                        break;
                    }
                }
            }
        }

      
        if(flag){
            System.out.println(bfs(startX,startY));
        }else {
            System.out.println("IMPOSSIBLE");
        }

    }
}

 

 

[두 번째 틀린 답안]

불이 여러개가 있을 수 있다는 사실을 간과했다..

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

public class Main {
    static int R,C;
    static char[][] map;
    static boolean[][] visited;

    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};


    static int bfs(int fx, int fy, int jx, int jy){
        int cnt = 0;
        int[][] cntMap = new int[R][C];
        visited = new boolean[R][C];
        Queue<int[]> fireQ = new LinkedList<>();
        fireQ.add(new int[]{fx, fy, 1});

        while(!fireQ.isEmpty()){
            int[] fire = fireQ.poll();
            int fireX = fire[0];
            int fireY = fire[1];
            int fireCnt = fire[2];

            for(int i=0;i<4;i++){
                int nextX = fireX+dx[i];
                int nextY = fireY+dy[i];
                int nextCnt = fireCnt+1;
                if(nextX>=0&&nextX<R && nextY>=0&&nextY<C){
                    if(!visited[nextX][nextY] && map[nextX][nextY]=='.'){
                        visited[nextX][nextY] = true;
                        fireQ.add(new int[]{nextX, nextY, nextCnt});
                        cntMap[nextX][nextY] = nextCnt;
                    }
                }
            }
        }


        visited = new boolean[R][C];
        Queue<int[]> jihoonQ = new LinkedList<>();
        jihoonQ.add(new int[]{jx,jy,1});

        while(!jihoonQ.isEmpty()){
            int[] jihoon = jihoonQ.poll();
            int jihoonX = jihoon[0];
            int jihoonY = jihoon[1];
            int jihoonCnt = jihoon[2];

            for(int i=0;i<4;i++){
                int nextX = jihoonX+dx[i];
                int nextY = jihoonY+dy[i];
                int nextCnt = jihoonCnt+1;
                if(nextX>=0&&nextX<R && nextY>=0&&nextY<C){
                    if(!visited[nextX][nextY]&& map[nextX][nextY]=='.') {
                        if(cntMap[nextX][nextY]!=0) {
                            if (cntMap[nextX][nextY] > nextCnt) {
                                visited[nextX][nextY] = true;
                                jihoonQ.add(new int[]{nextX, nextY, nextCnt});
                                cnt = nextCnt;

                                if(nextX==0||nextX==R-1 || nextY==0||nextY==C-1)
                                    return cnt;
                            }
                        }
                        else {
                                visited[nextX][nextY] = true;
                                jihoonQ.add(new int[]{nextX, nextY, nextCnt});
                                cnt = nextCnt;

                                if(nextX==0||nextX==R-1 || nextY==0||nextY==C-1)
                                    return cnt;
                            }
                }}
            }
        }
        return cnt;
    }

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

        map = new char[R][C];

        int fx=0,fy=0;
        int jx=0,jy=0;

        for(int i=0;i<R;i++){
            String arr = br.readLine();
            for(int j=0;j<C;j++) {
                map[i][j] = arr.charAt(j);
                if (map[i][j] == 'F') {
                    fx = i;
                    fy = j;
                } else if (map[i][j] == 'J') {
                    jx = i;
                    jy = j;
                }
            }
        }

        int result = bfs(fx,fy,jx,jy);

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

    }
}

 

 

[정답]

인터넷을 참조해서 코드를 수정했다!

지훈이는 불의 움직임에 영향을 받지만

불은 지훈이의 움직임에 영향을 받지 않는다

불을 시간에 따라 먼저 전파시킨 후에

불이 먼저 전파된 경우(시간이 지훈이보다 앞선 경우)만 제외하고

지훈이를 움직이면 된다 !!

 

또한 맨 처음부터 지훈이가 가장자리에 있는 경우에

바로 return 1을 하게 해주었다

 

아래와 같은 반례를 생각해주지 않아서 엄청 헤맸다,,,;ㅎ

2 2
JF
FF

1

 

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

public class Main {
    static int R,C;
    static char[][] map;
    static int[][] cntMap;
    static boolean[][] visited;

    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};


    static void fbfs(int fx, int fy){
        int cnt = 0;
        visited = new boolean[R][C];
        Queue<int[]> fireQ = new LinkedList<>();
        fireQ.add(new int[]{fx, fy, 1});

        while(!fireQ.isEmpty()){
            int[] fire = fireQ.poll();
            int fireX = fire[0];
            int fireY = fire[1];
            int fireCnt = fire[2];

            for(int i=0;i<4;i++){
                int nextX = fireX+dx[i];
                int nextY = fireY+dy[i];
                int nextCnt = fireCnt+1;
                if(nextX>=0&&nextX<R && nextY>=0&&nextY<C){
                    if(!visited[nextX][nextY] && map[nextX][nextY]=='.'){
                        if(cntMap[nextX][nextY]==0 || cntMap[nextX][nextY]!=0 && nextCnt<cntMap[nextX][nextY]){
                            visited[nextX][nextY] = true;
                            fireQ.add(new int[]{nextX, nextY, nextCnt});
                            cntMap[nextX][nextY] = nextCnt;
                        }

                    }
                }
            }
        }
    }

    static int jbfs(int jx, int jy){
        int cnt = 0;
        visited = new boolean[R][C];
        Queue<int[]> jihoonQ = new LinkedList<>();
        jihoonQ.add(new int[]{jx,jy,1});

        if(jx==0||jx==R-1 || jy==0||jy==C-1)
            return 1;
        while(!jihoonQ.isEmpty()){
            int[] jihoon = jihoonQ.poll();
            int jihoonX = jihoon[0];
            int jihoonY = jihoon[1];
            int jihoonCnt = jihoon[2];

            for(int i=0;i<4;i++){
                int nextX = jihoonX+dx[i];
                int nextY = jihoonY+dy[i];
                int nextCnt = jihoonCnt+1;
                if(nextX>=0&&nextX<R && nextY>=0&&nextY<C){
                    if(!visited[nextX][nextY]&& map[nextX][nextY]=='.') {
                        if(cntMap[nextX][nextY]!=0) {
                            if (cntMap[nextX][nextY] > nextCnt) {
                                visited[nextX][nextY] = true;
                                jihoonQ.add(new int[]{nextX, nextY, nextCnt});
                                cnt = nextCnt;

                                if(nextX==0||nextX==R-1 || nextY==0||nextY==C-1)
                                    return cnt;
                            }
                        }
                        else {
                            visited[nextX][nextY] = true;
                            jihoonQ.add(new int[]{nextX, nextY, nextCnt});
                            cnt = nextCnt;

                            if(nextX==0||nextX==R-1 || nextY==0||nextY==C-1)
                                return cnt;
                        }
                    }}
            }
        }
        return 0;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        cntMap = new int[R][C];

        for(int i=0;i<R;i++){
            String arr = br.readLine();
            for(int j=0;j<C;j++) {
                map[i][j] = arr.charAt(j);
            }
        }

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++) {
                if (map[i][j] == 'F') {
                    fbfs(i,j);
                }
            }
        }


        int result = 0;
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++) {
                if (map[i][j] == 'J') {
                    result=jbfs(i,j);
                    break;
                }
            }
        }


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

    }
}