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

1. 문제

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

2206번: 벽 부수고 이동하기

---

2. 접근 및 해결

2-1) 접근

1. bfs로 접근합니다.

2. 3차원 배열(isVisited)을 이용합니다. isVisited[부순 벽인지][x][y]로 작성했습니다.

-> 부순 벽인지? 0:부수지 않고 옴, 1: 부숴서 옴

부수지 않고 현재 x, y좌표까지 왔는지? 부숴서 현재 x, y좌표까지 왔는지를 나타냅니다.

3. Node는 x, y, cnt(현재까지 이동한 거리), brk(벽을 부숴서 온 것인지 아닌지)를 이용합니다.

 

2-2) 해결

if(list[nx][ny]==0) { // 벽이 아닌 경우
	if(isVisited[node.getBrk()][nx][ny]==false){ // 현재까지 도달한 방법으로 다음으로 이동함(이동하려는 공간이 벽이 아니므로, 벽을 부쉈던 부수지 않았던 간에 상관 없음)
	isVisited[node.getBrk()][nx][ny] = true;
	queue.offer(new Node4(nx, ny, node.getCnt() + 1, node.getBrk()));
	}
} else if(list[nx][ny]==1){ // 벽인 경우
    if(node.getBrk()==0 && isVisited[1][nx][ny]==false) { // 벽인 경우에는 부순적이 없는 경우에 대해서만(벽은 최대 1번 부술 수 있음) 부술 수 있음 && 부술 곳이 방문하지 않은 경우  
        isVisited[1][nx][ny] = true;
        queue.offer(new Node4(nx, ny, node.getCnt() + 1, 1)); 
    }
}

문제의 입력1에 대해 bfs를 실행하고 나면 isVisited가 아래의 사진과 같이 됩니다.

isVisited[0] = 부수지 않고 이동한 최단거리, isVisited[1] = 벽을 부수고 이동한 최단거리

// 예제 입력 1
6 4
0100
1110
1000
0000
0111
0000

bfs 실행 이후 isVisited 상황

---

3. 코드(JAVA) 

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

class Node4 {
	int x, y, cnt, brk;
	
	Node4(int x, int y, int cnt, int brk) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
		this.brk = brk;
	}
	
	int getX() {
		return this.x;
	}
	
	int getY() {
		return this.y;
	}
	
	int getCnt() {
		return this.cnt;
	}
	
	int getBrk() {
		return this.brk;
	}
}

public class p2206 {
	static int N, M, result;
	static int[][] list;
	static boolean[][][] isVisited;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		list = new int[N][M];
		isVisited = new boolean[2][N][M];
		result = -1;
		
		for(int i=0; i<N; i++) {
			String s = br.readLine();
			for(int j=0; j<M; j++) {
				list[i][j] = Integer.valueOf(s.charAt(j))-'0';
			}
		}
		isVisited[0][0][0] = true;
		bfs(0, 0, 1, 0);
		
		if(N==1 && M==1) 
			bw.write("1");
		else
			bw.write(Integer.toString(result));
		br.close();
		bw.close();
	}
	
	public static void bfs(int x, int y, int cnt, int brk) {
		Queue<Node4> queue = new LinkedList<>();
		
		queue.offer(new Node4(x, y, cnt, brk));
		
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		
		while(!queue.isEmpty()) {
			Node4 node = queue.poll();
			
			for(int d=0; d<4; d++) {
				int nx = node.getX() + dx[d];
				int ny = node.getY() + dy[d];
				
				if(nx<0||ny<0||nx>=N||ny>=M) continue;
				if(nx == N-1 && ny == M-1) {
					result = node.getCnt() +1;
					return;
				}
				if(list[nx][ny]==0) { // 벽이 아닌 경우
					if(isVisited[node.getBrk()][nx][ny]==false){
					isVisited[node.getBrk()][nx][ny] = true;
					queue.offer(new Node4(nx, ny, node.getCnt() + 1, node.getBrk()));
					}
				} else if(list[nx][ny]==1){ // 벽인 경우
					if(node.getBrk()==0 && isVisited[1][nx][ny]==false) {
						isVisited[1][nx][ny] = true;
						queue.offer(new Node4(nx, ny, node.getCnt() + 1, 1));
					}
				}
			}
		}
	}
}

 

* 참고한 블로그

 

https://moonsbeen.tistory.com/125

[백준]2206: 벽 부수고 이동하기 - JAVA