[Baekjoon] 9204_체스

Silver I

문제(출처: https://www.acmicpc.net/problem/9204)

---

< 체스 >

 

문제 풀이 

 

bfs를 활용하여 대각선으로 이동가능한 모든 경우를 탐색한다. 이동하면서 이동 위치도 같이 저장해 둔다.

 

 my solution (Java)

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

public class _9204_ { // 체스
	static int dx[] = { -1, -1, 1, 1 };
	static int dy[] = { -1, 1, -1, 1 };

	static class Bishop {
		private int x;
		private char y;
		private int cnt;
		private ArrayList<Bishop> list;

		public Bishop(int x, char y, int cnt, ArrayList<Bishop> list) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.list = list;
		}

		public Bishop(int x, char y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int T = Integer.parseInt(bf.readLine());
		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(bf.readLine());
			char y1 = st.nextToken().charAt(0);
			int x1 = Integer.parseInt(st.nextToken());
			char y2 = st.nextToken().charAt(0);
			int x2 = Integer.parseInt(st.nextToken());

			if(x1==x2 && y1==y2) {
				bw.write("0 "+y1+" "+x1+"\n");
			}else {
				ArrayList<Bishop> temp = bfs(x1, y1, x2, y2);
				if (temp == null) {
					bw.write("Impossible\n");
				}else {
					bw.write((temp.size()+1) + " "+y1+" "+x1+" ");
					for (Bishop bishop : temp) {
						bw.write(bishop.y + " " + bishop.x + " ");
					}
					bw.write(y2+" "+x2+"\n");
				}
			}
		}
		bw.flush();
	}

	private static ArrayList<Bishop> bfs(int x1, char y1, int x2, char y2) {
		boolean visited[][] = new boolean[8][8];
		Queue<Bishop> queue = new LinkedList<>();

		visited[8 - x1][y1 - 'A'] = true;
		queue.add(new Bishop(x1, y1, 0, new ArrayList<>()));

		int resultX = 8 - x2;
		int resultY = y2 - 'A';

		while (!queue.isEmpty()) {
			Bishop bishop = queue.poll();
			for (int i = 0; i < 4; i++) {
				int y = bishop.y - 'A';
				int x = 8 - bishop.x;
				while (x >= 0 && x < 8 && y >= 0 && y < 8) {
					x += dx[i];
					y += dy[i];
					if (x >= 0 && x < 8 && y >= 0 && y < 8 && !visited[x][y]) {
						visited[x][y] = true;
						ArrayList<Bishop> temp=new ArrayList<>();
						for(Bishop b: bishop.list) {
							temp.add(b);
						}
						if (resultX == x && resultY == y) {
							return temp;
						}
						if (bishop.cnt + 1 == 4) {
							return null;
						}
						temp.add(new Bishop(Math.abs(8 - x), (char) (y+'A')));
						queue.add(new Bishop(Math.abs(8 - x), (char) (y+'A'), bishop.cnt + 1, temp));
					}
				}
			}
		}
		return null;
	}
}

변수)
T : 테스트 케이스 개수
x1, y1, x2, y2 : 시작 위치, 도착 위치
temp : 이동 경로

 

Bishop

비숍 위치 x, y

움직인 횟수 cnt

이동 경로 ArrayList <Bishop> list

 

Main

테스트 케이스 개수를 입력받는다. 테스트 케이스 수만큼 다음 과정을 반복한다.

 

1) 시작 위치, 도착 위치 입력

2) 시작 위치와 도착 위치가 같다면 0과 위치를 출력

3) 시작 위치와 도착 위치가 같지 않다면 bfs함수 호출 

4) 반환 값이 null이라면 Impossible 출력, null이 아니라면 (ArrayList의 크기+1) 출력 및 경로 출력

 

bfs(int x1, char y1, int x2, char y2)

x1과 y1 좌표를 각각 8-x1, y1-'A'로 바꿔야 한다. 시작 위치를 방문 표시 후 queue에 객체로 저장한다. queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) 1번 값에서 현재 좌표를 꺼내와 각각 y-'A', 8-x로 변환

3) 대각선으로 이동해서 체스판 범위 안이며 아직 방문하지 않은 곳이면 방문

4) 만약 도착 위치에 도착했다면 이동 경로 반환

5) 4번 움직여서 도착 위치에 도착하지 못했다면 null 반환

6) 현재 이동 경로에서 새로 경로를 추가 및 queue에 Bishop 객체 추가

 

---

---