[BOJ] 백준 17837 새로운 게임 2

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

4 4

0 0 2 0

0 0 1 0

0 0 1 2

0 2 0 0

2 1 1

3 2 3

2 2 1

4 1 2

 

 Output 

-1

※ 가장 아래에 있는 말만 움직이는 문제: [BOJ] 17780 새로운 게임

[BOJ] 백준 17780 새로운 게임

 

A번 말의 이동 규칙

▶ 흰색(0)

해당 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.

A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.

ex) A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는

     A번 말이 이동한 후 D, E, A, B, C가 된다.

▶ 빨간색(1)

이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.

ex) A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.

ex) A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는

      E, C, B, G, F, D, A가 된다.

▶ 파란색(2) 

A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 

방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.

※ 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

 

시뮬레이션

▶ 첫번째 턴

① [1]번 말이 흰칸으로 이동하여 [3]말 위에 올라갑니다.

② [2]번 말이 흰칸으로 이동하여 [3], [1] 위에 올라갑니다.

③ [3]번 말이 빨간칸으로 이동하여 쌓인 순서가 반대가 됩니다. (방향은 유지)

    [3], [1], [2] → [2], [1], [3]

④ [4]번 말은 체스판을 벗어나서 방향을 바꿔 한 칸 이동시도 합니다.

    방향 전환 후 이동하는 곳에도 파란색 칸이기에 방향만 전환된 채로 멈춥니다.

 

▶ 두번째 턴

① [1]번 말이 흰칸으로 이동합니다.

    이때, 위에 올려져 있는 [3]번 말도 같이 이동합니다.

② [2]번 말이 파란색 칸으로 이동하므로 방향을 바꿔 빨간색 칸으로 이동합니다.

     올려져 있는 것이 없으므로, 순서가 거꾸로 되지는 않습니다.

③ [3]번 말이 체스판을 벗어나 방향을 바꿔 빨간색 칸으로 이동합니다.

     올려져 있는 것이 없으므로, 순서가 거꾸로 되지는 않습니다.

④ [4]번 말이 파란색 칸으로 이동하므로 방향을 바꿔 이동 시도.

     하지만 벽이기 때문에 방향만 전환된 채로 멈춥니다.

 

구현

체스판 위에 K개의 말들을 어떻게 구현할지 고민해야할 문제입니다.

// List를 이차원 배열형태로 하여 체스 말들의 번호(ID)를 저장
static ArrayList<Integer>[][] board;

// 말들의 번호(ID), 위치(x, y), 방향(dir)
static Horse[] horse;

// 색깔 정보
static int[][] colorMap;

 

 Input 

6 10

0 1 2 0 1 1

1 2 0 1 1 0

2 1 0 1 1 0

1 0 1 1 0 2

2 0 1 2 0 1

0 2 1 0 2 1

1 1 1

2 2 2

3 3 4

4 4 1

5 5 3

6 6 2

1 6 3

6 1 2

2 4 3

4 2 1

 

 Output 

7

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static final int WHITE = 0;
	static final int RED = 1;
	static final int BLUE = 2;
	static int N, K;
	static int[][] colorMap;
	static Horse[] horse; 
	static ArrayList<Integer>[][] board;
	// → ← ↑ ↓
    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 = null;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		// 색깔 정보와 각 칸의 말들의 정보를 초기화 
		colorMap = new int[N+1][N+1];
		board = new ArrayList[N+1][N+1];
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				colorMap[i][j] = Integer.parseInt(st.nextToken());
				board[i][j] = new ArrayList<>();
			}
		}
		horse = new Horse[K+1];
		for(int ID=1; ID<=K; ID++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());
			horse[ID] = new Horse(ID, x, y, dir);
			// 체스판에 말들을 배치
			board[x][y].add(ID);
		}
		
		// 최대 1000번 동안 진행
		for(int turn = 1; turn <= 1000; turn++) {
			// 1~K개의 말들을 순차적으로 움직입니다.
			for(int idx = 1 ; idx <= K ; idx++) {
				// 1000번의 턴 중에 조건을 만족하면 종료.
				if(move(idx)) {
					System.out.println(turn);
					return;
				};
			}
		}
		System.out.println(-1);
	}
	
	private static boolean move(int idx) {
		Horse current = horse[idx];
		
		int nX = current.x + dx[current.dir];
		int nY = current.y + dy[current.dir];
		
		// 체스판을 벗어나거나 파란색 칸인 경우
		if(!isRangeValid(nX, nY)) {
			// 이동하는 말의 방향을 반대로 전환하여 이동하려는 칸 위치를 함께 바꿔준다.
			current.changeDirection();
		    nX = current.x + dx[current.dir];
		    nY = current.y + dy[current.dir];
		}
		

		// 체스판을 벗어나거나 파란색 칸이면 위에서 방향전환 된 것으로 continue
		// 체스판 내에서 빨간색이나 흰색칸으로 이동되는 경우
		if(isRangeValid(nX, nY)) {
			actionByColor(current, nX, nY);
			// 이동된 칸에 올려져 있는 말의 개수 확인 
			if(board[nX][nY].size() >= 4) return true;
		}
		return false;
	}
	
	private static void actionByColor(Horse current, int nX, int nY) {
		// 이동 전 말의 위치
		ArrayList<Integer> from = board[current.x][current.y];
		// 이동 후 말의 위치
		ArrayList<Integer> to = board[nX][nY];
		// 이동하는 말이 위치한 칸에서 놓여져 있는 위치(높이)
		int position = from.indexOf(current.ID);
		// 원소가 변하면서 size()값도 함께 변하므로 변수로 저장
		int fromSize = from.size();
		
		// 흰색 or 빨간색에 따른 처리
		switch(colorMap[nX][nY]) {
		case WHITE:
		    // 이동하는 말 위에 올려져 있는 말들과 함께 이동
		    for(int i = position; i < fromSize; i++){
		    	// 리스트의 원소가 삭제되면서 위치가 당겨져 옵니다.
		        int horseID = from.remove(position);
		        // 해당 말의 좌표 변경
		        horse[horseID].x = nX;
		        horse[horseID].y = nY;
		        to.add(horseID);
		    }
		    break;
		    
		case RED:
			// 이동하는 말 위에 올려져 있는 말들을 뒤집어서 함께 이동 
			for(int i = position; i < fromSize; i++){
		    	// 뒤집어서 다음 위치로 이동해야 하기에 리스트 끝자리에서 삭제
		    	int horseID = from.remove(from.size()-1);
		        // 해당 말의 좌표 변경
		        horse[horseID].x = nX;
		        horse[horseID].y = nY;
		        to.add(horseID);
		    }
		    break;
		}
	}
	
	private static boolean isRangeValid(int nX, int nY) {
		if( nX > N || nX < 1 || nY > N || nY < 1 || colorMap[nX][nY] == BLUE) {
			// 체스판을 벗어나거나 파란색 칸인 경우
			return false;
		}
		return true;
	}
}

class Horse{
	int ID, x, y, dir;
	Horse(int ID, int x, int y, int dir){
		this.ID = ID;
		this.x = x;
		this.y = y;
		this.dir = dir;
	}
	public void changeDirection() {
		// → ← ↑ ↓
		if(dir == 1) dir = 2; 
		else if(dir == 2) dir = 1;
		else if(dir == 3) dir = 4;
		else if(dir == 4) dir = 3;
	}
}