알고리즘 스터디 7월 3주차 문제3 (미로 탐색)

Jul 15, 2020

Post Series

문제#

링크로 대체

풀이 및 주저리..

BFS를 활용해서 풀어본 문제이다. 맵을 먼저 받은후에 갈수 있는 길을 BFS 로 탐색하며 진행하여 맵의 모든 위치의 최소로 갈 수 있는 방법을 구하고 마지막에 맵의 끝을 출력하게 해주었다. 백준 단계별로 풀어보기를 하다보니.. 참 비슷한 유형의 문제를 계속 반복하면서 푸는 것 같아서 실력증진에 조금 문제가 있을 것 같은데.. 후에는 오프라인 강의때 풀어봤던 문제 하나 그리고 단계별 문제 2문제 정도를 풀어보던가 해야겠다. 정답 비율 자체는 상당히 낮은데.. 이게 36%인건.. 말이 안되는 것 같다. 아마 이 BFS DFS 들어와서 많이들 힘들어서 그런 정답률이 나오는건지.. 아무튼 쉽게 문제를 풀 수 있었다.

코드

package baekjoon.algorithm.dfsbfs;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Problem2178 {
    static final int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        char[][] map = new char[n][m];
        int[][] moveMap = new int[n][m];

        for (int i = 0; i < n; i++) {
            map[i] = sc.nextLine().toCharArray();
        }
        Queue<Integer> que = new LinkedList<>();
        que.add(0);
        que.add(0);
        moveMap[0][0] = 1;

        while (!que.isEmpty()) {
            int x = que.poll();
            int y = que.poll();

            for (int i = 0; i < 4; i++) {
                int mX = x + dx[i];
                int mY = y + dy[i];

                if (mX >= 0 && mX < n && mY >= 0 && mY < m && map[mX][mY] == '1' && moveMap[mX][mY] == 0) {
                    moveMap[mX][mY] = moveMap[x][y] + 1;
                    que.add(mX);
                    que.add(mY);
                }
            }
        }

        System.out.println(moveMap[n-1][m-1]);
    }
}

기억에 남길 것!

가중치가 1인 길찾기는 = BFS