99클럽 코테 스터디 35일차 게임 맵 최단거리

📝 문제

프로그래머스

 

🔥 시도해본 접근 방식

1. 주어진 행렬을 통해 재귀 DFS을 사용

2. 목표지점까지 이동 할 수 있는 모든 경우의 수 들의 이동 칸수를 리스트에 기록하여 최소값을 답으로 반환

위와 같은 방법으로 접근하였다.

 

1️⃣ 첫번째 시도

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    int[][] maps;
    boolean[][] visited;

    int rowSize;
    int columnSize;

    // 목표 지점에 도달 가능한 루트의 이동한 칸 수 리스트
    List<Integer> cntList;

    // 상, 하, 좌, 우
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};

    public int solution(int[][] maps) {
        this.maps = maps;
        this.rowSize = maps.length;
        this.columnSize = maps[0].length;
        this.visited = new boolean[this.rowSize][this.columnSize];
        this.cntList = new ArrayList<>();

        recursiveDfs(0, 0, 0);

        Collections.sort(this.cntList);

        if (this.cntList.isEmpty()) {
            return -1;
        } else {
            return this.cntList.get(0);
        }
    }

    private void recursiveDfs(int x, int y, int cnt) {
        cnt++;
        this.visited[x][y] = true;

        // x와 y가 마지막 목표지점에 도달했다면 list에 이동한 칸수 기록
        if (x == this.rowSize - 1 && y == this.columnSize - 1) {
            this.cntList.add(cnt);
            return;
        }

        // 현재 위치에서 이동 가능한 방향으로 이동
        for (int i = 0; i < 4; i++) {
            int nextX = x + this.dx[i];
            int nextY = y + this.dy[i];

            if (nextX >= 0 &&
                    nextX <= this.rowSize - 1 &&
                    nextY >= 0 &&
                    nextY <= this.columnSize - 1 &&
                    this.maps[nextX][nextY] == 1 &&
                    !this.visited[nextX][nextY]
            ) {
                recursiveDfs(nextX, nextY, cnt);
            }
        }
    }
}

위와 같이 작성하여 제출 하였지만 여러 케이스에서 실패 하였다.

자세히 보니 위 코드에서는 visited 배열의 원소 값이 재귀호출에서 돌아오는 경우 원소의 상태를 복구하지 않고 있는 결함을 발견하였고,

백트래킹 처리를 추가하였다.

2️⃣ 두번째 시도

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    int[][] maps;
    boolean[][] visited;

    int rowSize;
    int columnSize;

    // 목표 지점에 도달 가능한 루트의 이동한 칸 수 리스트
    List<Integer> cntList;

    // 상, 하, 좌, 우
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};

    public int solution(int[][] maps) {
        this.maps = maps;
        this.rowSize = maps.length;
        this.columnSize = maps[0].length;
        this.visited = new boolean[this.rowSize][this.columnSize];
        this.cntList = new ArrayList<>();

        recursiveDfs(0, 0, 0);

        Collections.sort(this.cntList);

        if (this.cntList.isEmpty()) {
            return -1;
        } else {
            return this.cntList.get(0);
        }
    }

    private void recursiveDfs(int x, int y, int cnt) {
        cnt++;
        this.visited[x][y] = true;

        // x와 y가 마지막 목표지점에 도달했다면 list에 이동한 칸수 기록
        if (x == this.rowSize - 1 && y == this.columnSize - 1) {
            this.cntList.add(cnt);
            this.visited[x][y] = false; // 백트래킹
            return;
        }

        // 현재 위치에서 이동 가능한 방향으로 이동
        for (int i = 0; i < 4; i++) {
            int nextX = x + this.dx[i];
            int nextY = y + this.dy[i];

            if (nextX >= 0 &&
                    nextX < this.rowSize &&
                    nextY >= 0 &&
                    nextY < this.columnSize &&
                    this.maps[nextX][nextY] == 1 &&
                    !this.visited[nextX][nextY]
            ) {
                recursiveDfs(nextX, nextY, cnt);
            }
        }

        this.visited[x][y] = false; // 백트래킹
    }
}

위와 같이 코드를 수정하였지만 아쉽게도 효율성 테스트에서는 여전히 모두 실패하였다.

BFS로 풀면 맨 처음에 도출된 값이 최소 횟수인 것이 보장되므로 BFS로 풀어야 하는 것 같다.

✨ 성공 코드

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

class Solution {
    // 상, 하, 좌, 우
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};

    public int solution(int[][] maps) {
        int rowSize = maps.length;
        int columnSize = maps[0].length;

        Block[][] blocks = new Block[rowSize][columnSize];

        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < columnSize; j++) {
                blocks[i][j] = new Block(i, j, maps[i][j]);
            }
        }

        Queue<Block> queue = new LinkedList();
        blocks[0][0].cnt = 1;
        blocks[0][0].visited = true;
        queue.offer(blocks[0][0]);

        while (!queue.isEmpty()) {
            Block cur = queue.poll();

            if (cur.x == blocks.length - 1 && cur.y == blocks[0].length - 1) {
                return blocks[cur.x][cur.y].cnt;
            }

            for (int i = 0; i < 4; i++) {
                int newX = cur.x + this.dx[i];
                int newY = cur.y + this.dy[i];

                if (newX >= 0 &&
                        newX < blocks.length &&
                        newY >= 0 &&
                        newY < blocks[0].length &&
                        blocks[newX][newY].data == 1 &&
                        !blocks[newX][newY].visited
                ) {
                    blocks[newX][newY].cnt = cur.cnt + 1;
                    queue.offer(blocks[newX][newY]);
                    blocks[newX][newY].visited = true;
                }
            }
        }

        return -1;
    }

    static class Block {
        int x;
        int y;
        int data;
        boolean visited;
        int cnt;

        public Block(int x, int y, int data) {
            this.x = x;
            this.y = y;
            this.data = data;
            this.visited = false;
        }
    }
}