[프로그래머스/JAVA] Level 2, 게임 맵 최단거리

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

프로그래머스

 

[문제 요약 설명]
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의
최솟값을 return 하도록 solution 함수를 완성해 주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

* 해당 문제에서 체크해야할 조건
1) 벽(0)이 아닌 길(1)인가?
2) 다음 이동할 위치가 맵의 외곽인가?
3) 지나왔던 길인가?
- [최솟값을 구하는 문제이기 때문에, 이미 지난 길을 다시 방문할 필요가 없다.]

---

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

 

입출력 예

---

1. 첫번 째 풀이

효율성 테스트에서 실패

문제를 해결하기 위해 탐색을 진행합니다. 여기서 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘을 고민할 수 있습니다. 두 알고리즘 모두 해를 구할 수는 있습니다. 단, DFS는 불필요한 길까지 탐색하기 때문에 긴 시간이 발생합니다. 따라서 해당 문제에서는 BFS 알고리즘으로 접근합니다. BFS 경우에는 존재하는 길을 모두 탐색하는데요, 아무 길 중 목적지에 도달한다면, 더 이상 탐색을 하지 않아도 됩니다. 즉, 가장 처음 발견하는 해가 최솟값이 됩니다.

BFS 탐색 과정

BFS 알고리즘은 Queue 자료구조를 활용합니다. 그리고 우리는 '(1) 다음 길을 지나갈 수 있는지, (2) 목적지에 도달했는지'를 체크합니다. 저는 이 문제를 풀면서, 여러 갈림길이 발생하는 구간 때문에 어려움을 느꼈습니다. (위 그림에서 7번 다음, 8번 길에 해당하는 부분입니다.) 한 개의 Queue로 두 길을 동시에 밟는 것을 구현하지 못했습니다. 그래서 두 개의 큐를 생성했는데요. 각각에 다음 지나갈 길과 현재 지나가는 길을 저장했습니다. 아래 코드를 보고, 이어서 설명하겠습니다.

(1) BFS 선언 메서드 (2) BFS 구현 메서드

방법은 이렇습니다.
1) 캐릭터 움직임 좌표 배열을 순회하면서, 현재 위치에 더합니다. (움직였다고 가정) 다음 위치가 갈 수 있는 길인지 체크한 후, Next Queue 에 저장합니다.
2) Next Queue 에서 Current Queue로 옮길 때 count를 추가합니다. (위 코드에선 변수명 answer)
3) 다음 길이 없어질 때까지 탐색을 진행합니다. 중간에 목적지에 도달하면, 그 즉시 메서드를 종료합니다. 이때 목적지를 찾았기 때문에 true를 반환합니다. 만약 찾지 못했다면, false를 반환합니다.
4) 최종적으로 find가 true면, 카운트한 answer를 반환하고, false면 -1을 반환합니다.

첫 번째 풀이 결과

일반 테스트 결과는 모두 통과했지만, 효율성 테스트는 시간초과가 발생했습니다. 아마 while 문을 두 번 사용하면서 발생한 것 같습니다.

---

2. 두번 째 풀이

반복문을 한번만 사용해서 해를 구할 방법

maps와 동일한 크기로, int 타입에 이차원 배열을 만듭니다. 이렇게 만든 배열에는 지나갈 때 count를 기록할 것입니다.
예를 들면, 시작하는 칸은 무조건 1입니다. 다음 지나갈 길에 해당하는 칸에는 현재 count+1을 하여 저장합니다. 따라서 2가 됩니다. 이와 같이 진행하면 첫 번째 풀이에서 진행한 것과 같이 두 개의 Queue를 생성하지 않아도, 갈림길에서 동시에 count를 측정할 수 있습니다.
그리고 현재 길(1)을 지났다면, 더 이상 다시 지나갈 필요가 없기 때문에 maps 배열에서 0으로 변경합니다.

이 방법을 처음 알게되었는데, 굳이 boolean 배열을 생성해서 방문 여부를 체크할 필요가 없었네요. 👍

import java.util.*;

public class Main {
	private class Position {
        int x,y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public int solution(int[][] maps) {

        int answer = 0;
        int[][] move = {{0,1}, {0,-1},{1,0},{-1,0}};

        Queue<Position> que = new LinkedList<>();
        int[][] count = new int[maps.length][maps[0].length];

        que.add(new Position(0,0));
        count[0][0]=1;

        while (!que.isEmpty()) {
            Position curr = que.poll();
            int curCnt = count[curr.y][curr.x];

            for(int i = 0; i < 4; i++) {
                Position p = new Position(curr.x + move[i][0], curr.y + move[i][1]);

                if(isOutside(maps, p)) continue;
                if(isWall(maps, p)) continue;
                count[p.y][p.x] = curCnt+1;
                maps[p.y][p.x] = 0;
                que.add(p);
            }
        }
        answer=count[maps.length-1][maps[0].length-1];
        if(answer==0) return -1;
        else return answer;
    }
    
        private static boolean isOutside(int[][] maps, Position p) {
        return p.x < 0 || p.y < 0 || p.x == maps[0].length || p.y == maps.length;
    }

    private static boolean isWall(int[][] maps, Position p) {
        return maps[p.y][p.x] == 0;
    }
}