게임 맵 최단거리 (Java, BFS, 프로그래머스)

BFS, DFS 문제를 풀때는 다음과 같은 순서로 사고를 하도록 하자.

 

1. 재귀적인 특징을 가지거나 백트래킹을 이용해야 하는 완전탐색의 문제를 풀어야 할 때는 DFS 

e.g. 순열 조합

깊이를 이용한 문제를 풀어야 할 때는 BFS 

e.g. 최단 거리 구하기

 

1-1. 최단 거리를 구하는 문제에서 DFS를 사용하게 되면 매 노드를 방문 표시를 하면서 경우의 수를 구해나가기 때문에 다시 무를 방법이 없다. (백트래킹을 통해 최적의 해를 구하지 않는다면)

매 순간 최선의 선택을 하는 BFS가 최단 거리를 구할 때 가장 적합하다.

 

2. 주어지는 파라미터를 전역 변수로 넘긴다. 필수는 아니지만 코드가 더 간결해진다.

2-1. 2차원 배열의 경우 y,x 좌표를 받는 노드 클래스를 생성한다. 이 역시 필수는 아니지만 y,x를 같이 다루기에 더 편리하다.

2-2. 방문 표시를 하는 배열은 메인 메서드에서 DFS, BFS를 부르기 전에 선언한다. 

2-3. 이동 방향이 정해진 문제라면 전역 상수로 이동 방향을 미리 정의해둔다.

e.g. 상하좌우로만 움직일 수 있다면 

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

혹은 

    int[][] D = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

3. BFS에는 현재 위치를 파라미터로 넘겨받는다.

3-1. 매 선택을 담는 자료구조는 BFS 내에서 생성한다.

3-2. 시작 위치를 방문 처리하고 현재 위치와 depth의 노드를 생성하며 큐에 넣어준다.

3-3. BFS는 현재 위치만 파라미터로 받고 depth에 대한 처리는 노드 클래스에서 한다.

 

4. '큐가 비어있지 않은 동안'이 유일한 순회 조건이다. 내부에서 계속 노드를 생성하여 큐에 넣어줄 것이기때문에. (double for loop를 쓰지 않는다.)

4-1. 큐에서 값을 하나 꺼낸다.

4-2. 탈출 조건을 작성한다. 탈출 조건은 문제에서 주어진 것을 판단하여 이용한다.

 

5. 2-3에서 미리 정해둔 상수값을 돌면서 '이동할 수도 있는' 노드의 좌표를 임시 생성한다.

5-1. 임시 노드가 배열에서 벗어나지는 않았는지, 혹은 문제에서 주어진 제한 조건을 어기지는 않는지, 방문한 적이  없는지 등을 체크한다.

5-1-1. 이때 노드가 index(zero-based)라면 >= 0, < length의 조건으로 체크한다. 항상 index인지 length인지를 체크하면서 생각한다.

5-1-2. 배열을 벗어났는지에 대한 체크는 아래와 같이 2가지 방식으로 할 수 있다.

배열을 벗어나는 경우에 대해서 continue로 스킵하거나
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

배열이 벗어나지 않는 범위를 정해서 그 내부로 로직을 계속 진행.
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
}

5-2. 체크 조건을 만족한다면 방문 여부를 체크하고 큐에 임시 노드의 좌표를 넣어준다.

 

(Under the hood) 

6. 시작 위치에서 새로 갈 수 있는 노드들이 큐에 쌓여있다. (한 loop에 최대 3개.)

6-1. 이미 지나온 위치들은 visited[x][y] = true로 처리되어있으므로 다시 되돌아가지 않는다.

6-2. 만약 갈 수 없는 지역과 이미 지나온 곳으로 둘러싸인다면 그 노드는 소멸한다. 

q.poll()로 큐에서 제거했지만 이후에 제한 조건에 의해 q.offer()를 하지 못 하므로.

6-3. 마지막 노드까지 갈 수 있는 노드는 매순간 살아남은 노드들과 매순간 최선의 선택을 한 노드들 뿐이므로 마지막 결정 조건에 도달한 depth는 최단 거리가 된다.

6-4. 어떤 경우에도 마지막에 도달할 수 없다면 6-2에 의해 알아서 큐가 비워지므로 while문 내의 탈출 조건문이 아닌 디폴트 return에 의해 값을 반환하게 된다.

 

---

