[프로그래머스] 게임 맵 최단거리 (JAVA)

soluinoon·2023년 5월 5일

알고리즘 저지

목록 보기

6/13

개요

프로그래머스 고득점 kit의 bfs/dfs 문제인 게임 맵 최단거리를 풀어봤습니다. 효율성 문제에서 막혔었는데, 생각해보기 좋은 문제라서 오답 과정과 함께 공유합니다!!

문제

문제 링크

풀이 과정

DFS로 진행

풀이에는 문제가 없지만, 예시에서 이상한 루트로 먼저 들어가게 됩니다.

이런 방식으로 먼저 들어간다면 참 좋겠지만, 저는 상하좌우로 진행하기 때문에 분기점에서 아래와 같은 루트를 먼저 검사하게 됩니다.

최단거리가 아니죠? 따라서 백트레킹 비슷하게 밖에서 재귀를 들어갈 때 방문처리를 해주고, 밖에서 방문처리를 취소해서 진행했습니다.

	...
	visited[i][j] = true;
    foo(i, j);
    visited[i][j] = false;
    ...

이렇게 되면 모든 경우의 수를 검사합니다. 따라서 효율성 검사에서 통과가 불가능합니다.

BFS로 진행

그렇기 때문에 BFS를 사용해서 깊게 보단, 얕게 탐색하면서 탈출점에 도착하면 함수를 종료하는 방향으로 만들었습니다.
하지만 여기서도 효율성 문제에 걸리는 부분이 있습니다!!

큐에 노드를 삽입 후, 꺼낼 때 방문처리를 하는 방식

while (!q.isEmpty()) {
	Node cur = q.poll();
    
	// 큐에서 뽑고 트루로 함.
    visited[cur.row][cur.col] = true;

    if (cur.row == maps.length - 1 && cur.col == maps[0].length - 1) {
        answer = cur.count;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nextRow = cur.row + mrow[i];
        int nextCol = cur.col + mcol[i];
        
        if (canMove(nextRow, nextCol, maps)) {
            q.add(new Node(nextRow, nextCol, cur.count + 1));
        }
        
    }
}

정확성은 통과하지만, 효율성은 통과할 수 없습니다. 그 이유는 큐에 노드를 삽입하고 꺼낼 때 방문처리하기 때문에
특정 노드가 4방향 검사를 진행할 때, 방문처리가 안됐을 수 있기 때문입니다. 따라서 중복된 노드가 큐에 들어갈 수 있습니다.
따라서 다음과 같이 수정하면 효율성 테스트도 통과할 수 있습니다.

큐에 노드를 삽입할 때 방문처리를 하는 방식

while (!q.isEmpty()) {
	Node cur = q.poll();

    if (cur.row == maps.length - 1 && cur.col == maps[0].length - 1) {
        answer = cur.count;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nextRow = cur.row + mrow[i];
        int nextCol = cur.col + mcol[i];
        
        if (canMove(nextRow, nextCol, maps)) {
        	// 큐에서 넣을 때 트루로 함.
    		visited[cur.row][cur.col] = true;
            q.add(new Node(nextRow, nextCol, cur.count + 1));
        }
        
    }
}

이렇게 만들면 큐에 들어갈 때 바로 방문처리를 하기 때문에 다음 꺼내는 노드부터 바로 반영이 됩니다.
따라서 중복되는 노드가 들어가지 않고, 효율성 검사를 무사히 통과할 수 있습니다.

전체코드

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

// start 1:14

class Solution {
    static int answer = -1;
    static boolean[][] visited;
    // 상 하 좌 우 
    static int[] mrow = {-1, 1, 0, 0};
    static int[] mcol = {0, 0, -1, 1};
    
    
    public int solution(int[][] maps) {
        visited = new boolean[maps.length][maps[0].length];
        
        bfs(0, 0, maps);
        
        return answer;
    }
    
//     public void dfs(int row, int col, int count, int[][] maps) {
//         // System.out.printf("row=%d, col=%d, count = %d\n", row, col, count);
//         if (visited[row][col]) {
//             return;
//         }
//         if (row == maps.length - 1 && col == maps[0].length - 1) {
//             if (answer == -1 || answer > count)
//                 answer = count;
//             return;
//         }
        
//         for (int i = 0; i < 4; i++) {
//             int nextRow = row + mrow[i];
//             int nextCol = col + mcol[i];
            
//             if (canMove(nextRow, nextCol, maps)) {
//                 visited[row][col] = true;
//                 dfs(nextRow, nextCol, count + 1, maps);
//                 visited[row][col] = false;
//             }
//         }
//     }
    
    public void bfs(int row, int col, int[][] maps) {
        Queue<Node> q = new LinkedList<>();
        
        q.add(new Node(0, 0, 1));
        visited[0][0] = true;
        
        while (!q.isEmpty()) {
            Node cur = q.poll();
            

        // System.out.printf("row=%d, col=%d, count = %d\n", cur.row, cur.col, cur.count);

            if (cur.row == maps.length - 1 && cur.col == maps[0].length - 1) {
                answer = cur.count;
                // System.out.println("catch");
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nextRow = cur.row + mrow[i];
                int nextCol = cur.col + mcol[i];
                
                if (canMove(nextRow, nextCol, maps)) {
                    // System.out.printf("add row=%d, col=%d, count = %d\n", cur.row, cur.col, cur.count);
                    visited[nextRow][nextCol] = true;
                    q.add(new Node(nextRow, nextCol, cur.count + 1));
                }
                
            }
        }
    }
    
    class Node {
        int row;
        int col;
        int count;
        
        public Node(int row, int col, int count) {
            this.row = row;
            this.col = col;
            this.count = count;
        }
    }
    
    public boolean canMove(int row, int col, int[][] maps) {
        return row >= 0 && row < visited.length && col >= 0 && col < visited[0].length
                    && !visited[row][col] && maps[row][col] != 0;
    }
}