백준 1726 (로봇) - java

https://www.acmicpc.net/problem/1726

1726번: 로봇

코드가 굉장히 길지만 사실 함수로 만들 경우 줄일 수 있다. ( 줄이는 건 기력이 보충되면 하도록 하겠습니다. )

해당 문제를 해결하는데 있어 중요한 팁을 설명하겠다.

   1. 1, 2, 3칸 이동하는 경우 중간에 벽을 만나면 다음 차례의 이동도 불가능하다.

   2. 각 방향을 기준으로 90도 회전하는 방향은 정해져 있다.

   3. 더 적은 명령어의 횟수로 도착하는 경우 갱신을 해줘야 한다. 방문 좌표계를 방향까지 고려하여 3차원으로 선언하고 int 값을 통해 값           을 갱신 할 수 있도록 한다.

import java.io.*;
import java.util.*;
/*
    동,서 쪽 기준 90도 회전 -> 북 , 남
    북,남 쪽 기준 90도 회전 -> 동 , 서
*/
public class Main {

    static int[] dx ={0,0,0,1,-1}; // 동 , 서 , 남 , 북 방향 기억 !!!!
    static int[] dy ={0,1,-1,0,0}; 
    static int[][]board = new int[101][101]; 
    static int[][][] visit = new int[101][101][5]; // x 좌표 , y 좌표 , 방향
    static Queue<point> q = new LinkedList<>();
    static int n = 0;
    static int m = 0;
    static int result = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i =1 ;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j= 1;j<=m;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine()," ");
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        point start= new point(x,y,w);
        visit[x][y][w] = 1;
        q.add(start);

        st = new StringTokenizer(br.readLine()," ");
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        point last= new point(x,y,w);
        bfs(last);

        System.out.println(result);
        br.close();
    }



    static void bfs(point last)
    {
        while(!q.isEmpty())
        {
            point cur = q.poll();

            if(cur.x==last.x&&cur.y==last.y&&cur.pos==last.pos) // 도착 좌표일 경우
            {
                if(result==-1) // 최솟값을 구하는 문제이기 때문에 갱신 방식으로 진행
                    result = visit[cur.x][cur.y][cur.pos]-1;
                else if(result>visit[cur.x][cur.y][cur.pos]-1)
                    result = visit[cur.x][cur.y][cur.pos]-1;
            }

            if(cur.pos==1) // 동쪽 방향인 경우
            {
                for(int i=1;i<=3;i++) // 앞으로 1,2,3 칸 진행
                {
                    int nx = cur.x+dx[cur.pos]*i;
                    int ny = cur.y+dy[cur.pos]*i;
                    if(nx>=1&&nx<=n&&ny>=1&&ny<=m) // 범위의 좌표값인지 확인
                    {
                        if(board[nx][ny]==1) // 벽을 만나는 경우 반복문 탈출
                            break;
                        if(visit[nx][ny][cur.pos]==0||visit[nx][ny][cur.pos]>visit[cur.x][cur.y][cur.pos]+1)
                        {
                            visit[nx][ny][cur.pos] = visit[cur.x][cur.y][cur.pos]+1;
                            q.add(new point(nx,ny,cur.pos));
                        } // 방문한 적이 없거나 더 적은 명령어의 횟수로 도착 가능한 경우
                    }
                    else{
                        break;
                    }
                }
                
                // 왼쪽 , 오른쪽 90도 회전의 경우를 계산 
                if(visit[cur.x][cur.y][3]==0||visit[cur.x][cur.y][3]>visit[cur.x][cur.y][1]+1)
                {
                    visit[cur.x][cur.y][3]=visit[cur.x][cur.y][1]+1;
                    q.add(new point(cur.x,cur.y,3));
                } 

                if(visit[cur.x][cur.y][4]==0||visit[cur.x][cur.y][4]>visit[cur.x][cur.y][1]+1)
                {
                    visit[cur.x][cur.y][4]=visit[cur.x][cur.y][1]+1;
                    q.add(new point(cur.x,cur.y,4));
                }

            }

            else if(cur.pos==2) // 서쪽 
            {
                for(int i=1;i<=3;i++)
                {
                    int nx = cur.x+dx[cur.pos]*i;
                    int ny = cur.y+dy[cur.pos]*i;

                    if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
                    {
                        if(board[nx][ny]==1)
                            break;
                        if(visit[nx][ny][cur.pos]==0)
                        {
                            visit[nx][ny][cur.pos] = visit[cur.x][cur.y][cur.pos]+1;
                            q.add(new point(nx,ny,cur.pos));
                        }

                        else if(visit[nx][ny][cur.pos]>visit[cur.x][cur.y][cur.pos]+1)
                        {
                            visit[nx][ny][cur.pos] = visit[cur.x][cur.y][cur.pos]+1;
                            q.add(new point(nx,ny,cur.pos));
                        }
                    }
                    else{
                        break;
                    }
                }

                if(visit[cur.x][cur.y][3]==0||visit[cur.x][cur.y][3]>visit[cur.x][cur.y][2]+1)
                {
                    visit[cur.x][cur.y][3]=visit[cur.x][cur.y][2]+1;
                    q.add(new point(cur.x,cur.y,3));
                }

                if(visit[cur.x][cur.y][4]==0||visit[cur.x][cur.y][4]>visit[cur.x][cur.y][2]+1)
                {
                    visit[cur.x][cur.y][4]=visit[cur.x][cur.y][2]+1;
                    q.add(new point(cur.x,cur.y,4));
                }

            }

            else if(cur.pos==3) // 남쪽
            {
                for(int i=1;i<=3;i++)
                {
                    int nx = cur.x+dx[cur.pos]*i;
                    int ny = cur.y+dy[cur.pos]*i;

                    if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
                    {
                        if(board[nx][ny]==1)
                            break;
                        if(visit[nx][ny][cur.pos]==0)
                        {
                            visit[nx][ny][cur.pos] = visit[cur.x][cur.y][cur.pos]+1;
                            q.add(new point(nx,ny,cur.pos));
                        }

                        else if(visit[nx][ny][cur.pos]>visit[cur.x][cur.y][cur.pos]+1)
                        {
                            visit[nx][ny][cur.pos] = visit[cur.x][cur.y][cur.pos]+1;
                            q.add(new point(nx,ny,cur.pos));
                        }
                    }
                    else{
                        break;
                    }
                }

                if(visit[cur.x][cur.y][1]==0||visit[cur.x][cur.y][1]>visit[cur.x][cur.y][3]+1)
                {
                    visit[cur.x][cur.y][1]=visit[cur.x][cur.y][3]+1;
                    q.add(new point(cur.x,cur.y,1));
                }

                if(visit[cur.x][cur.y][2]==0||visit[cur.x][cur.y][2]>visit[cur.x][cur.y][3]+1)
                {
                    visit[cur.x][cur.y][2]=visit[cur.x][cur.y][3]+1;
                    q.add(new point(cur.x,cur.y,2));
                }

            }
            else if(cur.pos==4) //북쪽
            {
                for(int i=1;i<=3;i++)
                {
                    int nx = cur.x+dx[cur.pos]*i;
                    int ny = cur.y+dy[cur.pos]*i;

                    if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
                    {
                        if(board[nx][ny]==1)
                            break;
                        if(visit[nx][ny][cur.pos]==0)
                        {
                            visit[nx][ny][cur.pos] = visit[cur.x][cur.y][cur.pos]+1;
                            q.add(new point(nx,ny,cur.pos));
                        }

                        else if(visit[nx][ny][cur.pos]>visit[cur.x][cur.y][cur.pos]+1)
                        {
                            visit[nx][ny][cur.pos] = visit[cur.x][cur.y][cur.pos]+1;
                            q.add(new point(nx,ny,cur.pos));
                        }
                    }
                    else{
                        break;
                    }
                }

                if(visit[cur.x][cur.y][1]==0||visit[cur.x][cur.y][1]>visit[cur.x][cur.y][4]+1)
                {
                    visit[cur.x][cur.y][1]=visit[cur.x][cur.y][4]+1;
                    q.add(new point(cur.x,cur.y,1));
                }

                if(visit[cur.x][cur.y][2]==0||visit[cur.x][cur.y][2]>visit[cur.x][cur.y][4]+1)
                {
                    visit[cur.x][cur.y][2]=visit[cur.x][cur.y][4]+1;
                    q.add(new point(cur.x,cur.y,2));
                }

            }

        }
    }
}

class point
{
    int x;
    int y;
    int pos;

    point(int x,int y,int pos)
    {
        this.x = x;
        this.y = y;
        this.pos = pos;
    }
}