[백준 알고리즘] 2178번자바(Java) 미로탐색 BFS

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

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

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

풀이

 - 시간복잡도

입력받는 값이 nxm의 최대값이 1만이기때문에 O(n^2)방법으로는 시간제한이 아슬아슬하다.

따라서 O(nlogn)복잡도를 가진 너비우선탐색을 사용해 해결할거다.

 

- 입력

보통 StringTokenizer를 통해 받는것과 달리 데이터가 110111 이런식으로 들어온다. 

이 문자열 데이터를 정수로 바꿔주는 방법에는 여러가지 존재한다. 아래 코드에 주석으로 

코드는 표현해놨다. 문자열을 -> 문자 -> 정수로 바꿔줘야하는데

문자열을 -> 문자로 바꾸는 방법은 2가지가있다.(문자열 s를 기준)

1. s.charAt() //평상시 자주사용방법

2. char[] charArr = s.toCharArray();  //문자열을 char형 배열로 만듬, 프로그래머스에서 자주사용

프로그래머스에서는 return값으로 답을 제출하기때문에 2번을 알아두면 유용하다.

문자 -> 정수(3가지 방법)

1. s.charAt() - '0';  //아스키 코드를 활용해서 문자를 정수로 만든다. - 가장추천

2. Charater.getNumericValue(s.charAt())  //getNumeriValue메소드를 사용하는건데 자주사용하진 않는다

3. Integer.parseInt(StringvalueOf(s.charAt()))   //Integer.parseInt()는 문자열만 정수로 바꿔준다 그러므로 문자를 문자열로 만들어주고 정수로 바꾸는 방식이다. 

 

- 푸는 방법 코드

위에 정수로 바꾼값을 map[N+1][M+1]에 다 담아주고 bfs를 만들어준다.

미리 nearY[]와 nearX[]를 통해 칸에서 상하좌우 칸에 있는 칸으로 이동하기 쉽게 해준다.

이를 통해 반복문(i<4)만들어주고 이동해야하는 칸의 y가 0보다 크고 N보다 작거나 같아야 하고

x도 0보다 크고 M보다 작거나 같아야 하므로 이를 참고해 조건을 만들어준다. 추가로 map[][]의 값이 

0이면 이동못하는것과 전에 방문한지를 체크하는것까지 조건으로 넣어주면된다.

마지막으로 길이를 체크하는게 관건인데 더 보기쉽게 Node클래스 안에 len변수를 만들어 증가시키는 방식도

있지만 더 간단하게 map[][]의 값을 len이라고 생각하면된다. 아래 코드를 보면 쉽게 이해될 것이다.

 

예제 입력 예시

4 6
110110
110110
111111
111101

예제 출력 예시

9

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//p2178

public class P2178 {
    static int N, M;
    static int map[][];
    static boolean visited[][];
    static int[] nearX = {-1, 0, 1, 0};
    static int[] nearY = {0, 1, 0, -1};

    private static class Node {  //각 칸의 x,y
        int x, y;
        public Node(int y, int x) {
            this.x = x;
            this.y = y;
        }
    }

    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());  //열
        visited = new boolean[N + 1][M + 1];
        map = new int[N + 1][M + 1];

        //입력받아서 map에 저장
        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 1; j <= M; j++) {
                // map[i][j] = Character.getNumericValue(s.charAt(j - 1)); //char to integer
                map[i][j] = s.charAt(j-1) - '0'; //char to integer, 아스키코드사용
            }
        }
        //너비우선탐색
        bfs();
        System.out.println(map[N][M]);
    }

    private static void bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(1, 1));
        visited[1][1] = true;
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();  //현재 노드
            for (int i = 0; i < 4; i++) {  //현재 노드에서 갈 수 있는 방향 4가지
                int curNearY = curNode.y + nearY[i];
                int curNearX = curNode.x+ nearX[i];
                //조건문성립: 존재하는칸, 값이 0아니며, 아직방문안함
                if (curNearX > 0 && curNearY > 0 && curNearY <= N && curNearX <= M && map[curNearY][curNearX] != 0 && visited[curNearY][curNearX] == false) {
                    queue.offer(new Node(curNearY, curNearX));
                    map[curNearY][curNearX] = map[curNode.y][curNode.x]+1;
                    visited[curNearY][curNearX] = true;
                }
            }
        }
    }
}

 

 

 

 

문제 출처

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

2178번: 미로 탐색