2022-08-15 새로운 풀이 추가 

y, x와 m, n으로 완전히 고정시켜서 문제 풀이.

x, y는 헷갈릴 여지가 너무 많다.

 

Node 클래스를 생성하지 않고 배열로 y, x 좌표를 다룸.

visited[][]도 boolean으로 하는 것이 아닌 int 배열을 이용하여 memoization을 좌표에 바로 이용.

import java.util.*;

class Solution {
    int[][] maps, visited;
    int m, n;
    int[] dy = {0,0,1,-1};
    int[] dx = {1,-1,0,0};
    
    void bfs() {
        visited[0][0] = 1;
        var queue = new LinkedList<int[]>();
        queue.add(new int[]{0,0});
        
        while (!queue.isEmpty()) {
            var curr = queue.remove();
            var y = curr[0];
            var x = curr[1];
            
            for (var i = 0; i < 4; i++) {
                var ny = y + dy[i];
                var nx = x + dx[i];
                
                if (ny >= m || ny < 0 || nx >= n || nx < 0) continue;
                if (visited[ny][nx] == 0 && maps[ny][nx] == 1) {
                    visited[ny][nx] = visited[y][x] + 1;
                    queue.add(new int[]{ny, nx});
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
        m = maps.length;
        n = maps[0].length;
        visited = new int[m][n];
        this.maps = maps;
        
        bfs();
        answer = visited[m - 1][n - 1] == 0 ? - 1 : visited[m - 1][n - 1];
        return answer;
    }
}

---

이전 풀이

import java.util.*;

class Solution {
    int[][] maps;
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,-1,1};
    boolean[][] visited;
    int n, m;
    
    public int solution(int[][] maps) {
        this.maps = maps;
        
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
        return bfs(0, 0);
    }
    int bfs(int x, int y) {
        visited[x][y] = true;
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 1));
        
        while (!q.isEmpty()) {
            Node node = q.poll();
            
            if (node.x == n - 1 && node.y == m - 1) return node.depth;
            
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (visited[nx][ny] || maps[nx][ny] != 1) continue;
                
                visited[nx][ny] = true;
                q.offer(new Node(nx, ny, node.depth + 1));
            }
        }
        return -1;
    }
    
    class Node {
        int x;
        int y;
        int depth;
        
        Node (int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
}

 

DFS로 푼다면 아래와 같이 작성된다. 하지만 DFS는 해당 문제에서 TLE 발생

BFS와 다른 점은 BFS는 BFS 메서드가 한번만 불리기 때문에 특정값을 리턴할 수 있지만

DFS에서는 콜스택을 이용하므로 정답 컨트롤을 전역 변수로 해주어야 한다.

 

import java.util.*;

class Solution {
    int[][] maps;
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,-1,1};
    boolean[][] visited;
    int n, m;
    //DFS에서 값을 관리하기 위해 추가.
    int min;
    
    public int solution(int[][] maps) {
        this.maps = maps;
        
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
        
        //최소값을 구해야하므로 최대값으로 기본값 설정.
        min = Integer.MAX_VALUE;
        //콜스택을 통해 자기 자신을 호출하므로 depth에 대한 관리도 dfs 메서드가 한다.
        dfs(0, 0, 1);
        if (min == Integer.MAX_VALUE) return -1;
        return min;
    }
    void dfs(int x, int y, int depth){
        if(x == n - 1 && y == m - 1){
        	//최소값 비교.
            min = Math.min(depth, min);
            return;
        }
        for(int i = 0; i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(visited[nx][ny] || maps[nx][ny] != 1) continue;
            
            //dfs를 돌기 전 방문 처리 후 돌고 나와서 미방문 처리.
            visited[nx][ny] = true;
            dfs(nx, ny, depth + 1);
            visited[nx][ny] = false;
        }
    }
}

 

DFS에서의 방문 처리가 진행되는 방식은 다음과 같이 표현할 수 있다.

visited[nx][ny] = true;
dfs(nx, ny, depth + 1);
visited[nx][ny] = true;
dfs(nx, ny, depth + 1);
visited[nx][ny] = true;
dfs(nx, ny, depth + 1);

visited[nx][ny] = false;
visited[nx][ny] = false;
visited[nx][ny] = false;

 

레퍼런스

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

https://foameraserblue.tistory.com/188?category=481823 

PS를 하며 느끼는 DFS와 BFS 선택의 기준