[백준] no14940: 쉬운 최단거리

문제

* 배열의 세로(N)와 가로(M)와 0,1,2로 이루어진 이중 배열이 주어진다.
* 이 때, 2는 딱 한칸만 주어진다.
* 2로부터 각 칸까지의 거리를 모두 구하시오
* 단, 0일경우 이동이 불가한 칸이기에 0을 입력
* 단, 1이지만 도달할 수 없는 칸은 -1을 입력

문제 링크 : https://www.acmicpc.net/problem/14940

---

원리

1. BFS를 위한 Node클래스

private static class Node {
    private int Y, X, Cnt;
    public Node(int y, int x, int cnt) {
        Y = y;
        X = x;
        Cnt = cnt;
    }
}

2. BFS 공식

: 여기서 시작용 int 값인 baseY와 baseX는 BFS()를 호출하는 main메소드에서 얻어 class내 static 필드로 저장해뒀다.

private static void BFS() {
    Deque<Node> dq = new ArrayDeque<>();
    dq.add(new Node(baseY, baseX, 0));
    visit[baseY][baseX] = true;

    while(!dq.isEmpty()) {
        Node now = dq.poll();

        for(int move=0 ; move<4 ; move++) {
            int nextY = now.Y + ver[move];
            int nextX = now.X + hor[move];
            if(nextY<0 || N<=nextY || nextX<0 || M<=nextX) continue;

            if(map[nextY][nextX].equals("0")) continue;

            if(!visit[nextY][nextX]) {
                dq.add(new Node(nextY, nextX, now.Cnt+1));
                distance[nextY][nextX] = now.Cnt + 1;
                visit[nextY][nextX] = true;
            }
        }
    }
}

 

---

나의 코드

[메모리초과] 시도1. BFS를 이용한 좌표이동 공식

: 모든 경우를 돌면서 일일히 구하므로, 메모리 소모가 심하다.

: 따로 출력용 이중배열을 두지않고 계산과 함께 BufferedWriter에 입력하기 위해 작성한 방식이나,

  오히려 메모리 소모가 심하다.

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class no14940 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N, M, baseY, baseX;
    private static String[][] map;
    private static int[] ver = {-1, 1, 0, 0};
    private static int[] hor = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new String[N][M];
        boolean check = false;

        for(int i=0; i<N ; i++) {
            map[i] = br.readLine().split(" ");
            if(!check) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j].equals("2")) {
                        baseY = i;
                        baseX = j;
                        check = true;
                        break;
                    }
                }
            }
        }

        for(int y=0; y<N; y++) {
            for(int x=0; x<N; x++) {
                if(y==baseY && x==baseX) bw.append("0 ");
                else if(map[y][x].equals("0")) bw.append("0 ");
                else bw.append(""+BFS(y,x)+" ");
            }
            bw.write("\n");
        }

        bw.close();
    }

    private static int BFS(int startY, int startX) {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(startY, startX, 0));
        boolean[][] visit = new boolean[N][M];
        visit[startY][startX] = true;
        int count = -1;

        while(!dq.isEmpty()) {
            Node now = dq.poll();

            if(now.Y==baseY && now.X==baseX) {
                count = now.Cnt;
                return count;
            }

            for(int move=0 ; move<4 ; move++) {
                int nextY = now.Y + ver[move];
                int nextX = now.X + hor[move];
                if(nextY<0 || N<=nextY || nextX<0 || N<=nextX) continue;

                if(map[nextY][nextX].equals("0")) continue;

                if(!visit[nextY][nextX]) {
                    dq.add(new Node(nextY, nextX, now.Cnt+1));
                    visit[nextY][nextX] = true;
                }
            }
        }

        return count;
    }

    private static class Node {
        private int Y;
        private int X;
        private int Cnt;
        public Node(int y, int x, int cnt) {
            Y = y;
            X = x;
            Cnt = cnt;
        }
    }
}

 

[성공] 시도2. 목표지점부터 순차적으로 각 칸에 거리값을 대입해주는 BFS

: 위의 방식과 접근법이 반대로 된다.

: 값이 2인 칸부터 순차적으로 2차원 배열(map)을 순회하며, 각 칸에 이동거리를 입력하면서 BFS를 진행한다.

: 이때, 한 개의 visit 처리로 하기때문에 첫 번째 시도에 비해 중복방문이 없다.

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

public class no14940 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N, M, baseY, baseX;
    private static String[][] map;
    private static int[][] distance;
    private static boolean[][] visit;
    private static int[] ver = {-1, 1, 0, 0};
    private static int[] hor = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        // 입력 구간
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new String[N][M];
        boolean check = false;

        for(int i=0; i<N ; i++) {
            map[i] = br.readLine().split(" ");
            if(!check) { // 이 조건이 없으면, map 초기화시 모든칸을 이중반복이 돌게 됨(한번 2을 찾으면 그 뒤론 반복이 필요없으므로 설정해둠)
                for (int j = 0; j < M; j++) {
                    if (map[i][j].equals("2")) {
                        baseY = i;
                        baseX = j;
                        check = true;
                        break;
                    }
                }
            }
        }

        // 실질적인 탐색 구간
        visit = new boolean[N][M];
        distance = new int[N][M];
        BFS();

        // distance에 있는 모든 값을 출력용으로 입력
        for(int Y=0; Y<N; Y++) {
            for(int X=0; X<M; X++) {
                if(!visit[Y][X] && map[Y][X].equals("1")) bw.write("-1 "); // 도달 못한칸은 visit가 false상태이며, 해당칸이 활성화된 칸이면 1이기 때문
                else bw.write(distance[Y][X] + " ");
            }
            bw.write("\n");  // 한 줄 입력완료
        }

        bw.close();
    }

    private static void BFS() {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(baseY, baseX, 0)); // 첫 칸
        visit[baseY][baseX] = true;

        while(!dq.isEmpty()) {
            Node now = dq.poll();

            for(int move=0 ; move<4 ; move++) { // 현재칸으로부터 상하좌우 좌표이동을 위한 4번 반복
                int nextY = now.Y + ver[move];
                int nextX = now.X + hor[move];
                if(nextY<0 || N<=nextY || nextX<0 || M<=nextX) continue; // 범위를 벗어나면 패스

                if(map[nextY][nextX].equals("0")) continue; // 0이면 못가는 칸이므로 패스(초기화 되어 어차피 0으로 되어있음)

                if(!visit[nextY][nextX]) {
                    dq.add(new Node(nextY, nextX, now.Cnt+1));  // 다음칸이 계산한 적이 없고, 이동가능한 경우 이동
                    distance[nextY][nextX] = now.Cnt + 1;  // 각 칸의 거리를 map과 같은 크기의 distance에 기록
                    visit[nextY][nextX] = true; // 방문체크
                }
            }
        }
    }

    private static class Node {
        private int Y, X, Cnt;
        public Node(int y, int x, int cnt) {
            Y = y;
            X = x;
            Cnt = cnt;
        }
    }
}

---

레퍼런스

참고링크 : kry-p님의 벨로그