[java, BFS(깊이우선탐색)]프로그래머스 - 리코쳇 로봇

📖 풀이한 문제

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

프로그래머스

 

---

💡 문제에서 사용된 알고리즘

너비 우선 탐색(BFS, breadth-first search)
그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

기능	특징	시간 복잡도(노드 수: V, 에지 수: E)
그래프 완전 탐색	- FIFO 탐색 - Queue 자료구조 이용	O(V + E)

너비 우선 탐색의 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기

---

📜 코드

import java.util.*;

public class 리코쳇로봇 {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char [][] map;
    static int h;
    static int w;

    public int solution(String[] board) {
        // 게임판의 높이와 너비
        h = board.length;
        w = board[0].length();

        // 방문 확인
        boolean [][] visited = new boolean[h][w];

        // BFS를 사용하기 위한 말이 이동할 위치를 넣을 Queue
        Queue<Move> que = new LinkedList<>();

        // 게임판 초기화
        map = new char[h][w];
        // map에 게임판의 상태를 넣어주면서 시작 위치를 찾는다면 que에 넣어준다.
        for (int i = 0; i < h; i++) {
            map[i] = board[i].toCharArray();
            if (board[i].contains("R")) {
                que.add(new Move(i, board[i].indexOf("R"), 0));
                visited[i][board[i].indexOf("R")] = true;
            }
        }

        // BFS
        // 현재 위치부터 네방향으로 이동해준다.
        // 메서드 stop을 사용하여 장애물이나 맨 끝에 부딪힐 때까지의 위치를 구해준다.
        // stop으로 멈춘 위치(next)가 G 목표지점이면 이동 횟수를 출력해준다.(BFS이므로 최소를 구할 수 있음)
        // 멈춘 위치(next)가 G가 아니고 방문을 안했다면 que에 넣어준다.
        while (!que.isEmpty()) {
            Move now = que.poll();
            for (int i = 0; i < 4; i++) {
                Move next = stop(now, i);
                if(map[next.x][next.y] == 'G') return next.cnt;
                else if (!visited[next.x][next.y]) {
                    que.add(next);
                    visited[next.x][next.y] = true;
                }
            }
        }

        // 목표지점을 찾지 못했다면 -1 출력
        return -1;
    }

    private static Move stop(Move move, int direc) {
        int nx = move.x;
        int ny = move.y;

        while (true) {

            nx += dx[direc];
            ny += dy[direc];

            if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
                if(map[nx][ny] == 'D') break;
            } else break;
        }

        return new Move(nx - dx[direc], ny - dy[direc], move.cnt + 1);
    }

}

// 움직이는 위치 객체
// x: x값, y: y값, cnt: 움직인 횟수
class Move {
    int x;
    int y;
    int cnt;

    public Move(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

 

---

📜 코드 설명

- 최소 이동 거리를 구하는 문제이므로 BFS를 사용하여 탐색하였다.

 

- 메소드 stop

: 현재 위치부터 한 방향으로 이동을 할 때 장애물을 만나거나 끝일 때 멈추는 위치를 찾아준다.

private static Move stop(Move move, int direc) {
        int nx = move.x;
        int ny = move.y;

        while (true) {

            nx += dx[direc];
            ny += dy[direc];

            if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
                if(map[nx][ny] == 'D') break;
            } else break;
        }

        return new Move(nx - dx[direc], ny - dy[direc], move.cnt + 1);
    }

 

- 객체 Move

:  큐에 넣어줄 말의 위치와 이동한 거리의 정보를 포함

// 움직이는 위치 객체
// x: x값, y: y값, cnt: 움직인 횟수
class Move {
    int x;
    int y;
    int cnt;

    public Move(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

 

- que에 현재 말의 위치를 넣어주었다.

 

- BFS

: BFS에서는 현재 que에서 꺼낸 Move를 4방향으로 stop을 사용하여 멈춘 위치를 구해주었고 그 위치가 목표 위치라면 움직인 거리를 출력, 그 위치가 목표 위치가 아니라고 방문하지 않은 위치라면 que에 넣어주었다.

// BFS
        // 현재 위치부터 네방향으로 이동해준다.
        // 메서드 stop을 사용하여 장애물이나 맨 끝에 부딪힐 때까지의 위치를 구해준다.
        // stop으로 멈춘 위치(next)가 G 목표지점이면 이동 횟수를 출력해준다.(BFS이므로 최소를 구할 수 있음)
        // 멈춘 위치(next)가 G가 아니고 방문을 안했다면 que에 넣어준다.
        while (!que.isEmpty()) {
            Move now = que.poll();
            for (int i = 0; i < 4; i++) {
                Move next = stop(now, i);
                if(map[next.x][next.y] == 'G') return next.cnt;
                else if (!visited[next.x][next.y]) {
                    que.add(next);
                    visited[next.x][next.y] = true;
                }
            }
        }