BOJ 2206 벽 부수고 이동하기(JAVA) 🧱

구조화

• 벽을 부수고 움직일 수 있는 한 번의 기회가 있음
• [x][y][0] → 벽을 안 부수고 이동
• [x][y][1] → 벽을 한 번 부숨
• if [x][y][1]이 true고 map[nx][ny] == 1 → 안됨

소스 코드

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

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

	static int N, M, result;
	static char[][] map;
	static boolean[][][] visited;
	// 상 하 좌 우
	static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("input/test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new char[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++) 
			{
				map[i][j] = str.charAt(j-1);
			}
		}
		
		bfs();
	}
	
	private static void bfs() {
		
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {1,1,0});
		visited[1][1][0] = true;
		
		int level = 0;
		
		while(!q.isEmpty())
		{
			int size = q.size();
			for (int s = 0; s < size; s++) 
			{
				int[] cur = q.poll();
				int cx = cur[0];
				int cy = cur[1];
				int once = cur[2];
				
				if(cx==N && cy==M)
				{
					System.out.println(level+1);
					return;
				}
				
				for (int i = 0; i < 4; i++) 
				{
					int nx = cx + way[i][0];
					int ny = cy + way[i][1];
					
					if(!isRight(nx, ny)) continue;
					if(visited[nx][ny][once]) continue;
					
					if(map[nx][ny]=='1')
					{
						if(once==0)
						{
							q.offer(new int[] {nx,ny,once+1});
							visited[nx][ny][once+1] = true;
						}
					}
					else
					{
						q.offer(new int[] {nx,ny,once});
						visited[nx][ny][once] = true;
					}
				}
			}
			level++;
		}
		System.out.println(-1);
	}

	private static boolean isRight(int nx, int ny) {
		return (nx>0 && nx<N+1 && ny>0 && ny<M+1);
	}

}