[백준, JAVA]17837번, 새로운 게임 2

문제 링크

17837번: 새로운 게임 2

 

---

주의사항

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

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

---

문제 설명

---

접근 방법

BFS

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심

1. 한 번의 턴에 1~K번의 말이 차례대로 이동합니다.

2. 이동하려는 칸에 색에 따라 말의 상태를 변경해줍니다.

3. 한 칸에 말이 4개 이상있을 때까지 진행됩니다.

4. 1000턴이 넘어갈 경우 -1을 결과로 출력합니다.

5. 1000턴 이전에 한 칸에 4개 이상의 말이 존재하는 최소 턴을 결과로 출력합니다.

 

 

한 번의 턴마다 각 말들을 방향대로 이동하는 시뮬레이션이 되도록 구현하였습니다.

 

이동하려는 칸에 색에 따라 말의 상태가 변경됩니다.

 

흰색(0)

해당 칸으로 말을 이동, 이미 칸에 말이 있을 경우 해당 말 위에 순서대로 쌓인다.

 

빨간색(1)

해당 칸으로 말을 이동, 이미 칸에 말이 있는 경우 해당 말 위에 역순으로 쌓인다.

 

파란색(2) | 체스판에 벗어날 경우

해당 말 방향을 반대로 바꾸고 이동, 반대로 바꾸고 이동할 칸도 파란색이나 벗어난 경우일 때는 이동X

 

체스판에 말이 쌓일 수 있으므로 ArrayList<>형태의 배열로 만들었습니다.

 

문제에서는 예제입력 1이 진행되는 과정을 참고하시면서 제 코드를 살펴보시면 이해가 잘 될 것입니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용해서 게임에 대한 정보를 나누었습니다.
• 게임을 진행하는 gameStart를 실행하여 최소 턴을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• gameStart는 1~N까지 체스말을 이동하며 4개가 쌓이는 최소턴을 구하는 함수입니다.
• whiteMove는 말이 하얀색 칸으로 이동할 때 조건에 맞게 형태를 바꿔주는 함수입니다.
• redMove는 말이 빨간색 칸으로 이동할 때 조건에 맞게 형태를 바꿔주는 함수입니다
• directionChange는 방향을 바꾸는 함수입니다.
• inBoard는 체스판에 벗어나는지 확인하는 함수입니다.
• stackCheck는 체스말이 4개가 쌓이는지 확인하는 함수입니다.

 

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

public class Main {
    //체스판 위치 관련 클래스
    static class position{
        int x, y, direction;
        public position(int x, int y, int direction) {
            this.x = x;
            this.y = y;
            this.direction = direction;
        }
    }
    static int N,K;
    static ArrayList<Integer>[][] stack;	//체스판에 쌓여있는 체스말 저장 배열
    static position[] piece;	//체스말 위치 저장 배열
    static int[][] board;	//체스판에 대한 정보 저장 배열
    static int[] dx = {1, -1, 0, 0};	//상하좌우 x 변경값
    static int[] dy = {0, 0, -1, 1};	//상하좌우 y 변경값
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        stack = new ArrayList[N][N];
        board = new int[N][N];
        piece = new position[K];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                stack[i][j] = new ArrayList<>();
            }
        }
        //체스판 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++)
                board[i][j] = Integer.parseInt(st.nextToken());
        }
        //체스말 정보 저장
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine()," ");
            int y = Integer.parseInt(st.nextToken())-1;
            int x = Integer.parseInt(st.nextToken())-1;
            int direction = Integer.parseInt(st.nextToken())-1;
            piece[i] = new position(x,y,direction);
            stack[y][x].add(i);
        }
        bw.write(gameStart() + "");	//게임 시작으로 최소 턴 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //게임을 진행하여 4개가 쌓이는 최소 턴을 구하는 함수
    static int gameStart(){
        int answer = 1;
        while(true){
            if(answer>1000)		//1000턴을 넘어갔을 때
                return -1;
            for(int i=0;i<K;i++){
                position cur = piece[i];
                //x, y값 방향대로 이동
                int x = cur.x + dx[cur.direction];
                int y = cur.y + dy[cur.direction];
                if(!inBoard(x,y) || board[y][x] == 2){	//이동하려는 칸이 파란칸일 때
                    cur.direction = directionChange(cur.direction);	//방향 바꾸기
                    //x,y값 방향대로 이동
                    x = cur.x + dx[cur.direction];
                    y = cur.y + dy[cur.direction];
                    piece[i].direction = cur.direction;	//방향 저장
                    if(inBoard(x,y)) {
                        if (board[y][x] == 0) {	//바꾼 뒤 이동하려는 칸이 하얀색
                            whiteMove(cur.x, cur.y, x, y, i);
                        } else if (board[y][x] == 1) {	//바꾼 뒤 이동하려는 칸이 빨간색
                            redMove(cur.x, cur.y, x, y, i);
                        }
                    }
                }else if(board[y][x] == 0){		//이동하려는 칸이 하얀색
                    whiteMove(cur.x, cur.y, x, y, i);
                }else if(board[y][x] == 1){		//이동하려는 칸이 빨간색
                    redMove(cur.x,cur.y, x, y, i);
                }
                if(stackCheck(piece[i].x,piece[i].y))	//게임 종료 조건에 만족할 때
                    return answer;
            }
            answer++;		//턴 증가
        }
    }
    //하얀색 칸으로 이동할 때 함수
    static void whiteMove(int x, int y, int nx, int ny, int id){
        int size = stack[y][x].size();
        int index = stack[y][x].indexOf(id);
        //역순으로 쌓기
        for(int i=index;i<size;i++){
            int pieceNum = stack[y][x].get(index);
            stack[ny][nx].add(pieceNum);
            stack[y][x].remove(index);
            piece[pieceNum].x = nx;
            piece[pieceNum].y = ny;
        }
    }
    //빨간색 칸으로 이동할 때 함수
    static void redMove(int x, int y, int nx, int ny, int id){
        int size = stack[y][x].size();
        int index = stack[y][x].indexOf(id);
        //정순으로 쌓기
        for(int i=size-1;i>=index;i--){
            int pieceNum = stack[y][x].get(i);
            stack[ny][nx].add(pieceNum);
            stack[y][x].remove(i);
            piece[pieceNum].x = nx;
            piece[pieceNum].y = ny;
        }
    }
    //방향 바꾸는 함수
    static int directionChange(int direction){
        if(direction==0)
            return 1;
        else if(direction==1)
            return 0;
        else if(direction==2)
            return 3;
        else
            return 2;
    }
    //좌표가 체스판 안에 존재하는지
    static boolean inBoard(int x, int y){
        if(x>=0 && y>=0 && x<N && y<N)
            return true;
        return false;
    }
    //체스말이 4개 이상 쌓여있을 때
    static boolean stackCheck(int x, int y){
        if(stack[y][x].size()>=4)
            return true;
        return false;
    }
}