[백준/JAVA] 1726번: 로봇

📖 문제

1726번: 로봇

 

 

 

💡  풀이 방식

• BFS

필요 자료구조
- 로봇 객체  (행, 열, 방향, 명령 횟수)
- 3차원 boolean형 방문 표시 배열 : [행][열][방향] ⭐
- dx/dy 배열 동서남북 배열

 

 

1. 격자를 입력받는다.

2. 시작점 위치,방향과 도착점 위치,방향을 입력받는다.

String[] s1 = br.readLine().split(" ");
start = new Robot(Integer.parseInt(s1[0]) -1, Integer.parseInt(s1[1]) -1, Integer.parseInt(s1[2]) -1, 0);
	    
String[] s2 = br.readLine().split(" ");
end = new Robot(Integer.parseInt(s2[0]) -1, Integer.parseInt(s2[1]) -1, Integer.parseInt(s2[2]) -1, 0);

 

 

3. 시작점부터 도착점에 도착하기 전까지 BFS를 수행한다.

 - 현재 지점이 도착지라면, 현재까지의 명령 횟수를 출력하고 종료한다.

if(now.r == end.r && now.c == end.c && now.d == end.d) {
    return now.cnt;
}

 

 3-1) 명령1. Go k: 도착지가 아니라면, 현재 바라보는 방향으로 1~3칸 이동한다. (벽이라면 바로 종료)

// 명령1. Go K : 현재 바라보는 방향으로 1,2,3만큼 이동
for(int i = 1 ; i <= 3 ; i++) {
    int nr = now.r + dr[now.d]*i;
    int nc = now.c + dc[now.d]*i;

    if(nr < 0 || nr >= M || nc < 0 || nc >= N)  continue;

    // 중간에 벽이 있으면 아예 끝
    if(map[nr][nc] == 1) break;
    if(!visited[nr][nc][now.d]) {
        visited[nr][nc][now.d] = true;
        q.add(new Robot(nr, nc, now.d, now.cnt +1));
    }
}

 

 

 3-2) 명령2. Turn dir: 현재 방향을 전환한다.

int left = 0;   // 왼쪽   90도 회전: 동0 > 북3> 서1> 남2
int right = 0;  // 오른쪽 90도 회전: 동0 > 남2 > 서1> 북3

switch(now.d) {
    case 0: left = 3; right = 2; break;
    case 1: left = 2; right = 3; break;
    case 2: left = 0; right = 1; break;
    case 3: left = 1; right = 0; break;
}

if(!visited[now.r][now.c][left]) {
    visited[now.r][now.c][left] = true;
    q.add(new Robot(now.r, now.c, left, now.cnt +1));
}

if(!visited[now.r][now.c][right]) {
    visited[now.r][now.c][right] = true;
    q.add(new Robot(now.r, now.c, right, now.cnt +1));
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dr = {0,0,1,-1};   // 동서남북
    static int[] dc = {1,-1,0,0};
    
    static int M,N;
    static int[][] map;
    static boolean[][][] visited;
    
    static Robot start, end;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        
        map = new int[M][N];
        visited = new boolean[M][N][4];
        
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        String[] s1 = br.readLine().split(" ");
        start = new Robot(Integer.parseInt(s1[0]) -1, Integer.parseInt(s1[1]) -1, Integer.parseInt(s1[2]) -1, 0);
        
        String[] s2 = br.readLine().split(" ");
        end = new Robot(Integer.parseInt(s2[0]) -1, Integer.parseInt(s2[1]) -1, Integer.parseInt(s2[2]) -1, 0);
        
        System.out.println(bfs());
    }
    
    private static int bfs() {
        Queue<Robot> q = new ArrayDeque<>();
        q.add(start);
        visited[start.r][start.c][start.d] = true;
        
        while(!q.isEmpty()) {
            Robot now = q.poll();
            
            // 도착지인지 확인
            if(now.r == end.r && now.c == end.c && now.d == end.d) {
                return now.cnt;
            }
            
            // 명령1. Go K : 현재 바라보는 방향으로 1,2,3만큼 이동
            for(int i = 1 ; i <= 3 ; i++) {
                int nr = now.r + dr[now.d]*i;
                int nc = now.c + dc[now.d]*i;
                
                if(nr < 0 || nr >= M || nc < 0 || nc >= N)  continue;
                
                // 중간에 벽이 있으면 아예 끝
                if(map[nr][nc] == 1) break;
 
                if(!visited[nr][nc][now.d]) {
                    visited[nr][nc][now.d] = true;
                    q.add(new Robot(nr, nc, now.d, now.cnt +1));
                }
            }
 
            // 명령2. Turn dir
            int left = 0;   // 왼쪽   90도 회전: 동0 > 북3> 서1> 남2
            int right = 0;  // 오른쪽 90도 회전: 동0 > 남2 > 서1> 북3
            
            switch(now.d) {
                case 0: left = 3; right = 2; break;
                case 1: left = 2; right = 3; break;
                case 2: left = 0; right = 1; break;
                case 3: left = 1; right = 0; break;
            }
            
            if(!visited[now.r][now.c][left]) {
                visited[now.r][now.c][left] = true;
                q.add(new Robot(now.r, now.c, left, now.cnt +1));
            }
            
            if(!visited[now.r][now.c][right]) {
                visited[now.r][now.c][right] = true;
                q.add(new Robot(now.r, now.c, right, now.cnt +1));
            }
        }
        
        return -1;
    }
}
 
class Robot {
    int r,c,d,cnt;
    
    public Robot(int r, int c, int d, int cnt) {
        this.r = r;
        this.c = c;
        this.d = d;
        this.cnt = cnt;
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

비트마스킹으로 방문 처리...

[알고리즘 문제풀이] 백준 1726 로봇 (JAVA코드)

 

---

💦 어려웠던 점

- 방향 전환을 어떻게 하지..?의 문제

- 저 명령1 Go K를 제대로 이해하지 못 했다.

 

 

🧐 새로 알게 된 내용

- 이동과 회전을 같이 하면, 목적지 도착 시 최소 거리라는 보장을 할 수 없다고 한다. (참고)

- 3차원 방문 배열 사용해서 해당 방향에서의 최소 거리를 한 방에 구하는 것,,,

- 이 문제 복습 진짜 자주 해야겄다,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 1726 로봇 - JAVA

[Algorithm] 백준_1726 로봇 JAVA

#백준_1726 로봇 - Java 자바