[JAVA][프로그래머스] 리코쳇 로봇

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

프로그래머스

---

풀이 과정

사실 문제를 딱 봤을때 이 문제는 바로 bfs로 풀면 된다는 것을 알아서 블로그에 글을 안올릴려고 했다.

그런데 막상 풀어보니 나에겐 좀 많이 까다로웠던 문제..

일반적인 bfs문제만 풀다가 변형이 필요한 bfs가 나오니깐 잘 못하겠다...

그만큼 문제를 많이 안 풀어봤다는 뜻이지만..

 

앞으로 더 열심히 해야지

 

어쨌든 풀이 과정을 보면

해당 문제는 가중치가 모두 같은 최단 거리 구하는 문제이다.

최단 거리를 구하는 문제는 dfs보다 bfs가 훨씬 효율적이다.

왜냐하면 해당 문제는 모든 방향을 봐야하는데 dfs는 한방향을 쭉 돌고나서 그 다음 다른 방향을 보기 때문에

모든 가능한 경로를 탐색하게 된다.

하지만 우리가 원하는건 최단거리이기 때문에 최단 거리를 보장하지 않는 dfs는 비효율적이다.

최단거리가 나오면 bfs와 다익스트라 알고리즘을 고민해보면 되는데 보통 가중치가 있다면 다익스트라, 없다면 bfs를 사용하면 된다.

 

 

그래서 bfs로 문제풀이를 하다가

아래와 같은 코드가 나왔는데 다음으로 진행하는 조건을 설정하는 부분에서 생각이 막혔다

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

public class PG_169199 {
    private static int[] dr = {-1, 1, 0, 0};
    private static int[] dc = {0, 0, -1, 1};
    private static int N, M;
    private static char[][] field;
    private static boolean[][] visited;

    public int solution(String[] board) {
        int answer = 0;
        field = new char[board.length][board[0].length()];
        for (int i = 0; i < board.length; i++) {
            field[i] = board[i].toCharArray();
        }

        N = field.length;
        M = field[0].length;
        visited = new boolean[N][M];

        // 시작점 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (field[i][j] == 'R') {
                    return bfs(i, j);
                }
            }
        }
        return answer;
    }

    private int bfs(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c, 0});
        visited[r][c] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            if (field[cur[0]][cur[1]] == 'G') {
                return cur[2];
            }

            for (int i = 0; i < 4; i++) {
                
                int nr = cur[0] + dr[i];
                int nc = cur[1] + dc[i];

                while (isValid(nr, nc) && field[nr][nc] == '.') {

                    nr += dr[i];
                    nc += dc[i];
                }

            }
        }

        return -1;
    }

    private boolean isValid(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }

}

 

while문 다음에 벽에 막힌다면 그 자리에서 다른 방향으로 진행을 해야되는데

방문하지 않은 부분을 넣어야한다.

그런데 nr, nc가 이미 바뀐 상태라서 nr nc를 방문체크하는 것은 의미가 없고 그 이전 좌표를 봐야하는데

 

한번 뒤로 가는 코드를 추가할까 하다가

일단 이전 위치가 어디였는지 기록하는 코드를 넣었다.

(지금보니 그냥 한번 뒤로 가는게 효율적이었을 것 같다.,,..)

그 다음 벽에 닿으면 while문이 종료되는데 그때
이전 위치에서 방향을 탐색해서 다른 경로로 가야하므로 q에 넣어주기

prev가 이미 방문한 곳이면 그냥 패스하고 방문하지 않은 곳이었을 경우 q에 넣었다.

 

 

채점 결과는 실패~~!!

어디가 틀렸을까 봤는데 사진에서는 while문 조건에 보면 'D'라고 되어있지만 이건 제출 코드를 캡처한 부분이고

맨 처음올린 코드를 보면 == '.'으로 되어있다.

예시를 보면 일직선으로 갈때 중간에 도착지점을 만나도 그냥 일직선으로 지나가야되는데 지나가질 못했던 것.

그래서 첫번째 테스트케이스의 결과가 -1이 나오고 있었다.

그래서 !='D'로 바꾸어 벽일때만 멈추는 로직으로 바꾸고 나서 해결!

 

---

풀이 코드

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

public class PG_169199 {
    private static int[] dr = {-1, 1, 0, 0};
    private static int[] dc = {0, 0, -1, 1};
    private static int N, M;
    private static char[][] field;
    private static boolean[][] visited;

    public int solution(String[] board) {
        int answer = 0;
        field = new char[board.length][board[0].length()];
        for (int i = 0; i < board.length; i++) {
            field[i] = board[i].toCharArray();
        }

        N = field.length;
        M = field[0].length;
        visited = new boolean[N][M];

        // 시작점 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (field[i][j] == 'R') {
                    return bfs(i, j);
                }
            }
        }
        return answer;
    }

    private int bfs(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c, 0});
        visited[r][c] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            if (field[cur[0]][cur[1]] == 'G') {
                return cur[2];
            }

            for (int i = 0; i < 4; i++) {
                int prevR = cur[0];
                int prevC = cur[1];
                int nr = cur[0] + dr[i];
                int nc = cur[1] + dc[i];

                while (isValid(nr, nc) && field[nr][nc] != 'D') {
                    prevR = nr;
                    prevC = nc;
                    nr += dr[i];
                    nc += dc[i];
                }

                if (!visited[prevR][prevC]) {
                    visited[prevR][prevC] = true;
                    q.add(new int[]{prevR, prevC, cur[2] + 1});
                }
            }
        }

        return -1;
    }

    private boolean isValid(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }

}

 

---

테스트케이스에서 틀리는 경우에는 바로바로 문제점을 찾을 수 있는데...

테스트케이스는 통과했는데 틀렸을 경우 좀 난감하다.

백준이 예제가 별로 없다보니 그런 경우가 좀 많은데 테스트케이스를 생각해 내는 방법을 연습하고 싶다면 백준을 푸는게 좀 더 좋고, 문제풀이나 구현에 좀 더 초점을 맞추고 싶다면 프로그래머스가 좀 더 좋은 것 같다.

 

그리고 같이 공부하는 친구들이 코테에서 import 어떻게 하는지 종종 물어보는데

import파일을 전부 외워서 하지 않고 그냥

코테 시작하자마자 일단 

import java.util.*;을 쓰고 시작한다.

 

나는 시간 형태로 바꾸어 나오는 문제도 있을 수 있을 것 같다고 생각해서 

import java.time.*;까지는 외웠다.

 

그런데 자바 공식 문서 정도는 참고할 수 있는 코테도 있어서...

저 두 줄은 일단 외우고 다른건 그때그때 상황에 따라서 쓰는 것 같다.

(그리고 많이 풀다보면 자동완성도 다 외우게 되는 것 같다.)

 

개인적으로 이런 조건을 생각해서 변형해야되는 문제를 좋아해서

좋은 문제였던 것 같다.

막 엄청 노가다스럽게 bfs를 했다가 dfs했다가 전체를 또 돌아야했다가
이런 쉬운 방법들이 열거 되는 형태이면 별로지만 이 문제는 bfs만 하면 되고, 또 그 방법을 그대로 사용하는게 아니라 고민해서 변형하는 문제였기 때문에 귀찮지도 않고 재미있었다.