SW 역량 테스트 기출 문제(새로운 게임 2)

[새로운 게임 2 - 17837]

 

 

* 로직

• 맵의 값, 각각의 말 정보들을 관리할 수 있는 리스트에 대한 클래스를 만들어 2차원 배열 맵을 생성한다 (MapInfo_17837[][])
• 말의 위치, 방향을 관리할 수 있는 클래스를 만든다(Knight)
  
  
• 1번부터 K번째까지의 말의 정보들을 리스트에 순차적으로 담는다
• 1번말부터 꺼내어 턴을 진행한다
  • 1번말이 존재하는 맵의 위치에 해당 말 위에 쌓여있는 말들이 존재하는지 확인한다
  • 만약 존재한다면 임시 리스트에 말들의 정보를 담고, 현재 위치에 존재하는 말들은 제거해준다
  • 이후, 1번말의 방향에 맞게 이동할 위치에 대하여
    • 만약, 범위를 벗어나거나 파란칸(2) 이라면
      • 말의 방향을 반대 방향으로 바꿔주고 바뀐 방향으로 한 칸 이동한다
      • 한 칸 이동할 때
        • 이동할 위치가 범위를 벗어나거나 파란칸이라면 -> 현재칸에 머문다
        • 흰색칸이라면 -> 이동
        • 빨간색 칸이라면 -> 임시 리스트에 있는 말들의 순서를 반대로 바꾼 뒤, 이동할 칸의 리스트에 말들의 정보를 추가한다
    • 만약, 흰색 칸(0)이라면
      • 이동
    • 만약, 빨간색 칸(1)이라면
      • 임시 리스트에 있는 말들의 순서를 반대로 바꾼 뒤, 이동할 칸의 리스트에 말들의 정보를 추가한다
  • 1번말에 대한 과정이 끝난 뒤, 말이 4개 이상 쌓인 곳이 존재한다면 종료시킨다
• 4개 이상 쌓인 곳이 없다면 그 다음 말을 진행하고 K번째 말까지 이를 진행한다
• K번째 말까지 진행이 완료되면 턴을 1 증가시킨다

말들의 정보를 담을 때, 객체는 공유된다는 점을 고려해야한다. 예를 들어 다음 칸으로 이동한다면 좌표를 함께 갱신해주거나 방향이 바뀌면 방향을 갱신 등이다.

 

 

// 새로운 게임 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class MapInfo_17837 {

	public int value;
	public LinkedList<Knight> queue;

	public MapInfo_17837(int value) {
		this.value = value;
		this.queue = new LinkedList<>();
	}
}

class Knight {

	public int y, x;
	public int dir;

	public Knight(int y, int x, int dir) {
		super();
		this.y = y;
		this.x = x;
		this.dir = dir;
	}
}

public class Problem_17837 {

	static int N;
	static MapInfo_17837[][] Map;
	static int K;
	static LinkedList<Knight> KnightQueue;

