[백준/2178][Java] 미로탐색

문제

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

2178번: 미로 탐색

알고리즘

C++로 이런 기초 BFS 문제를 많이 풀어봤으나 JAVA로는 처음 풀어서 큐에 저장하는 방식이나 스트링을 문자열로 바꾸고 이를 다시 이차원 배열에 저장하는 과정이 조금 까다로웠다.

알게된 점을 정리하자면, 먼저 BFS를 진행할 때 큐에 해당 좌표를 삽입하는데, 이때 

Queue<int[]> q = new LinkedList<>();

이처럼 int[]의 형식으로 좌표를 저장하게 된다.
그리고 이 큐에 push를 진행할 때면

q.add(new int[] {0,0});

위처럼 add를 진행하게 된다. 

C++의 pair에는 first, second로 각 원소에 바로 접근할 수 있었다면, 

int cur[] = q.poll(); int curX = cur[0]; int curY = cur[1];

cur[0]과 cur[1]을 미리 선언해야 한다.

 

가장 기초적인 BFS문제이고, 상하좌우를 모두 돌면서 탐색하면 된다. 

아래 코드에서 가장 중요한 포인트는 vis[nx][ny] = vis[curX][curY] + 1; 이다.
다음에 방문할 위치의 거리는 현재 위치의 거리에서 + 1을 한 값이 저장된다.

코드

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

public class B2178_미로탐색 {
	static int[][] board;
	static int[][] vis;
	static int n, m;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	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());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		board = new int[n][m];
		vis = new int[n][m];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				board[i][j] = s.charAt(j) - '0'; //문자열을 int로 바꾸려면 이렇게 '0'을 빼줘서 저장한다
			}
		}
		vis[0][0] = 1; //맨처음부터 방문 시작
		Queue<int[]> q = new LinkedList<>();//큐 생성 배열을 자료형으로 가짐
		q.add(new int[] {0,0});
		while(!q.isEmpty()) {
			int cur[] = q.poll();
			int curX = cur[0];
			int curY = cur[1];
			
			for(int dir = 0; dir<4;dir++) {
				int nx = curX + dx[dir];
				int ny = curY + dy[dir];
				if(nx<0||ny<0||nx>=n||ny>=m) continue;
				if(board[nx][ny]==0||vis[nx][ny]>0) continue;
				vis[nx][ny] = vis[curX][curY] + 1;
				q.add(new int[] {nx,ny});
			}
		}
		System.out.println(vis[n-1][m-1]);
		
	}

}