#1063 : 킹

풀이방법

사용된 것:

시뮬레이션

Queue

 

 

 

 

 

 

2022.11.14

 

문제에서 말해주는 상황을 그대로 시뮬레이션하기만 하면 되는 단순한 문제이다.

최대 움직임 수가 50번밖에 안 되므로 시간초과 걱정이 없기 때문이다.

 

 

기본적인 풀이 과정은 다음과 같다.

 

1. 킹의 최초 위치와 돌의 최초 위치를 읽어온다.

 

2. 모든 움직임 명령을 읽어와 순서대로 큐에 저장해둔다.

 

3. 큐에 넣은 명령들을 다음과 같은 과정을 따라 수행한다.

   - 이번 명령에 따라 킹을 이동하였을 때에 킹이 판 밖으로 나가는지 판별한다. 만약 킹이 나가게 된다면 아무것도 옮기지 않고 이번 명령을 종료한다.

   - 킹이 판 밖으로 나가지 않는다면, 킹이 옮겨갈 위치에 돌이 있는지 판별한다. 만약 그 위치에 돌이 없다면 킹만 옮기고 이번 명령을 종료한다.

   - 킹이 판 밖으로 나가지 않고 킹이 옮길 곳에 돌이 있다면, 이번 명령에 따라 킹과 돌을 이동하였을 때에 돌이 판 밖으로 나가는지 판별한다. 만약 돌이 판 밖으로 나가게 된다면 아무것도 옮기지 않고 이번 명령을 종료한다. 만약 돌이 판 밖으로 나가지 않는다면 킹과 돌을 옮기고 이번 명령을 종료한다.

 

4. 정답을 출력한다.

 

 

 

나는 다음과 같은 방법을 사용하여 반복작업을 줄였다.

 

1. 체스판 인덱스 변환

문제에서 주어지는 체스판은 행을 아래에서 위로 갈수록 숫자가 커지도록 표시하고, 열은 알파벳으로 표시한다.

그러나 나는 체스판을 일반적인 2차원 배열의 인덱스로 변환하여 시뮬레이션하였다. 가장 왼쪽 위 칸이 (0, 0)이고 가장 오른쪽 아래 칸이 (7, 7)인 8*8 크기의 2차원 배열이다.

이렇게 하면 계산이 편하기 때문이다.

 

 

2. Direction 객체를 사용함

만약 문제에서 주어지는 입력값을 R, L, RT 와 같은 문자열 데이터로 저장하면, 한 칸 한 칸 움직일 때마다 문자열을 숫자로 변환해야 하기 때문에 매우 귀찮다!

그러므로, 덧셈만 하면 계산이 끝나도록, 명령을 미리 숫자 데이터로 변환해놓고 사용하였다.

 

하나의 Direction 객체는 특정한 움직임 명령 하나의 정보를 저장한다.

int 형 변수인 row와 col을 필드로 갖는다.

col은 열 방향으로의 이동 칸 수, row는 행 방향으로의 이동 칸 수이다.

8가지의 이동 명령을 Direction 객체로 변환하면 다음과 같다.

명령 문자열	이동방향	col	row
R	오른쪽으로 한 칸	1	0
L	왼쪽으로 한 칸	-1	1
B	아래로 한 칸	0	1
T	위로 한 칸	0	-1
RT	오른쪽 위로 한 칸	1	-1
LT	왼쪽 위로 한 칸	-1	-1
RB	오른쪽 아래로 한 칸	1	1
LB	왼쪽 아래로 한 칸	-1	1

모든 명령을 이렇게 미리 변환해서 저장해놓으면, 이동할 땐 덧셈만 하면 된다.

 

코드

Java(2022.11.14)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	
	static Queue<Direction> moves = new LinkedList<Direction>();	//움직임 명령을 저장할 큐
	static int kcol, krow, rcol, rrow;	//킹과 돌의 현재 위치
	
	//킹과 돌을 움직이는 함수
	public static void move() {
		Direction dir = moves.poll();
		//옮길 경우 킹의 위치 계산
		int nkcol = kcol+dir.getC();
		int nkrow = krow+dir.getR();
		
		//옮길 경우 킹이 밖으로 나가는지 판별
		if(nkcol>7
				||
				nkcol<0
				||
				nkrow>7
				||
				nkrow<0) return;	//나간다면 아무것도 옮기지 않고 즉시 리턴
		
		//킹이 밖으로 나가지 않는 경우
		//킹이 옮길 곳에 돌이 있는지 판별
		if(nkcol!=rcol || nkrow != rrow) {
			//그곳에 돌이 없는 경우
			//킹만 옮기고 리턴
			kcol = nkcol;
			krow = nkrow;
			return;
		}
		//그곳에 돌이 있는 경우
		//옮길 경우 돌의 위치 계산
		int nrcol = rcol+dir.getC();
		int nrrow = rrow+dir.getR();
		//옮길 경우 돌이 밖으로 나가는지 판별
		if(nrcol>7
				||
				nrcol<0
				||
				nrrow>7
				||
				nrrow<0) return;	//돌이 밖으로 나간다면 즉시 리턴
		
		//돌이 밖으로 나가지 않는 경우
		//킹과 돌을 모두 옮기고 리턴
		kcol = nkcol;
		krow = nkrow;
		rcol = nrcol;
		rrow = nrrow;
		return;
	}

	public static void main(String[] args)  throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/*
		 * 입력값 받아오기
		 */
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//초기 위치 설정
		char[] king = st.nextToken().toCharArray();
		char[] rock = st.nextToken().toCharArray();
		int n = Integer.parseInt(st.nextToken());	//움직임 횟수
		
		kcol = king[0] - 'A';
		krow = 8 - (king[1] - '0');
		rcol = rock[0] - 'A';
		rrow = 8 - (rock[1] - '0');
		
		//움직임 정보 받아오기
		for(int i=0; i<n; i++) {
			String input = br.readLine();
			
			switch(input) {
			case "R" : moves.add(new Direction(1, 0));
				break;
			case "L" : moves.add(new Direction(-1, 0));
				break;
			case "B" : moves.add(new Direction(0, 1));
				break;
			case "T" : moves.add(new Direction(0, -1));
				break;
			case "RT" : moves.add(new Direction(1, -1));
				break;
			case "LT" : moves.add(new Direction(-1, -1));
				break;
			case "RB" : moves.add(new Direction(1, 1));
				break;
			case "LB" : moves.add(new Direction(-1, 1));
				break;
			}
		}
		
		
		/*
		 * 움직이기
		 */
		while(!moves.isEmpty()) move();
		
		/*
		 * 정답 출력
		 */
		
		System.out.print((char)(kcol + 'A'));
		System.out.println(8 - krow);
		System.out.print((char)(rcol + 'A'));
		System.out.print(8 - rrow);
		
		

	}

}

class Direction {
	private int col;	//열 방향으로 움직어야 하는 방향
	private int row;	//행 방향으로 움직여야 하는 방향
	//예)col = 1, row = 1 이라면, 이번 명령은 열 방향으로 1만큼 행 방향으로 1만큼 움직이는 것이므로 RB이다
	
	public Direction (int col, int row) {
		this.col = col;
		this.row = row;
	}
	
	public int getC() {
		return col;
	}
	public int getR() {
		return row;
	}

}