	// 시계방향
	static int[][] directions = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };

	// 오른, 왼, 위, 아래(1~4)
	static int[] dir = { -1, 1, 3, 0, 2 };

	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		String input = br.readLine();
		st = new StringTokenizer(input, " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		Map = new MapInfo_17837[N + 1][N + 1];

		// input map
		for (int i = 1; i <= N; ++i) {
			input = br.readLine();
			st = new StringTokenizer(input, " ");

			for (int j = 1; j <= N; ++j) {
				Map[i][j] = new MapInfo_17837(Integer.parseInt(st.nextToken()));
			}
		}

		// input Knight
		KnightQueue = new LinkedList<>();
		for (int i = 0; i < K; ++i) {
			input = br.readLine();
			st = new StringTokenizer(input, " ");
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());

			Knight knight = new Knight(y, x, dir);
			KnightQueue.offer(knight);
			Map[y][x].queue.add(knight);
		}

		result = 0;
		doSolution();
		System.out.println(result);
	}

	private static void doSolution() {

		// 말의 개수만큼 한 사이클씩 돌리기
		int cycle = 1;
		while (true) {

			if (cycle > 1000) {
				result = -1;
				return;
			}

			int size = KnightQueue.size();
			for (int s = 0; s < size; ++s) {
				Knight q = KnightQueue.get(s);

				doProcess(q);
				
				// 진행 도중 4 이상의 말들이 쌓여있다면 종료
				boolean find = false;
				for (int i = 0; i < KnightQueue.size(); ++i) {
					if(Map[KnightQueue.get(i).y][KnightQueue.get(i).x].queue.size() >= 4) {
						find = true;
						break;
					}
				}

				if (find) {
					result = cycle;
					return;
				}
			}			

			cycle++;
		}
	}

	private static void doProcess(Knight q) {

		// 해당 말위에 다른 말들도 존재한다면 리스트에 따로 담기(같이 이동해야하니까)
		LinkedList<Knight> list = new LinkedList<>();
		int idx = Map[q.y][q.x].queue.indexOf(q);

		// 현재 칸에 존재하는 말의 정보는 제거
		for (int i = idx; i < Map[q.y][q.x].queue.size(); ++i) {
			Knight tmp = Map[q.y][q.x].queue.get(i);
			list.add(tmp);
		}

		for (int i = 0; i < list.size(); ++i) {
			Map[q.y][q.x].queue.remove(list.get(i));
		}

		// 이동 가능한 조건들 고려
		int moveY = q.y + directions[0][dir[q.dir]];
		int moveX = q.x + directions[1][dir[q.dir]];

		// 이동하려는 칸이 범위를 벗어나거나 파란색 칸인 경우
		if (!isRanged(moveY, moveX) || Map[moveY][moveX].value == 2) {

			// 방향을 반대로 바꾸고 한 칸 이동
			if (q.dir == 1)
				q.dir = 2;
			else if (q.dir == 2)
				q.dir = 1;
			else if (q.dir == 3)
				q.dir = 4;
			else if (q.dir == 4)
				q.dir = 3;

			moveY = q.y + directions[0][dir[q.dir]];
			moveX = q.x + directions[1][dir[q.dir]];

			// 만약 이동할 위치가 범위를 벗어나거나, 파란칸이라면
			if (!isRanged(moveY, moveX) || Map[moveY][moveX].value == 2) {

				// 현재칸에 머문다(방향은 바뀐 상태 유지)
				for (Knight tmp : list) {
					Map[q.y][q.x].queue.add(tmp);
					tmp.y = q.y;
					tmp.x = q.x;
				}
			}

			// 흰색칸 or 빨간칸이라면 이동
			else {
				
				// 흰색 칸이라면 -> 이동
				if(Map[moveY][moveX].value == 0) {
					for (Knight tmp : list) {
						Map[moveY][moveX].queue.add(tmp);
						tmp.y = moveY;
						tmp.x = moveX;
					}
				}
				
				// 빨간 칸이라면
				else if(Map[moveY][moveX].value == 1) {
					
					// 말들의 순서를 뒤집어 주고 이동
					for (int i = list.size() - 1; i >= 0; --i) {
						Map[moveY][moveX].queue.add(list.get(i));
						list.get(i).y = moveY;
						list.get(i).x = moveX;
					}
				}
			}
		}

		// 이동하려는 칸이 흰색인 경우
		else if (Map[moveY][moveX].value == 0) {

			// 이동
			for (Knight tmp : list) {
				Map[moveY][moveX].queue.add(tmp);
				tmp.y = moveY;
				tmp.x = moveX;
			}
		}

		// 빨간색인 경우
		else if (Map[moveY][moveX].value == 1) {

			// 말들의 순서를 뒤집어 주고 이동
			for (int i = list.size() - 1; i >= 0; --i) {
				Map[moveY][moveX].queue.add(list.get(i));
				list.get(i).y = moveY;
				list.get(i).x = moveX;
			}
		}

		// 파란색인 경우
		else if (Map[moveY][moveX].value == 2) {

			// 방향을 반대로 바꾸고 한 칸 이동
			if (q.dir == 1)
				q.dir = 2;
			else if (q.dir == 2)
				q.dir = 1;
			else if (q.dir == 3)
				q.dir = 4;
			else if (q.dir == 4)
				q.dir = 3;

			moveY = q.y + directions[0][dir[q.dir]];
			moveX = q.x + directions[1][dir[q.dir]];

			// 만약 이동할 위치가 범위를 벗어나거나, 파란칸이라면
			if (!isRanged(moveY, moveX) || Map[moveY][moveX].value == 2) {

				// 현재칸에 머문다(방향은 바뀐 상태 유지)
				for (Knight tmp : list) {
					Map[q.y][q.x].queue.add(tmp);
					tmp.y = q.y;
					tmp.x = q.x;
				}
			}

			// 흰색칸이라면 이동
			else {

				for (Knight tmp : list) {
					Map[moveY][moveX].queue.add(tmp);
					tmp.y = moveY;
					tmp.x = moveX;
				}
			}
		}

	}

	private static boolean isRanged(int y, int x) {
		if (y >= 1 && y <= N && x >= 1 && x <= N)
			return true;
		return false;
	}

}