백준 17837 (새로운 게임 2) - java

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

17837번: 새로운 게임 2

유형 :  구현

 

접근 : 구현 유형의 문제들은 예전에도 말했듯 메소드로 분리하여 차근차근 접근하는 것이 중요하다.

1. 1번부터 m번 말까지 순서대로 이동을 시킨다.
2. 한개의 말이 이동하고 나서 바로 바로 4개가 쌓였는지 확인한다. -> 새로운 게임 1과의 차이점

주의 사항

• 고려해야 할 점은 원래 이동 지점이 파란색인 경우이다.
  • 반대 지점이 빨간색, 회색일 경우를 분할해서 고려해야 한다 !!!!!!

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int[][] board;
    static Node[] where;
    static ArrayList<Integer>[][] map;

    static int[] dx = {0,0,0,-1,1};
    static int[] dy = {0,1,-1,0,0};

    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());

        board = new int[n+1][n+1];
        map = new ArrayList[n+1][n+1];
        where = new Node[m+1];

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

        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int x= Integer.parseInt(st.nextToken());
            int y= Integer.parseInt(st.nextToken());
            int d= Integer.parseInt(st.nextToken());

            where[i] = new Node(x,y,d);
            map[x][y].add(i);
        }

        int result = -1;
        for(int i=1;i<=1000;i++)
        {
            boolean tmp = turn(); // 4개가 쌓였는지 확인 !

            if(!tmp){
                result = i; // 쌓였다면 해당 초를 반환
                break;
            }
        }

        System.out.println(result);
        br.close();
    }
    static boolean turn(){

        for(int i=1;i<=m;i++)
        {
            boolean tmp = true;
            Node cur = where[i];

            int nx = cur.x + dx[cur.d];
            int ny = cur.y + dy[cur.d]; // 원래 이동 지점

            if(nx < 1 || nx > n || ny < 1 || ny > n)
            {
                tmp = moveB(cur.x,cur.y,i); // 밖으로 벗어나는 경우 - 파란색 지점 이동과 동일
            }

            else if(board[nx][ny] == 0)
            {
               tmp =  moveW(cur.x,cur.y,nx,ny,i); // 회색 지점 이동
            }

            else if(board[nx][ny] == 1){
               tmp =  moveR(cur.x,cur.y,nx,ny,i); // 빨간색 지점 이동
            } 

            else if(board[nx][ny] == 2){
               tmp =  moveB(cur.x,cur.y,i); // 파란색 
            }

            if(!tmp)
                return false; // 한개의 말이 이동했을때마다 종료 조건 check!
        }

        return true;
    }
    // 방향 전환 메소드
    static int changeD(int d)
    {
        if(d == 1)
            return 2;
        if(d == 2)
            return 1;
        if(d == 4)
            return 3;

        return 4;
    }

    static boolean moveR(int x,int y,int nx,int ny,int num)
    {
        ArrayList<Integer> tmp = new ArrayList<>(); // 원래 지점을 초기화 하기 위해 사용
        Stack<Integer> q = new Stack<>(); // 빨간색의 경우 순서가 뒤집힌다 - 스택 이용

        boolean start = false;
        for(int i=0;i<map[x][y].size();i++)
        {
            int cur = map[x][y].get(i);

            if(cur == num)
            {
                start = true; // 해당 지점에서 말의 위치를 찾는다.
            }

            if(start)
            {
                q.add(cur); // 스택에 추가
                where[cur] = new Node(nx,ny,where[cur].d); // 위치 변경
            }

            else{
                tmp.add(cur); 
            }
        }

        while(!q.isEmpty())
        {
            map[nx][ny].add(q.pop());
        }

        map[x][y] = tmp;

        if(map[nx][ny].size() >= 4)
            return false;

        return true;
    }

    static boolean moveW(int x,int y,int nx,int ny,int num)
    {
        ArrayList<Integer> tmp = new ArrayList<>();
        boolean start = false;
        for(int i=0;i<map[x][y].size();i++)
        {
            int cur = map[x][y].get(i);

            if(cur == num)
            {
                start = true;
            }

            if(start)
            {
                map[nx][ny].add(cur);
                where[cur] = new Node(nx,ny,where[cur].d);
            }

            else{
                tmp.add(cur);
            }
        }

        map[x][y] = tmp;

        if(map[nx][ny].size() >= 4)
            return false;

        return true;
    }
    // 파란색 ! 
    static boolean moveB(int x,int y,int num){
        int cd = changeD(where[num].d);
        int n2x = x + dx[cd];
        int n2y = y + dy[cd];
        /* 반대 지점도 벗어나거나 파란색인 경우 - num번째 말의 방향만 바꾸기 */
        if(n2x < 1 || n2x > n || n2y < 1 || n2y > n)
        {
            where[num] = new Node(where[num].x,where[num].y,cd);
        }

        else if(board[n2x][n2y] == 2)
        {
            where[num] = new Node(where[num].x,where[num].y,cd);
        }

        else{
            where[num] = new Node(where[num].x,where[num].y,cd);

            if(board[n2x][n2y] == 0)
            {
                boolean tmp = moveW(x,y,n2x,n2y,num);
                return tmp;
            }

            else if(board[n2x][n2y] == 1)
            {
                boolean tmp = moveR(x,y,n2x,n2y,num);
                return tmp;
            }
        }

        return true;
    }
}
class Node
{
    int x;
    int y;
    int d; // 방향

    Node(int x,int y,int d)
    {
        this.x = x;
        this.y = y;
        this.d = d;
    }
}