[백준] 17837 새로운 게임2

---

 

문제에 주어진 조건에 따라 구현하는 문제이다.

 

문제에서 주어지는 체스판 각 칸의 색을 저장하는 배열 뿐만 아니라 추가적으로 체시판 각 칸에 위치한 말 정보를 저장할 배열을 따로 선언하여 사용해야한다.

 

파이썬의 경우 3차원 배열, 자바는 2차원 ArrayList 배열을 가지고 해결하였다.

 

Python

 

	from sys import stdin
	readline = stdin.readline
	N, K = map(int, readline().split())
	_map = [list(map(int, readline().split())) for _ in range(N)]
	horses = [list(map(int, readline().split())) for _ in range(K)]
	hmap = [[[] for _ in range(N)] for _ in range(N)]
	dr, dc = (0, 0, -1, 1), (1, -1, 0, 0)
	for i in range(len(horses)):
	hmap[horses[i][0]-1][horses[i][1]-1].append(i)
	def solve():
	for turn in range(1, 1001):
	for i in range(K):
	flag = move(i)
	if flag:
	return turn
	return -1
	def move(horse):
	r, c, d = horses[horse]
	nr, nc = r + dr[d-1], c + dc[d-1]
	if not(0<nr<=N and 0<nc<=N) or _map[nr-1][nc-1] == 2:
	if d == 1 or d == 2:
	d = (d + 2) % 2 + 1
	else:
	d = (d - 2) % 2 + 3
	nr, nc = r + dr[d-1], c + dc[d-1]
	if not(0<nr<=N and 0<nc<=N) or _map[nr-1][nc-1] == 2:
	horses[horse][2] = d
	return False
	idx = 0
	for i in range(len(hmap[r-1][c-1])):
	if hmap[r-1][c-1][i] == horse:
	idx = i
	break
	moving = hmap[r-1][c-1][idx:]
	hmap[r-1][c-1] = hmap[r-1][c-1][:idx]
	if _map[nr-1][nc-1] == 1:
	moving = list(reversed(moving))
	horses[horse] = [nr, nc, d]
	for i in moving:
	horses[i][:2] = [nr, nc]
	hmap[nr-1][nc-1] += moving
	if len(hmap[nr-1][nc-1]) >= 4:
	return True
	return False
	print(solve())

view raw BOJ17837.py hosted with ❤ by GitHub

 

Java

 

	import java.util.*;
	import java.io.*;
	public class BOJ17837 {
	static int K;
	static int N;
	static int[][] map;
	static int[] dr = {0, 0, -1, 1};
	static int[] dc = {1, -1, 0, 0};
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String[] temp = br.readLine().split(" ");
	N = Integer.parseInt(temp[0]);
	K = Integer.parseInt(temp[1]);
	map = new int[N][N];
	ArrayList<Integer>[][] piece_map = new ArrayList[N][N];
	int[][] pieces = new int[K][3];
	for(int r=0;r<N;r++){
	String[] line = br.readLine().split(" ");
	for(int c=0;c<N;c++){
	map[r][c] = Integer.parseInt(line[c]);
	piece_map[r][c] = new ArrayList<Integer>();
	}
	}
	for(int i=0;i<K;i++){
	String[] line = br.readLine().split(" ");
	piece_map[Integer.parseInt(line[0])-1][Integer.parseInt(line[1])-1].add(i);
	pieces[i][0]= Integer.parseInt(line[0])-1;
	pieces[i][1]= Integer.parseInt(line[1])-1;
	pieces[i][2]= Integer.parseInt(line[2]);
	}
	System.out.println(solve(piece_map, pieces));
	}
	public static int solve(ArrayList<Integer>[][] piece_map, int[][] pieces){
	boolean flag = false;
	for(int turn=1;turn<=1000;turn++){
	for(int i=0;i<K;i++){
	flag = move(i, piece_map, pieces);
	if(flag == true){
	return turn;
	}
	}
	}
	return -1;
	}
	public static boolean move(int h, ArrayList<Integer>[][] piece_map, int[][] pieces){
	int r = pieces[h][0]; int c = pieces[h][1]; int d = pieces[h][2];
	int nr = r + dr[d-1]; int nc = c + dc[d-1];
	if((nr >= N || nr < 0 || nc >= N || nc < 0) || map[nr][nc] == 2){
	if(d == 1 || d == 2){
	d = (d + 2) % 2 + 1;
	} else {
	d = (d - 2) % 2 + 3;
	}
	nr = r + dr[d-1];
	nc = c + dc[d-1];
	if((nr >= N || nr < 0 || nc >= N || nc < 0) || map[nr][nc] == 2){
	pieces[h][2] = d;
	return false;
	}
	}
	int idx = 0;
	for(int i=0;i<piece_map[r][c].size();i++){
	if(piece_map[r][c].get(i) == h){
	idx = i;
	break;
	}
	}
	ArrayList<Integer> moving = new ArrayList<>();
	ArrayList<Integer> temp = new ArrayList<>();
	for(int i=0;i<piece_map[r][c].size();i++){
	if(i < idx){
	temp.add(piece_map[r][c].get(i));
	} else{
	moving.add(piece_map[r][c].get(i));
	}
	}
	piece_map[r][c] = temp;
	temp = new ArrayList<>();
	if(map[nr][nc] == 1){
	for(int i=moving.size()-1;i>=0;i--){
	temp.add(moving.get(i));
	}
	moving = temp;
	}
	temp = new ArrayList<>();
	temp.addAll(piece_map[nr][nc]);
	temp.addAll(moving);
	pieces[h][0] = nr;
	pieces[h][1] = nc;
	pieces[h][2] = d;
	for(int i=0;i<moving.size();i++){
	if (moving.get(i) != h){
	pieces[moving.get(i)][0] = nr;
	pieces[moving.get(i)][1] = nc;
	}
	}
	piece_map[nr][nc] = temp;
	if(temp.size() >= 4){
	return true;
	}
	return false;
	}
	}

view raw BOJ17837.java hosted with ❤ by GitHub