[백준, Java] 1726번, 로봇(다익스트라)

문제 링크

1726번: 로봇

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

1. 로봇은 2가지 명령을 통해 움직일 수 있습니다.

2. 움직이는 방향은 동서남북입니다.

3. 출발 위치에서 도착 위치까지 최소 명령 횟수를 결과로 출력합니다.

4. 도착 위치에 도달했을 때 방향까지 같아야 합니다.

5. 0은 로봇이 이동할 수 있는 공간, 1은 로봇이 이동할 수 없는 공간입니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 다익스트라를 통해 시작 위치에서 도착 위치까지의 로봇 명령을 탐색합니다.

 

3. 탐색해서 얻은 최소 명령 횟수를 결과로 출력합니다.

 

 

로봇 명령 탐색

 

로봇 명령

 

1. Go k (k = { 1, 2, 3}) : 현재 방향으로 로봇이 k칸 이동한다.

 

2. Turn left or right :   left or right 방향으로 90도 회전한다. 

 

위 명령어를 다익스트라를 통해서 탐색합니다.

 

로봇이 현재 칸에서 할 수 있는 행동은 5가지입니다.

 

1, 2, 3칸 이동(3가지)

 

하지만, 중간에 벽(1)을 만나거나 현재 공간에 벗어났을 때에는 더 이상 전진할 수 없습니다.

 

또한, 중간에 방문했었던 칸이 존재하면 해당 칸에 대한 정보를  PriorityQueue에 중복하게 저장되는 것을 방지해야 합니다.

 

오른쪽, 왼쪽 회전(2가지)

 

위에 설명한 행동을 토대로 다익스트라를 진행하여 가장 먼저 방향과 도착 위치가 동일한 로봇에 명령 횟수가 결과값이 됩니다.

 

※회전을 진행할 때에 입력값은 1 : 동, 2 : 서, 3 : 남, 4 : 북으로 값이 주어지는데 저는 { 북, 동, 남, 서 }순으로 잡았기 때문에 변환을 해주어야 합니다.

 

→ { 북, 동, 남, 서 }로 잡은 이유는

 

오른쪽 회전 : (방향 + 1)  % 4

 

왼쪽 회전 :(방향 - 1) < 0 ? 3 : 방향 - 1

 

점화식 형식으로 계산되도록 사용하기 위해서입니다.

 

※예제입력 과정을 확인하시면 이해하시기 편하실 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 5

 

M : 6

 

공장

 

0	0	0	0	0	0
0	1	1	0(도착)→	1	0
0	1	0	0	0	0
0	0(시작)↓	1	1	1	0
1	0	0	0	0	0

 

 

 

 

2. 다익스트라를 통해 시작 위치에서 도착 위치까지의 로봇 명령을 탐색합니다.

 

시작 위치에서 로봇 이동 시작(횟수 : 1)

 

 

0	0	0	0	0	0
0	1	1	0(도착)	1	0
0	1	0	0	0	0
0	0(시작)↓←↑	1	1	1	0
1	0 ↓	0	0	0	0

 

다음 명령 수행(횟수 : 2)

 

0	0	0	0	0	0
0	1	1	0(도착)	1	0
0	1	0	0	0	0
0 ←	0(시작)↓←↑→	1	1	1	0
1	0 ↓ ← →	0	0	0	0

 

다음 명령 수행(횟수 : 3)

 

0	0	0	0	0	0
0	1	1	0(도착)	1	0
0	1	0	0	0	0
0 ←↑↓	0(시작) ↓←↑→	1	1	1	0
1	0 ↓←→ ↑	0 →	0 →	0 →	0

 

다음 명령 수행(횟수 : 4)

0 ↑	0	0	0	0	0
0 ↑	1	1	0(도착)	1	0
0 ↑	1	0	0	0	0
0 ←↑↓→	0(시작) ↓←↑→	1	1	1	0
1	0 ↓←→ ↑	0 → ↑↓	0 → ↑↓	0 → ↑↓	0 →

 

다음 명령 수행(횟수 : 5)

 

0 ↑ ← →	0	0	0	0	0
0 ↑ ← →	1	1	0(도착)	1	0
0 ↑ ← →	1	0	0	0	0
0 ←↑↓→	0(시작) ↓←↑→	1	1	1	0
1	0 ↓←→ ↑	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓

 

다음 명령 수행(횟수 : 6)

 

0 ↑ ← → ↓	0 →	0 →	0 →	0	0
0 ↑ ← → ↓	1	1	0(도착)	1	0 ↑
0 ↑ ← → ↓	1	0	0	0	0 ↑
0 ←↑↓→	0(시작) ↓←↑→	1	1	1	0 ↑
1	0 ↓←→ ↑	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←

 

다음 명령 수행(횟수 : 7)

 

0 ↑ ← → ↓	0 → ↑↓	0 → ↑↓	0 → ↑↓	0 →	0 → ↑
0 ↑ ← → ↓	1	1	0(도착)	1	0 ↑ ← →
0 ↑ ← → ↓	1	0	0	0	0 ↑ ← →
0 ←↑↓→	0(시작) ↓←↑→	1	1	1	0 ↑ ← →
1	0 ↓←→ ↑	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←	0 →↑↓←

 

다음 명령 수행(횟수 : 8)

 

0 ↑ ← → ↓	0 → ↑↓←	0 → ↑↓←	0 → ↑↓←	0 → ↑↓	0 → ↑ ↓ ←
0 ↑ ← → ↓	1	1	0(도착) ↓	1	0 ↑ ← → ↓
0 ↑ ← → ↓	1	0 ←	0 ↓ ←	0 ←	0 ↑ ← → ↓
0 ←↑↓→	0(시작) ↓←↑→	1	1	1	0 ↑ ← → ↓
1	0 ↓←→ ↑	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←

 

