[백준] 2178 미로 탐색 자바 BFS 문제 풀이 및 정답

문제 요약)

- 세로 n, 가로 m이 주어짐

- 출발위치에서 마지막 위치의 최소거리

 

주의점)

- x

 

풀이)

BFS로 풀이를 진행하며 q를 사용할때 x, y등 좌표값을 줘야하기 때문에 class를 선언해주거나 배열자체를 q에 넣어야하는데 별도 클래스를 만드는 것보다 배열이 조금 더 편해서 배열로 풀이했습니다.

 

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 Maze2178_blog {
​​​​static int[] dx = {-1, 0, 1, 0};
​​​​static int[] dy = {0, 1, 0, -1};
​​​​static int[][] map;
​​​​static int[][] distance;
​​​​static int n, m;

​​​​public static void main(String[] args) throws IOException {
​​​​​​​​BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
​​​​​​​​StringTokenizer st = new StringTokenizer(br.readLine(), " ");
​​​​​​​​n = Integer.parseInt(st.nextToken());
​​​​​​​​m = Integer.parseInt(st.nextToken());

​​​​​​​​// 첫 위치가 1,1이니까 인덱스가 1부터 잡히게 +1해주기
​​​​​​​​map = new int[n+1][m+1];
​​​​​​​​distance = new int[n+1][m+1];

​​​​​​​​// map 채워주기
​​​​​​​​for (int i=1; i<=n; i++) {
​​​​​​​​​​​​String[] strs = br.readLine().split("");
​​​​​​​​​​​​int j = 1;
​​​​​​​​​​​​for (String a : strs) {
​​​​​​​​​​​​​​​​map[i][j] = Integer.parseInt(a);
​​​​​​​​​​​​​​​​j++;
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​distance[1][1] = 1;
​​​​​​​​BFS(1, 1);
​​​​​​​​System.out.println(distance[n][m]);
​​​​}

​​​​static void BFS(int x, int y) {
​​​​​​​​Queue<int[]> q = new LinkedList<>();
​​​​​​​​q.offer(new int[]{x, y});
​​​​​​​​while(!q.isEmpty()) {
​​​​​​​​​​​​int[] current = q.poll();

​​​​​​​​​​​​for (int k=0; k<4; k++) {
​​​​​​​​​​​​​​​​int nx = current[0] + dx[k];
​​​​​​​​​​​​​​​​int ny = current[1] + dy[k];
​​​​​​​​​​​​​​​​// out of index 방지
​​​​​​​​​​​​​​​​if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
​​​​​​​​​​​​​​​​// 이미 방문했거나(dis가 0이상이면 방문했다는 것) 방문 불가한 곳 제외
​​​​​​​​​​​​​​​​if (distance[nx][ny] > 0 || map[nx][ny] == 0) continue;
​​​​​​​​​​​​​​​​// q에 넣고 거리 세팅해주기
​​​​​​​​​​​​​​​​q.offer(new int[] {nx, ny});
​​​​​​​​​​​​​​​​distance[nx][ny] = distance[current[0]][current[1]] + 1;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}