[BOJ/백준] 2178 미로 탐색(JAVA)

링크

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

 

문제 요약

미로 배열이 주어졌을 때, (1,1)에서 출발하여 (N, M)으로 이동할 때 지나야 하는 최소의 칸 수 구하기

1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 의미한다.

 

제한

• 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.
• 다음 N개의 줄에는 M개의 정수로 미로가 주어진다.
  • 각각의 수들은 붙어서 입력으로 주어진다.

 

풀이

문제에서 (1,1)이라고 주어졌는데, 이는 배열에서 (0,0) 값을 의미합니다.

따라서 왼쪽 맨 위에서 오른쪽 맨 아래로 이동하는 것이 목표입니다.

 

[입력]

평소와 다르게 각각의 수들이 붙어서 주어집니다. 그래서 StringTokenizer를 사용할 수 없습니다.

가장 쉽게 떠올릴 수 있는 입력 방법은 다음과 같았습니다.

1. 한 줄을 `String str` 에 입력받는다.
2. `str`을 순회하며 `str.charAt(i)-'0'` 값을 `int` 배열의 `i`번째 값을 저장한다.

for(int i=0; i<N; i++){
	String str = br.readLine();
	for(int j=0; j<M; j++){
		board[i][j] = str.charAt(j)-'0';
	}
}

 

코드의 길이는 복잡도와 상관없지만 개인적으로 저 5줄을 조금 줄이고 싶었습니다..!

그래서 `String → int []` 로 만들어주는 자바 api 없나~ 찾다가 이런 걸 발견합니다.

 

출처: 자바 21 공식 문서

https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/String.html#chars()

String (Java SE 21 & JDK 21)

 

`chars`라는 함수인데, String을 IntStream으로 변환해 주는 함수입니다.

근데, `String` 속 각각의 `char` 값을 아스키코드 값으로 변환해 주기 때문에 `char ’ 0’`의 아스키코드 값을 빼주어야 합니다. 이건 `map()` 함수를 통해 수행할 수 있습니다.

마지막으로 `IntStream`을 `array` 로 변환하기 위해 `toArray()` 함수를 쓰면 최종적으로 입력받는 부분이 완성됩니다.

for(int i=0; i<N; i++){
	board[i] = br.readLine().chars().map(val ->  val-'0').toArray();
}

 

[흐름]

N과 M의 최댓값이 10^2이므로 시간 복잡도는 `O(N^3)`까지도 가능합니다.

그래프 탐색 문제로, BFS로 문제를 풀었습니다.

1. 배열을 입력받는다.
   1. 동시에 값이 1인 칸의 정보(좌표, int의 최댓값)를 큐에 삽입한다.
2. 기준점 정보를 큐에 삽입한다. 정보는 좌표 값과 이동 거리이다.
   1. 시작점인 (1,1)은 이동 거리가 1이다.
3. 시작점으로부터 4 방향(위, 아래, 왼쪽, 오른쪽)으로 갈 수 있는 1칸을 찾는다.
4. 만약 아직 방문하지 않은 1칸이 있다면, 해당 칸의 정보(좌표, 이동 거리)를 큐에 삽입한다.
   1. 이동 거리는 (기존 이동거리 값, 기준점+1) 중 작은 값이다.
5. 큐에서 하나씩 정보를 빼내서 이를 기준점으로 2~4 과정을 반복한다.
6. 만약 새로 탐색할 위치가 목적지 위치라면, 이를 반환합니다.

 

코드

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

public class Main {
    static int N, M;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {0,-1,0,1};
    static int[] dy = {1,0,-1,0};

    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());
        board = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++){
            board[i] = br.readLine().chars().map(val ->  val-'0').toArray();
        }

        System.out.println(bfs(0,0));
    }

    static int bfs(int startX, int startY){
        // 시작점 초기화
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY, 1});
        visited[startX][startY]=true;

        while(!queue.isEmpty()){
            int[] info = queue.poll();

            for(int i=0; i<4; i++){ // 위, 아래, 왼쪽, 오른쪽 4방향으로 탐색
                int nx = info[0] + dx[i];
                int ny = info[1] + dy[i];

                if(nx<0 || ny<0 || nx>=N || ny>=M) continue; // 경계 범위 체크

                if(nx==N-1 && ny==M-1){ // 목적지에 도달하면 답 반환
                    return info[2]+1;
                }

                if(board[nx][ny]==1 && !visited[nx][ny]){ // 방문하지 않은 1칸은 큐에 삽입
                    visited[nx][ny]=true;
                    queue.add(new int[]{nx,ny,info[2]+1}); // 새로운 칸 최소 거리 = 이전 칸 최소 거리 + 1
                }
            }
        }
        return -1;
    }
}

🏷 시간 복잡도

• board: `N` * `M` 배열
• `bfs()` 함수는 모든 좌표를 순회하므로, `O(N*M)`
• 최종 시간 복잡도: `O(N*M)`

🏷 실행 속도

Time: 124 ms, Memory: 14956 KB