자바(백준) 1726 로봇

오답 노트 & 새로 알게 된 점

 

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

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

 

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

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

 

풀이

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

 

---

코드

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[] = {0, 0, 0, 1, -1};
    static int dy[] = {0, 1, -1, 0, 0};
    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] == 1) break;
 
                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;
        }
    }
}