[백준] 2206번 : 벽 부수고 이동하기 - 자바(JAVA)

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

2206번: 벽 부수고 이동하기

 

문제 해석

N x M의 행렬로 표현되는 맵이 있습니다.

맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽으로 표시됩니다.

(1,1)에서 (N, M)의 위치로 최단경로로 이동하려고 합니다

이때 시작하는 칸과 끝나는 칸도 포함해서 셉니다.

 

만약 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개까지 부수고 이동해도 됩니다.

 

문제 풀이 전 설계

벽을 부수는 것이 짧아질 수도 있고 부수지 않는 것이 짧아질 수도 있다.

따라서 벽을 한개 부수고 이동할 경우 / 벽을 부수지 않고 이동하는 경우로 나누어서 맵의 벽을 하나씩 부신 후 최단 거리를 탐색해보는 완전 탐색을 진행해봅니다.

 

최단 경로를 구해내야 하므로 BFS를 활용합니다.

 

 

문제 풀이 하면서

위의 방법처럼 풀이하게 될 경우에는 시간 초과를 만나게 됩니다.

따라서 BFS를 한 번만 돌면서 최단거리를 탐색해야 합니다.

이를 위해 3차원의 visited배열이 필요합니다.

2차원은 N * M의 정보를 저장하고 있으며 1차원은 벽을 부수지 않는 경우 / 벽을 부수는 경우를 저장합니다.

 

따라서 BFS를 탐색하며 벽인 경우에는 벽을 부술 수 없거나 이미 해당 벽을 부순 경우에는 continue를 통해 유효성 검사를 하고 그렇지 않다면 bfsQ에 넣고 반복합니다.

 

또한 벽이 아닌 경우에는 벽을 부수고 이동할 수도 있고 벽을 부수지 않고 이동할 수 도 있기 때문에 broken이라는 변수를 두어 방문 체크를 하며 반복합니다.

 

3차원 배열로 방문 체크를 한다는 점이 좀 신기했습니다.

 

시간 초과 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2206_벽부수고이동하기 {

	static class Pos {
		int y;
		int x;
		int depth;

		public Pos(int y, int x, int depth) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
		}

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + ", depth=" + depth + "]";
		}
		
		

	}

	static int N, M;
	static List<Pos> wallList = new ArrayList<Pos>();
	static boolean[][] board;
	static boolean[][] visited;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static final int DIRECTION = 4;
	static int result = Integer.MAX_VALUE;

	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		board = new boolean[N][M];
		visited = new boolean[N][M];
		
		String str = null;
		for (int y = 0; y < N; y++) {
			str = br.readLine();
			for (int x = 0; x < M; x++) {
				if (str.charAt(x) =='0') {
					board[y][x] = true;
					continue;
				}				
				wallList.add(new Pos(y, x, 0));
			}
		}
		// 벽을 부수지 않았을 때
		BFS();
		visited = new boolean[N][M];
		// 벽을 1개 부쉈을 때
		
		for (Pos e : wallList) {
			board[e.y][e.x] = true;
			BFS();
			board[e.y][e.x] = false;
			visited = new boolean[N][M];
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		if(result == Integer.MAX_VALUE) {
			bw.write(-1 + "\n");
			bw.flush();
			bw.close();
			return;
		}
		
		bw.write((result+1) + "\n");
		bw.flush();
		bw.close();
		

	}

	private static void BFS() {
		Queue<Pos> bfsQ = new LinkedList<Pos>();
		bfsQ.add(new Pos(0, 0, 0));
		visited[0][0] = true; 
		
		Pos currentPos = null;
		int currentY = 0, currentX = 0, currentDepth = 0;
		outer : while (!bfsQ.isEmpty()) {
			currentPos = bfsQ.poll();			
			if(currentPos.x == M-1 && currentPos.y == N-1) {
				result = currentPos.depth;
				break outer;
			}
			
			currentY = currentPos.y;
			currentX = currentPos.x;
			currentDepth = currentPos.depth;
			
			for(int k=0; k<DIRECTION; k++) {
				int tempY = currentY + dy[k];
				int tempX = currentX + dx[k];
				if(!isValid(tempY,tempX)){
					continue;
				}
				if(currentDepth+1 >=result) {
					break outer;
				}
				visited[tempY][tempX] = true;
				bfsQ.add(new Pos(tempY,tempX,currentDepth+1));
				
			}
			
		}
		

	}

	private static boolean isValid(int y, int x) {		
		return (y >=0 && x>=0 && y <N && x < M && board[y][x] && !visited[y][x]);
	}

}

 

 

통과한 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2206_벽부수고이동하기 {

	static class Player {
		int y;
		int x;
		int depth;
		boolean isBreakWall;
		
		
		
		public Player() {
			super();
			this.y = 0;
			this.x = 0;
			this.depth = 0;
			this.isBreakWall = true;
		}

		public Player(int y, int x, int depth, boolean isBreakWall) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
			this.isBreakWall = isBreakWall;
		}

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + ", depth=" + depth + "]";
		}
		
		

	}

	static int N, M;
	static boolean[][] board;
	static boolean[][][] visited;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static final int DIRECTION = 4;
	static int result = Integer.MAX_VALUE;
	static final boolean WALL = false;
	static final boolean EMPTY = true;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		board = new boolean[N][M];
		visited = new boolean[N][M][2];
		
		String str = null;
		for (int y = 0; y < N; y++) {
			str = br.readLine();
			for (int x = 0; x < M; x++) {
				if (str.charAt(x) =='0') {
					board[y][x] = true;
					continue;
				}								
			}
		}

		BFS();
		
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		if(result == Integer.MAX_VALUE) {
			bw.write(-1 + "\n");
			bw.flush();
			bw.close();
			return;
		}
		
		bw.write((result+1) + "\n");
		bw.flush();
		bw.close();
		

	}

	private static void BFS() {
		Queue<Player> bfsQ = new LinkedList<Player>();
		bfsQ.add(new Player());
		
		//벽 뚫지 않음
		visited[0][0][0] = true;
		//벽 뚫었는지 여부
		visited[0][0][1] = true;
		
		Player currentPos = null;
		int currentY = 0, currentX = 0, currentDepth = 0;
		boolean isBreakWall;
		int broken;
		outer : while (!bfsQ.isEmpty()) {
			currentPos = bfsQ.poll();			
			if(currentPos.x == M-1 && currentPos.y == N-1) {
				result = currentPos.depth;
				break outer;
			}
			
			currentY = currentPos.y;
			currentX = currentPos.x;
			currentDepth = currentPos.depth + 1;
			isBreakWall = currentPos.isBreakWall;
			broken = isBreakWall ? 0: 1;
			
			for(int k=0; k<DIRECTION; k++) {
				int tempY = currentY + dy[k];
				int tempX = currentX + dx[k];
				if(!isPosValid(tempY,tempX)){
					continue;
				}
				//벽인경우
				if(board[tempY][tempX] == WALL) {
					//벽을 부술 수 없거나, 방문한 경우
					if(!isBreakWall || visited[tempY][tempX][1]) {
						continue;
					}
					visited[tempY][tempX][1] = true;
					bfsQ.add(new Player(tempY,tempX,currentDepth,false));
					continue;
				}
				//벽이 아닌경우
				if(visited[tempY][tempX][broken]) {
					continue;
				}
				visited[tempY][tempX][broken] = true;
				bfsQ.add(new Player(tempY,tempX,currentDepth,isBreakWall));
				
			}
			
		}
		

	}

	private static boolean isPosValid(int y, int x) {
		return (y >=0 && x>=0 && y <N && x < M);
	}
	
	
	

}