[프로그래머스] 리코쳇 로봇 Java 풀이

 

 

개인적으로 좋았던 문제

 

bfs+dp를 정석으로 사용할 수 있다.

알고리즘을 풀 때 map과 방향이 나오면 dir_x, dir_y는 무조건 사용해 주는게 좋다.

아래 코드에서는 n = board.length, m = board[0].length() 이런식으로 빼주면 더 깔끔해질듯

 

bfs를 활용한 탐색을 할 때 주의해야 하는 점 

1. visited 사용

2. map을 벗어나지 않게 조건 (x >= 0 && x < board.length && y >= 0 && y < board[0].length())

 

여기까지는 dp+bfs 기본이고 문제에 맞게 조건을 더 추가해주면 된다.

 

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        int res = solution(new String[]{".D.R", "....", ".G..", "...D"});
        System.out.println(res);
    }

    public static int solution(String[] board) {
        // 동서남북
        int[] dir_x = {0, 0, 1, -1};
        int[] dir_y = {1, -1, 0, 0};

        int start_x = 0;
        int start_y = 0;

        int dest_x = 0;
        int dest_y = 0;

        // make map
        int[][] map = new int[board.length][board[0].length()];
        int[][] dp = new int[board.length][board[0].length()];
        boolean[][] visited = new boolean[board.length][board[0].length()];

        for (int i = 0; i < board.length; i++) {
            String b = board[i];
            for (int j = 0; j < board[0].length(); j++) {
                char c = b.charAt(j);

                if (c == '.')
                    map[i][j] = 0;
                else if (c == 'D')
                    map[i][j] = 1;
                else if (c == 'R') {
                    map[i][j] = 2;
                    start_x = i;
                    start_y = j;
                } else if (c == 'G') {
                    map[i][j] = 3;
                    dest_x = i;
                    dest_y = j;
                }
            }
        }

        Queue<Node> q = new LinkedList<Node>();
        // 시작노드에서 갈 수 있는 방향 넣기
        for (int i = 0; i < 4; i++) {
            int x = start_x + dir_x[i];
            int y = start_y + dir_y[i];

            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length() && map[x][y] != 1) {
                q.add(new Node(i, start_x, start_y));
                visited[start_x][start_y] = true;
            }
        }

        while (!q.isEmpty()) {
            Node node = q.poll();

            int x = node.x + dir_x[node.dir];
            int y = node.y + dir_y[node.dir];

            while (x >= 0 && x < board.length && y >= 0 && y < board[0].length()) {

                // 장애물
                if (map[x][y] == 1) {
                    break;
                }
                x = x + dir_x[node.dir];
                y = y + dir_y[node.dir];
            }

            x = x - dir_x[node.dir];
            y = y - dir_y[node.dir];

            if (dp[x][y] != 0)
                dp[x][y] = Math.min(dp[x][y], dp[node.x][node.y] + 1);
            else
                dp[x][y] = dp[node.x][node.y] + 1;


            // queue에 새로운 node 등록
            boolean isvisit = false;
            for (int i = 0; i < 4; i++) {
                if(visited[x][y])
                    break;

                if (node.dir == 0 || node.dir == 1) {
                    if (i == 0 || i == 1)
                        continue;
                } else if (node.dir == 2 || node.dir == 3) {
                    if (i == 2 || i == 3)
                        continue;
                }

                int tmp_x = x + dir_x[i];
                int tmp_y = y + dir_y[i];

                if (tmp_x >= 0 && tmp_x < board.length && tmp_y >= 0 && tmp_y < board[0].length()) {
                    q.add(new Node(i, x, y));
                    isvisit = true;
                }
            }
            if(isvisit)
                visited[x][y] = true;

        }

        if (dp[dest_x][dest_y] == 0)
            return -1;

        return dp[dest_x][dest_y];
    }
}

class Node {
    int dir;
    int x;
    int y;

    Node(int dir, int x, int y) {
        this.dir = dir;
        this.x = x;
        this.y = y;
    }
}