자바생
Published 2021. 11. 29. 13:00
자바(백준) 1726 로봇 BOJ(Java)
728x90

오답 노트 & 새로 알게 된 점

 

처음에 로봇을 움직일 때 회전과 이동을 같이했다.

이동을 하면서 회전을 같이하면 코드가 복잡하지 않고, 문제를 해결하는데 영향을 끼치지 않을 거라 생각했다.

 

하지만 이동과 회전을 같이하게 된다면 목적지에 도착했을 때,

최소 거리라는 보장을 할 수 없다.

 

풀이

  • 1 ~ 3을 차례대로 이동하고 큐에 넣기
    • 2나 3을 이동할 때, 중간에 1이 있지만 뛰어넘을 경우를 대비하여 순차적으로 이동하면서 1을 만나면 break함.
  • 이동하지 않고 방향만 바꿔주고 큐에 넣기
    • 180도 회전할 경우에는 cnt가 2 증가하기 때문에 규칙성을 찾음
      • 180도 회전할 경우는 동, 서 와 남, 북 이므로 둘을 더했을 땐 고유하게 3과 7의 값이 나오게 됨

 


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int row, col;
    static int A[][];
    static boolean visit[][][];
    static Info start = null, end = null;
    static int dx[] = {0001-1};
    static int dy[] = {01-100};
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        bfs();
 
        System.out.println(ans);
    }
 
    static void bfs() {
        Queue<Info> q = new ArrayDeque<>();
        q.offer(start);
        visit[start.x][start.y][start.status] = true;
 
        while (!q.isEmpty()) {
            Info info = q.poll();
 
            if (info.x == end.x && info.y == end.y && info.status == end.status) {
                ans = Math.min(ans, info.cnt);
                continue;
            }
 
            //현재 바라보는 방향으로 1, 2, 3만큼 이동
            for (int i = 1; i <= 3; i++) {
                int dX = info.x + i * dx[info.status];
                int dY = info.y + i * dy[info.status];
 
                if(!isRangeTrue(dX,dY)) continue;
                if(visit[dX][dY][info.status]) continue;
                if(A[dX][dY] == 1break;
 
                q.offer(new Info(dX, dY, info.status, info.cnt + 1));
                visit[dX][dY][info.status] = true;
            }
 
            //방향만 움직이기
            for (int i = 1; i <= 4; i++) {
                if(!visit[info.x][info.y][i] && i != info.status)
                if(i + info.status == 3 || i + info.status == 7){
                    q.offer(new Info(info.x, info.y, i, info.cnt + 2));
                    visit[info.x][info.y][i] = true;
                }
                else{
                    q.offer(new Info(info.x, info.y, i, info.cnt + 1));
                    visit[info.x][info.y][i] = true;
                }
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        row = atoi(st.nextToken());
        col = atoi(st.nextToken());
 
        A = new int[row][col];
        visit = new boolean[row][col][5];
 
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                A[i][j] = atoi(st.nextToken());
            }
        }
 
        st = new StringTokenizer(br.readLine());
        start = new Info(atoi(st.nextToken()) - 1, atoi(st.nextToken()) - 1, atoi(st.nextToken()),0);
        st = new StringTokenizer(br.readLine());
        end = new Info(atoi(st.nextToken()) - 1, atoi(st.nextToken()) - 1, atoi(st.nextToken()),0);
    }
 
 
    static class Info{
        int x, y, status, cnt;
 
        public Info(int x, int y, int status, int cnt) {
            this.x = x;
            this.y = y;
            this.status = status;
            this.cnt = cnt;
        }
    }
}
 
cs

728x90

'BOJ(Java)' 카테고리의 다른 글

자바(백준) 17136 색종이 붙이기  (0) 2021.11.30
자바(백준) 9935 문자열 폭발  (0) 2021.11.29
자바(백준) 1941 소문난 칠공주  (0) 2021.11.27
자바(백준) 3190 뱀  (0) 2021.11.24
자바(백준) 17144 미세먼지 안녕!  (0) 2021.11.23
profile

자바생

@자바생

틀린 부분이 있다면 댓글 부탁드립니다~😀

검색 태그