[백준] 2206 벽 부수고 이동하기 [자바]

---

https://www.acmicpc.net/board/view/74720

글 읽기 - C++ 메모리초과 해결방법좀 알려주세요

https://iseunghan.tistory.com/316

백준 2206번 : 벽 부수고 이동하기 (JAVA) 문제 풀이

---

import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	
	public class Main {
		static int[][] xy; // 좌표 계산
		static boolean[][][] visit;
		static int[][] cnt;
		static int[] x_move = {-1,1,0,0};
		static int[] y_move = {0,0,-1,1};
		static int N;
		static int M;
		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());
			xy = new int[N][M];
			visit = new boolean[N][M][2];
			cnt = new int[N][M];
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				String str = st.nextToken();	
				for(int j = 0; j < M; j++) {
					xy[i][j] = str.charAt(j)-'0';
				}
			}
			cnt[0][0] = 1;
			bfs();
		}
		static void bfs() {
			int c = 0;
			Queue<int[]> q = new LinkedList<>();
			q.offer(new int[] {0,0,0});
			int dis = 3;
			while(!q.isEmpty()) {
				int [] cur = q.poll();
				visit[cur[0]][cur[1]][cur[2]] = true;
				if(cur[0] == N-1 && cur[1] == M-1) {
					System.out.println(cnt[N-1][M-1]);
					return;
				}
				for(int i = 0; i < 4; i++) {
					int tx = cur[0]+x_move[dis];
					int ty = cur[1]+y_move[dis];
					if(tx >= 0 && tx < N && ty >= 0 && ty < M) {
						if(xy[tx][ty] == 0 && visit[tx][ty][cur[2]] == false) {
							visit[tx][ty][cur[2]] = true;
							cnt[tx][ty] = cnt[cur[0]][cur[1]] + 1;
							q.offer(new int[] {tx,ty,cur[2]});
						}
						else if(xy[tx][ty] == 1 && cur[2] == 0) {
							q.offer(new int[] {tx,ty,1});
							cnt[tx][ty] = cnt[cur[0]][cur[1]] + 1;
						}
					}
					dis = change(dis);
				}
			}
			System.out.println(-1);
			return;
		}
		static int change(int n) {
			if(n == 0)
				return 3;
			else
				return n-1;
		}
	}