[프로그래머스][JAVA][Lv. 2] 게임 맵 최단거리

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.HashSet;

class Solution {
    HashSet<Integer> openSet = new HashSet<>();
    HashSet<Integer> closedSet = new HashSet<>();
    HashSet<Integer> newOpenSet;
    
    public int solution(int[][] maps) {
        openSet.add(0);  // 출발지
        return doBfs(maps, 1);
    }
    
    public int doBfs(int[][] maps, int answer) {
        newOpenSet = new HashSet<>();
        int count = 0;
        
        for (Integer openPos : openSet) {
            int x = openPos / 1000;
            int y = openPos % 1000;
            
            // 목적지 도착
            if (x == maps[0].length - 1 && y == maps.length - 1) {
                return answer;
            }
            
            if (y + 1 < maps.length) {  // 상
                if (!closedSet.contains(x * 1000 + (y + 1)) && maps[y + 1][x] != 0) {
                    newOpenSet.add(x * 1000 + (y + 1));
                    count++;
                }
            }
            if (y - 1 >= 0) {  // 하
                if (!closedSet.contains(x * 1000 + (y - 1)) && maps[y - 1][x] != 0) {
                    newOpenSet.add(x * 1000 + (y - 1));
                    count++;
                }
            }
            if (x - 1 >= 0) {  // 좌
                if (!closedSet.contains((x - 1) * 1000 + y) && maps[y][x - 1] != 0) {
                    newOpenSet.add((x - 1) * 1000 + y);
                    count++;
                }
            }
            if (x + 1 < maps[0].length) {  // 우
                if (!closedSet.contains((x + 1) * 1000 + y) && maps[y][x + 1] != 0) {
                    newOpenSet.add((x + 1) * 1000 + y);
                    count++;
                }
            }
            closedSet.add(openPos);
        }
        openSet = newOpenSet;
        if (count == 0) return -1;
        else return doBfs(maps, answer + 1);
    }
}

---

후기

길찾기의 정석같은 문제이다. 단지 BFS, DFS 구현만 하면 되므로 난이도 자체는 그렇게 어렵지 않다. 대부분 비슷한 방법으로 풀겠지만 아마 좌표를 어떻게 처리할 것인지에서 세세한 풀이가 갈릴 것 같다. 나는 x좌표와 y좌표를 하나의 숫자로 저장하기 위해 x축에다 최대 값이 100보다 한자리 수 더 많은 1000을 곱해서 여기에 y를 더하는 식으로 풀었다. 예를 들어서 표현할 수 있는 최대 좌표는 (100, 100)인데 나는 이걸 100 * 1000 + 100을 계산해서 100100을 만든 것이다. 문자열로 x + y를 한 것과 비슷하다. 이렇게 풀면 어느정도 쉽게 풀 수 있다.