[백준] 쉬운 최단거리 JAVA

반응형

728x90

[백준] 쉬운 최단거리 - SILVER I 14940번

---

접근

• bfs

---

풀이

바로 전에 풀었던 미로 탐색의 문제와 유사한 문제로 도착점이 주어지고 도착점을 제외한 모든 지점에서 도착점까지의 최단 거리를 구하는 문제이다. 거꾸로 생각해 도착점으로 주어지는 곳에서 시작해 다른 모든 지점에 도달하는데 최단 거리를 구하면 된다. 역시나 갈 수 없는 곳이 존재하고 애초에 0으로 갈 수 없는 곳은 최단거리가 0이 되고 0이 아니지만 도달하지 못하는 지점은 -1을 출력해야 한다.

 

이번 문제도 최단 경로를 구해야 하기 때문에 bfs를 사용했고 미로 탐색 문제의 코드를 그대로 들고 와 수정하기로 했다.

2024.09.07 - [알고리즘/코딩테스트-백준] - [백준] 미로 탐색 JAVA

[백준] 미로 탐색 JAVA

그런데 bfs와 dfs문제의 코드야 완전 기본적인 베이스 코드기 때문에 큰 문제가 없는데 이런 다른 조건이 들어갔던 코드를 그대로 복사해 쓰는 건 언제나 조심하고 꼼꼼히 살펴봐야 하는 거 같다. 문제 내용 또한 비슷해 놓치고 수정하지 않은 사소한 부분에서 문제가 생겨 엉뚱한 부분에서 삽질을 좀 했었다. 또 찾기가 힘들 수 밖에 없는 게 사소한 부분이라 적당한 테스트 케이스는 또 정상적으로 동작을 하기 때문에 더 찾기가 힘든 거 같기도 하다.

    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};

    private static class Step{
        private final int x;
        private final int y;
        private final int count;

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

기존 객체와 가로 세로 움직임을 위한 배열은 그대로 사용한다.

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        int targetX = 0;
        int targetY = 0;
        
        int[][] maze = new int[n][m];

        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(result[i], -1);
        }

출력문의 양이 많기 때문에 BufferedWriter를 사용해 주었고 목표지점으로 주어지는 좌표를 저장하기 위한 변수와 결과 저장을 위한 배열을 선언해 주었다. 결과 배열은 모두 -1로 초기화해 주어 도달하지 못하는 부분은 -1인 채로 남게 된다.

	for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(line[j]);
                if (maze[i][j] == 2) {
                    targetX = i;
                    targetY = j;
                }

                if (maze[i][j] == 0) {
                    result[i][j] = 0;
                }
            }
        }

미로를 초기화하는 과정에 목표지점 좌표를 설정해 주었고 애초에 0으로 움직일 수 없는 칸은 결과 배열도 다 0으로 만들어 주었다.

	result[targetX][targetY] = 0;
        bfs(maze, n, m, result, targetX, targetY);

        for (int[] row : result) {
            for (int column : row) {
                bw.write(column +" ");
            }
            bw.write("\n");
        }

이번 문제는 출발 지점으로 사용될 목표지점은 칸 수를 세지 않기 때문에 0으로 초기화해 주었다.

private static void bfs(int[][] maze, int n, int m, int[][] shortCut, int targetX, int targetY) {
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(targetX,targetY,0));

        boolean[][] isVisited = new boolean[n][m];
        isVisited[targetX][targetY] = true;

        while (!queue.isEmpty()) {
            Step step = queue.poll();
            int x = step.x;
            int y = step.y;
            int count = step.count;

            shortCut[x][y] = count;

bfs의 코드는 큰 변경은 없고 사소한 부분들만 변경되었는데 우선 출발 좌표 칸을 세지 않으므로 count는 0인 상태에서 시작한다. 그리고 출발지점의 방문체크를 해주어야 하는데 저번 문제는 0, 0에서 출발하여 isVisited [0][0] = true로 되어있던걸 못 보고 고치지 않아서 다른 부분에 많은 삽질을 했다. 반복문에선 큐에서 꺼내는 지점에 도달할 때가 최단 경로이기 때문에 결과 배열을 채워준다.

 	    for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == 0) {
                    continue;
                }

                if(isVisited[nx][ny])
                    continue;

                queue.offer(new Step(nx, ny, count + 1));
                isVisited[nx][ny] = true;
            }

아래 코드는 이전과 동일하고 특정 지점에 도착하면 종료하는 코드가 빠지고 모든 경로를 다 탐색하여야 종료가 된다.

---

전체 코드

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

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

    private static class Step{
        private final int x;
        private final int y;
        private final int count;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        int targetX = 0;
        int targetY = 0;

        int[][] maze = new int[n][m];

        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(result[i], -1);
        }

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(line[j]);
                if (maze[i][j] == 2) {
                    targetX = i;
                    targetY = j;
                }

                if (maze[i][j] == 0) {
                    result[i][j] = 0;
                }
            }
        }


        result[targetX][targetY] = 0;
        bfs(maze, n, m, result, targetX, targetY);

        for (int[] row : result) {
            for (int column : row) {
                bw.write(column +" ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs(int[][] maze, int n, int m, int[][] shortCut, int targetX, int targetY) {
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(targetX,targetY,0));

        boolean[][] isVisited = new boolean[n][m];
        isVisited[targetX][targetY] = true;

        while (!queue.isEmpty()) {
            Step step = queue.poll();
            int x = step.x;
            int y = step.y;
            int count = step.count;

            shortCut[x][y] = count;


            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == 0) {
                    continue;
                }

                if(isVisited[nx][ny])
                    continue;

                queue.offer(new Step(nx, ny, count + 1));
                isVisited[nx][ny] = true;
            }
        }
    }
}

수정 안 된 곳에서 문제가 발생해 출력문을 찍어보고 출력문을 제거하지 않은 채 제출을 했다 메모리 초과가 나 뭐가 잘못된 건지 한참을 돌아봤다. 그냥 처음부터 다시 짰으면 한 두 번이면 통과했을 문제를 몇 번이나 제출을 한 건지 모르겠다.