[Java] 2206 벽 부수고 이동하기

[peppermintt0504]

문제 풀이 해당 문제는 기존의 DFS 문제와 유사하다. 하지만 벽을 부술 수 있다는 예외 케이스가 존재한다. 그렇기에 처음 구현했을 때 아래와 같이 Positon class를 만들어 벽을 부술 기회가 남아있다면 벽도 지날 수 있도록 지정해두었다.

코드는 아래와 같다.

import java.util.*;
import java.io.*;
public class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int[][] board;
    public static boolean[][] visited;

    public static Queue<Position> qu = new LinkedList<>();

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

    public static class Position {
        int x;
        int y;
        boolean chance = true;
        int distance;

        public Position() {
            // TODO Auto-generated constructor stub
        }

        public Position(int x, int y, boolean chance,int distance) {
            super();
            this.x = x;
            this.y = y;
            this.chance = chance;
            this.distance = distance;
        }
    }

    public static void main(String[] args) throws IOException{

        StringTokenizer st = new StringTokenizer(br.readLine());

        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int answer = -1;

        board = new int[R][C];
        visited = new boolean[R][C];

        for(int i = 0; i < R; i++) 
            board[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

        qu.add(new Position(0,0,true,1));

        while(!qu.isEmpty()) {
            Position cur = qu.poll();

            if(cur.x == C - 1 && cur.y == R - 1) {
                answer = cur.distance;
                break;
            }

            if(visited[cur.y][cur.x])continue;
            visited[cur.y][cur.x] = true;

            for(int i = 0; i < 4; i++) {
                int mx = cur.x + dx[i];
                int my = cur.y + dy[i];

                if(mx < 0 || mx >= C || my < 0 || my >= R)continue;

                if(cur.chance) {
                    if(board[my][mx] == 0) {
                        qu.add(new Position(mx,my,true,cur.distance+1));
                    }else {
                        qu.add(new Position(mx,my,false,cur.distance+1));
                    }
                }else {
                    if(board[my][mx] == 0) {
                        qu.add(new Position(mx,my,false,cur.distance+1));
                    }
                }
            }
        }
        if(R == 1 && C == 1) 
            System.out.println(0);
        else
        System.out.println(answer);

    }

}

하지만 테스트케이스 15%쯤 오답이 나왔다.

오답이 나오는 케이스는 아래와 같은 케이스였다.

7 5
00000
11110
00000
01111
00000
11111
00000

위와 같은 케이스에서는 (1,0)을 벽으로 부수고 아래로 진출 할 때 visited[1][0]에서 벽을 부수지 않고 돌아서 진출했을 때 진행을 하지 못하여 -1을 출력하였다.

빨간 케이스(벽을 부순 경우)로 인해 파란 케이스(벽을 부수지 않은 경우)가 막혀 답이 나오지 않는 것이다.

그렇기에 벽을 부순 경우는 visited를 별도로 만들어서 구현해보았고, 문제를 해결할 수 있었다.

해결 코드

import java.util.*;
import java.io.*;
public class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int[][] board;
    public static boolean[][] visited;
    public static boolean[][] visited2;

    public static Queue<Position> qu = new LinkedList<>();

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

    public static class Position {
        int x;
        int y;
        boolean chance = true;
        int distance;

        public Position() {
            // TODO Auto-generated constructor stub
        }

        public Position(int x, int y, boolean chance,int distance) {
            super();
            this.x = x;
            this.y = y;
            this.chance = chance;
            this.distance = distance;
        }

        @Override
        public String toString() {
            return "Position [x=" + x + ", y=" + y + ", chance=" + chance + ", distance=" + distance + "]";
        }
    }

    public static void main(String[] args) throws IOException{

        StringTokenizer st = new StringTokenizer(br.readLine());

        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int answer = -1;

        board = new int[R][C];
        visited = new boolean[R][C];
        visited2 = new boolean[R][C];

        for(int i = 0; i < R; i++) 
            board[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

        qu.add(new Position(0,0,true,1));

        while(!qu.isEmpty()) {
            Position cur = qu.poll();
            if(cur.x == C - 1 && cur.y == R - 1) {
                answer = cur.distance;
                break;
            }

            if(cur.chance) {
                if(visited[cur.y][cur.x])continue;
                else {
                    visited2[cur.y][cur.x] = true;
                    visited[cur.y][cur.x] = true;
                }

            }else {
                if(visited2[cur.y][cur.x])continue;
                else 
                    visited2[cur.y][cur.x] = true;
            }

            for(int i = 0; i < 4; i++) {
                int mx = cur.x + dx[i];
                int my = cur.y + dy[i];

                if(mx < 0 || mx >= C || my < 0 || my >= R)continue;

                if(cur.chance) {
                    if(board[my][mx] == 0) {
                        qu.add(new Position(mx,my,true,cur.distance+1));
                    }else {
                        qu.add(new Position(mx,my,false,cur.distance+1));
                    }
                }else {
                    if(board[my][mx] == 0) {
                        qu.add(new Position(mx,my,false,cur.distance+1));
                    }
                }
            }
        }
        System.out.println(answer);

    }

}

[alloy31]

멋있어용