다음 명령 수행(횟수 : 9)

 

0 ↑ ← → ↓	0 → ↑↓←	0 → ↑↓←	0 → ↑↓←	0 → ↑↓ →	0 → ↑↓ ←
0 ↑ ← → ↓	1	1	0(도착) ↓ ← →	1	0 → ↑ ↓ ←
0 ↑ ← → ↓	1	0 ← ↑ ↓	0 ↓ ← → ↑	0 ← ↑ ↓	0 → ↑ ↓ ←
0 ←↑↓→	0(시작) ↓←↑→	1	1	1	0 → ↑ ↓ ←
1	0 ↓←→↑	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←	0 → ↑↓ ←

 

목적지 도착!!

 

 

3. 탐색해서 얻은 최소 명령 횟수를 결과로 출력합니다.

 

쿼리를 통해 얻은 최소 명령 횟수 : 9

 

9 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 로봇의 정보 및 공장의 정보를 띄어쓰기 기준 저장합니다.
• 시작 위치와 도착 위치에 대한 방향 정보를 setDir함수를 통해 {북, 동, 남, 서} 형식으로 바꾸었습니다.
• search함수를 통해서 최소 명령 횟수를 구합니다.
• 탐색을 통해 얻은 최소 명령 횟수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 다익스트라를 통해서 로봇이 도착 위치에 도달하는 최소 명령 횟수를 구합니다.
• setDir함수는 {동, 서, 남, 북} 형식을 {북, 동, 남, 서}형식으로 변경합니다.
• inSpace함수는 이동하려는 공간이 공장에 존재하는지 확인합니다.

결과코드

import java.io.*;
import java.util.*;


public class Main {
    //다익스트라 탐색할 때 로봇 정보
    static class Info implements Comparable<Info>{
        //r : y, c : x
        //cnt : 명령 횟수, dir : 방향
        int r, c, cnt, dir;
        Info(int r, int c, int cnt, int dir){
            this.r = r;
            this.c = c;
            this.cnt = cnt;
            this.dir = dir;
        }
        //명령 횟수 기준 오름차순 정렬
        @Override
        public int compareTo(Info o){
            return this.cnt - o.cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M];
        //공장 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] position = new int[2][3];
        //시작 위치, 도착 위치 정보 저장
        for(int i=0;i<2;i++){
            st = new StringTokenizer(br.readLine()," ");
            position[i][0] = Integer.parseInt(st.nextToken()) - 1;
            position[i][1] = Integer.parseInt(st.nextToken()) - 1;
            //{동, 서, 남, 북} -> { 북, 동, 남, 서 } 형식으로 변경
            position[i][2] = setDir(Integer.parseInt(st.nextToken()));
        }
        //다익스트라 탐색
        int result = bfs(map, position, N, M);
        //최소 명령 횟수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라를 통해서 최소 명령 횟수 탐색하는 함수
    static int bfs(int[][] map, int[][] position, int N, int M){
        PriorityQueue<Info> pq = new PriorityQueue<>();
        //북동남서 이동하는 변경 r, c의 값
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0 , 1, 0, -1};
        //방문 확인 배열
        boolean[][][] visited = new boolean[N][M][4];
        //시작 위치를 기준으로 정보 저장
        visited[position[0][0]][position[0][1]][position[0][2]] = true;
        pq.offer(new Info(position[0][0], position[0][1], 0,  position[0][2]));
        //다익스트라 진행
        while(!pq.isEmpty()){
            Info cur = pq.poll();
            //도착 위치 도달 시
            if(cur.r == position[1][0] && cur.c == position[1][1] && cur.dir == position[1][2]){
                return cur.cnt;
            }
            //현재 방향으로 1, 2, 3칸 이동
            int nr = cur.r;
            int nc = cur.c;
            for(int i=1;i<=3;i++){
                nr += dr[cur.dir];
                nc += dc[cur.dir];
                //공장에 벗어나거나, 경로가 막힐 때
                if(!inSpace(nr, nc, N, M) || map[nr][nc] == 1){
                    break;
                }
                //이미 방문한 공간일 때
                if(visited[nr][nc][cur.dir]){
                    continue;
                }
                //전진!
                visited[nr][nc][cur.dir] = true;
                pq.offer(new Info(nr, nc, cur.cnt + 1, cur.dir));
            }

            //오른쪽 회전
            int rd = (cur.dir + 1) % 4;
            if(!visited[cur.r][cur.c][rd]){
                visited[cur.r][cur.c][rd] = true;
                pq.offer(new Info(cur.r, cur.c, cur.cnt + 1, rd));
            }
            //왼쪽 회전
            int ld = (cur.dir - 1) < 0 ? 3 : cur.dir - 1;
            if(!visited[cur.r][cur.c][ld]){
                visited[cur.r][cur.c][ld] = true;
                pq.offer(new Info(cur.r, cur.c, cur.cnt + 1, ld));
            }
        }
        return 0;
    }
    //{동, 서, 남, 북} -> {북, 동, 남, 서} 변경 함수
    static int setDir(int dir){
        if(dir == 1){	//동 -> 동
            return 1;
        }else if(dir == 2){ //서 -> 동
            return 3;
        }else if(dir == 3){ // 남 -> 남
            return 2;
        }else{ //북 -> 서
            return 0;
        }
    }
    //이동하려는 칸이 공장에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c, int N, int M){
        if(r >= 0 && c >= 0 && r < N && c < M){
            return true;
        }
        return false;
    }
}