[알고리즘] 백준2178 미로탈출 - 자바

한번 풀어본 문제지만 자바에 익숙해지기 위해 다시 풀어본다. 싸피에 입과 후 알고리즘은 자바 수업으로 하기 때문에 이렇게라도 대비를 해본다.

 

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

2178번: 미로 탐색

 

 

[풀이 코드]

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 Boj_2178_미로탈출 {
	static int[][] graph;
	static boolean[][] check;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int M;
	static int N;

	static void bfs() {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { 0, 0 });
		check[0][0] = true;

		while (!q.isEmpty()) {
			int y = q.peek()[0];
			int x = q.peek()[1];
			q.poll();
			for (int l = 0; l < 4; l++) {
				int yy = y + dy[l];
				int xx = x + dx[l];
				if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
					if (!check[yy][xx] && graph[yy][xx] == 1) {
						graph[yy][xx] = graph[y][x] + 1;
						check[y][x] = true;
						q.offer(new int[] { yy, xx });
					}
				}
			} // for문 종료
		} // while문 종료

	}// bfs 종료

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

		graph = new int[N][M];
		check = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String line = bf.readLine();
			for (int j = 0; j < M; j++) {
				graph[i][j] = line.charAt(j) - '0';
			}
		}

		bfs();
		System.out.println(graph[N - 1][M - 1]);

	}

}

• 파이썬 문법에 익숙해져서 그런지 큐를 생성하는 부분부터 헷갈렸다.. 심지어 BufferedReader로 입력받는 것도 아직 버벅거리는 것 같다.
• 문제를 풀이해보자면, bfs로 해결하려 했다. 큐에 배열인덱스 {0, 0}을 넣고 상하좌우를 탐색하면서 이동할 때마다 입력받은 graph자체에 +1씩 해주며 움직였다.