Pccp 준비하기 - 3 bfs 방식 익히기

코딩테스트 출제율 99%에 달하는 bfs/dfs 문제를 연습하기 위해
프로그래머스의 리코쳇 로봇 문제를 풀었습니다

문제 설명

1. 이 로봇은 상 하 좌 우로 움직일 수 있습니다
2. R에서 시작하며 D는 장애물이고 G가 도달위치 입니다
3. 장애물이나 벽을 만나야만 움직임을 멈춥니다 -> 즉 한번 갈때 끝에서 다른 끝까지 갈 수도 있음
4. 최소한으로 움직여서 R에서 G로 가면 됩니다, 못가면 -1을 출력하면 됩니다

bfs풀이

bfs를 하기 위해서는 시작위치, 목표위치, 전체사각형, 방문했는가 를 확인할 수 있는 각각의 변수들이 필요합니다

여기서는 이차원 boolean배열 visited를 사용해서 방문을 확인했습니다
Moving이라는 class를 만들어서 y,x그리고 몇걸음 즉 깊이인 depth를 저장할 수 있게 했습니다

구현 코드

import java.util.*;

class Solution {
	private final int[] dx = {-1,1,0,0};
    private final int[] dy = {0,0,-1,1};
    
    private final char ROBOT = 'R', DISABLE = 'D', GOAL = 'G';
    
    private int n,m;
    
    private class Moving {
    	int y,x,depth;
        
        public Moving(int y, int x, int depth) {
        	this.y = y;
            this.x = x;
            this.depth = depth;
        }
    }
    
    public int solution(String[] board) {
    	int answer = 0;
        n = board.length;
        m = board[0].length();
        
        Moving robot = null;
        Moving goal = null;
        
        for (int i=0; i<n; i++) {
        	for(int j=0; j<m; j++) {
            	char ch = board[i].charAt(j);
                
                if (ch == ROBOT) {
                	robot = new Moving(i,j,0);
                } else if (ch == GOAL) {
                	goal = new Moving(i,j,0);
                }
            }
        }
        answer = bfs(board, robot, goal);
        
        return answer;
    }
    private int bfs(MString[] baord, Moving robot, Moving goal) {
    	Queue<Moving> qu = new LinkedList<>();
        qu.add(robot);
        boolean [][] visited = new boolean[n][m];
        visited[robot.y][robot.x] = true;
        
        while(!qu.isEmpty()) {
        	Moving cn = qu.poll();
            
            if (cn.y == goal.y && cn.x == goal.x) {
            	return cn.depth;
            }
            
            for (int i = 0; i < 4; i++) {
            	int ny = dy[i] + cn.y;
                int nx = dx[i] + cn.x;
                
                while (inRange(ny,nx) && board[ny].charAt(nx) != DISABLE) {
                	ny += dy[i];
                    nx += dx[i];
                }
                ny -= dy[i];
                nx -= dx[i];
                
                if (visited[ny][nx] || (cn.y == ny && cn.x == nx)) continue;
                
                visited[ny][nx] = true;
                qu.add(new Moving(ny,nx, cn.depth + 1);
            }
        }
        
    }
	private boolean inRange(int y, int x) {
    	return 0 <= y && y < n && 0 <= x && x < m;
    }
}