[Java] 2206 벽 부수고 이동하기 #15
Description
문제 풀이
해당 문제는 기존의 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);
}
}