[알고리즘] 백준 2178 미로 탐색 -bfs, dfs- 자바 코틀린

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

2178번: 미로 탐색

 

 

시작점은 주어지고 마지막 좌표까지 가는데 최소거리를 구하는 문제이다. (무조건 끝까지 갈 수 있다는 조건이 붙음)

이전에 풀었던 백준 1012 유기농배추와 비슷하면서도 좀 더 생각을 해야하는 문제였다. 

 

마찬가지로 BFS를 돌리면서 동서남북을 찾는데 한칸 진행할 때마다 가중치를 1씩 더해나가는 로직이 필요했다. 이때 가중치는 map이 0과 1로 되어 있으므로 도착한 칸이 1이라면(갈수있는칸) 해당 칸의 값에 이전 칸의 값의 +1을 넣어주면 됬다. (이전 칸은 동서남북 탐색을 할때 알 수 있다.) 

 

 

처음 풀고 맞았겠다 싶어서 샘플을 붙이면 계속 0이뜨고 이상했다. (삽질 ㅠㅠ) 디버깅을 돌렸을때도 눈치 못챘는데 배열을 잘 못 줬었다. 행과 열 크기를 입력받고 항상 이차원배열에 대입할 때 순간 햇갈려서 반대로하는 경우가 많은 것 같다.  

항상 조심하자...!!ㅎㅎ

 

 

 

다음과 같이 해결했다.

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

public class Main {

    private static int[][] map;
    private static boolean[][] visited;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 행
        int M = sc.nextInt(); // 열

        map = new int[M + 2][N + 2];
        visited = new boolean[M + 2][N + 2];

        sc.nextLine();
        for (int i = 1; i < N + 1; i++) {
            String str = sc.nextLine();
            for (int j = 1; j < M + 1; j++) {
                map[j][i] = str.charAt(j - 1) - '0';
            }
        }

        bfs(1, 1);
        System.out.println(map[M][N]);
    }


    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if (!(map[x2][y2] == 0 || visited[x2][y2] == true)) {
                    visited[x2][y2] = true;
                    queue.offer(new Point(x2, y2));
                    //이전좌표의 값의 + 1을 가짐 (최소거리 누적해서 더해나감)
                    if (i == 0) { //왼쪽으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y] + 1;
                    } else if (i == 1) {//상단으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y] + 1;
                    } else if (i == 2) {//오른쪽으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y]+ 1;
                    } else {//밑으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y] + 1;
                    }
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

 

이 문제의 핵심이다. 기억해두자 (다른 풀이방법도 있겠지만..) 

for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if (!(map[x2][y2] == 0 || visited[x2][y2] == true)) {
                    visited[x2][y2] = true;
                    queue.offer(new Point(x2, y2));
                    //이전좌표의 값의 + 1을 가짐 (최소거리 누적해서 더해나감)
                    if (i == 0) { //왼쪽으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y] + 1;
                    } else if (i == 1) {//상단으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y] + 1;
                    } else if (i == 2) {//오른쪽으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y]+ 1;
                    } else {//밑으로 이동한 상태
                        map[x2][y2] = map[point.x][point.y] + 1;
                    }
                }
            }

 

 

 

[2020-09-18 복습 풀이]

과거(위 코드)에 왜저렇게 풀었는지 모르겠다. ㅋㅋㅋㅋ  동서남북을 왜 여기서..

밑에 풀이가 찐 풀이입니다..

참고로 한 줄의 String을 받을 때 nextLine() 말고 next() 를 써야 버퍼가 안걸립니다.  next()를 애용합시다. 

 

[Java]

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

public class Main {

    private static int N; //1차원
    private static int M; //2차원
    private static int[][] map;
    private static boolean[][] isVisited;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N + 2][M + 2];
        isVisited = new boolean[N + 2][M + 2];
        for (int i = 0; i < N; i++) {
            String line = sc.next();
            for (int j = 0; j < line.length(); j++) {
                int num = line.charAt(j) - '0';
                map[i + 1][j + 1] = num;
            }
        }
        bfs(1, 1);
        System.out.println(map[N][M]);
    }

    static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        isVisited[x][y] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if (map[x2][y2] == 1 && !isVisited[x2][y2]) {
                    isVisited[x2][y2] = true;
                    queue.offer(new Point(x2, y2));
                    map[x2][y2] = map[point.x][point.y] + 1;
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


}

 

 

 

[Kotlin]

import java.util.*


private var N: Int = 0 //1차원
private var M: Int = 0 //2차원
private var map: Array<IntArray>? = null
private var isVisited: Array<BooleanArray>? = null
private val dx = intArrayOf(-1, 0, 1, 0)
private val dy = intArrayOf(0, -1, 0, 1)


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    M = sc.nextInt()
    map = Array(N + 2) { IntArray(M + 2) }
    isVisited = Array(N + 2) { BooleanArray(M + 2) }
    for (i in 0 until N) {
        val line = sc.next()
        for (j in 0 until line.length) {
            val num = line[j] - '0'
            map!![i + 1][j + 1] = num
        }
    }
    bfs(1, 1)
    println(map!![N][M])
}

fun bfs(x: Int, y: Int) {
    val queue = LinkedList<Point>()
    queue.offer(Point(x, y))
    isVisited!![x][y] = true
    while (!queue.isEmpty()) {
        val point = queue.poll()
        for (i in 0..3) {
            val x2 = point.x + dx[i]
            val y2 = point.y + dy[i]
            if (map!![x2][y2] == 1 && !isVisited!![x2][y2]) {
                isVisited!![x2][y2] = true
                queue.offer(Point(x2, y2))
                map!![x2][y2] = map!![point.x][point.y] + 1
            }
        }
    }
}

data class Point(var x: Int, var y: Int)

github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%202178%20%EB%AF%B8%EB%A1%9C%20%ED%83%90%EC%83%89/%EB%B3%B5%EC%8A%B5

mtjin/algorithm_practice