[백준 2206번] 벽 부수고 이동하기 (java)

2206번: 벽 부수고 이동하기

 

처음에는 일반적인 너비우선탐색(BFS) 방법처럼 visited 배열을 2차원 배열로 만들어서 문제를 풀었으나, 

11%에서 틀렸다고 나왔다.

 

특정 위치(nr, nc)에 도착했을 때, 그 위치까지 도달하는 과정에서 벽을 한 번 부수고 도달했는지,

한 번도 부수지 않고 도달했는지 이 두가지 경우를 모두 고려해서 방문처리를 해야 한다.

 

따라서 visited 배열을 2차원 배열이 아닌 3차원 배열로 만들어서

1. 벽을 부수지 않고 방문한 경우 : visited[nr][nc][0]

2. 벽을 부수고 방문한 경우 : visited[nr][nc][1]

로 나누어서 방문처리를 하였다.

 

이 외의 다른 코드는 큐를 이용한 BFS 방식의 코드와 동일하게 해결하였다.

 

 

	import java.io.*;
	import java.util.*;
	public class n02206 {
	static int N, M;
	static int[][] board;
	static boolean[][][] visited;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] input = br.readLine().split(" ");
	N = Integer.parseInt(input[0]);
	M = Integer.parseInt(input[1]);
	board = new int[N + 1][M + 1];
	visited = new boolean[N + 1][M + 1][2];
	for (int i = 1; i <= N; i++) {
	String str = br.readLine();
	for (int j = 1; j <= M; j++) {
	board[i][j] = str.charAt(j - 1) - '0';
	}
	}
	bw.write(bfs() + "\n");
	bw.flush();
	}
	public static int bfs() {
	int[] r = { 0, 1, 0, -1 };
	int[] c = { 1, 0, -1, 0 };
	Queue<Pair> q = new LinkedList<>();
	Pos start = new Pos(1, 1);
	q.offer(new Pair(start, false, 1));
	visited[1][1][0] = true;
	while (!q.isEmpty()) {
	Pair pair = q.poll();
	Pos pos = pair.pos;
	if (pos.r == N && pos.c == M) {
	return pair.cnt;
	}
	for (int i = 0; i < 4; i++) {
	int nr = pos.r + r[i];
	int nc = pos.c + c[i];
	if ((1 <= nr && nr <= N) && (1 <= nc && nc <= M)) {
	if (board[nr][nc] == 0) {
	if (pair.flag && !visited[nr][nc][1]) {
	q.offer(new Pair(new Pos(nr, nc), pair.flag, pair.cnt + 1));
	visited[nr][nc][1] = true;
	} else if (!pair.flag && !visited[nr][nc][0]) {
	q.offer(new Pair(new Pos(nr, nc), pair.flag, pair.cnt + 1));
	visited[nr][nc][0] = true;
	}
	}
	else if (board[nr][nc] == 1 && !pair.flag && !visited[nr][nc][1]) {
	q.offer(new Pair(new Pos(nr, nc), true, pair.cnt + 1));
	visited[nr][nc][1] = true;
	}
	}
	}
	}
	return -1;
	}
	static class Pair {
	boolean flag;
	Pos pos;
	int cnt;
	Pair(Pos pos, boolean flag, int cnt) {
	this.pos = pos;
	this.flag = flag;
	this.cnt = cnt;
	}
	}
	static class Pos {
	int r, c;
	Pos(int r, int c) {
	this.r = r;
	this.c = c;
	}
	}
	}

view raw 2206.java hosted with ❤ by GitHub