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

게임 맵이 주어지면 목적지까지 가는 최단거리를 구하는 문제로 예전에 풀었던건데 오래 되기도 했고 연습할겸 다시 풀어보았다.

 

 

맵의 값이 1이면 이동 가능하고 최단거리를 구해야 하기 때문에 DFS로 풀면 시간 초과가 뜬다. (엉뚱한 길로 가도 끝까지 파고 들어가기 때문)

4방향으로 한칸씩 이동 가능한 단위 방향 배열을 만들고 이동 가능한 경우를 Queue에 넣어가면서 목적지에 도착하면 최단 거리를 구할 수 있다.

4방향이면 뒤로도 갈 수 있기 때문에 이동 경로를 체크하는 boolean 배열을 만들어준다.

 

 

예전에 풀었던 코드

while (!q.isEmpty()) {
    int len = q.size();
    for (int i = 0; i < len; i++) {
        Pos pos = q.poll();
        if (pos.y == y_length && pos.x == x_length) {
            answer = Math.min(answer, pos.move);
        } else {
            // 이동 가능하고 체크가 안된 경우
            if (graph[pos.y][pos.x] == 1 && ch[pos.y][pos.x] == 0) {
                // 이동 체크
                ch[pos.y][pos.x] = 1;
                // 일단 4방향 전부 Queue 삽입하고 poll에서 거름
                if (pos.y < y_length) q.offer(new Pos(pos.y + 1, pos.x, pos.move + 1));
                if (pos.y > 1) q.offer(new Pos(pos.y - 1, pos.x, pos.move + 1));
                if (pos.x < x_length) q.offer(new Pos(pos.y, pos.x + 1, pos.move + 1));
                if (pos.x > 1) q.offer(new Pos(pos.y, pos.x - 1, pos.move + 1));
            }
        }
    }
}

 

다시 보고 느끼는 이전 코드 문제점

- 최단거리를 찾고 멈추지 않음

- queue의 size()만큼 for문을 돌릴 이유가 없음 (Pos에 거리 move를 저장하고 있기 때문)

- if문으로 안되는 경로 컷트하고 되는 경로만 넣으면 되는데 일단 다 넣고 있음

 

// ...
	while (!players.isEmpty()) {
            Player player = players.poll();
            if (isClear(player)) {
                return player.distance;
            }
            
            // 방향 배열 dy,dx
            for (int i = 0; i < 4; i++) {
                int my = player.y + dy[i];
                int mx = player.x + dx[i];

                if (canMove(my, mx)) {
                    moved[my][mx] = true;
                    players.offer(new Player(my, mx, player.distance + 1));
                }
            }
        }
        return -1;
    }

private boolean isClear(Player player) {
    return (player.y == maps.length - 1 && player.x == maps[0].length - 1);
}

private boolean canMove(int my, int mx) {
    if (mx < 0 || mx == maps[0].length ||
            my < 0 || my == maps.length) {
        return false;
    }
    
    if (maps[my][mx] == 0 || moved[my][mx]) {
        return false;
    }
    
    return true;
}

 

프로그래머스