새로운게임_Java

문제 접근 하기 위해 아래 2가지를 만들어주었다. 

1. 말의 상태를 관리하는 class를 생성

=> 체스의 상태를 관리해줘야 하는 이유는 체스가 움직이면 맨 밑에 있는지 위치는 어디인지 방향은 어디인지를 명확하게 알기 위함이다.

2. 맵, ArrayList 맵 

=> 맵은 0,1,2 이렇게 표시만 되는 부분이고 ArrayList 맵은 어떤 체스들이 들어 있는지 보여준다. 예를 들면 다음과 같다.

ArrayList_Map[0][0] = { 1,2,3 } 의 의미는 (0,0) 좌표에 체스 1,2,3 이 포진해 있다. 이렇게 해석하면 된다. 

3. 우선 main으로 쭉 나열해서 푸는 방법 그리고 재귀적으로 푸는 방법 2가지 모두 시도해보았다. 아무래도 main에다 다 때려박아서 하는게 속도는 더 좋았다. 그치만 처리해줘야하는 부분이 더 많아져서 이건 좀 까다로웠다. 

본론으로 돌아와서 순서대로 어떤 부분을 구현했는지 보자!

우선은 입력부터 보자. (간단하다.)

N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N+1][N+1];
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}//end of for loop
		
		
		al = new ArrayList[N+1][N+1];
		for(int i=0; i<=N; i++) {
			for(int j=0; j<=N; j++) {
				al[i][j] = new ArrayList<>();
			}
		}

 

두번째는 체스의 정보를 받아와 chess에 담아주었다. 여기서 보면 mapPosDir 이라는 구조체가 있는데 

chess = new mapPosDir[K+1];
		
		for(int i=1; i<=K; i++) {
			st = new StringTokenizer(br.readLine());
			int posX = Integer.parseInt(st.nextToken());
			int posY = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());
			
			
			chess[i] = new mapPosDir(posX, posY, dir, true);
			
			al[posX][posY].add(i);
		}

 

mapPosDir 구조체는 이렇게 정의되어 있다. 어쩃든 말의 상태를 관리한다. 

static class mapPosDir{
		int x;
		int y;
		int dir;
		boolean below; //현재 말이 가장 아래에 있는지 판단
		mapPosDir(int x, int y, int dir, boolean below){
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.below = below;
		}
	}

K개의 말을 이제 방향에 맞춰 이동시켜줘 보자

체스를 움직일꺼면 현재좌표 그리고 다음에 갈좌표가 필요하다. 당연하게도..

그리고 방향도 중요하다.

여기서 2가지 분기로 나눈 이유는 예외되는 부분이 있기 떄문이다. (파란색, 범위초과) 

그래서 파란색 부분은 어차피 방향만 바꿔줄꺼기 때문에

Change_State(x,y,nx,ny,2);

로 넘겨주었다. 

for(int chessNumber=1; chessNumber<=K; chessNumber++) {
				if(!chess[chessNumber].below) {
					continue;
				}
				int x = chess[chessNumber].x;
				int y = chess[chessNumber].y;
				int dir = chess[chessNumber].dir;
				int nx = chess[chessNumber].x + dx[dir];
				int ny = chess[chessNumber].y + dy[dir];
				
				if( (nx<1 || nx>=N+1 || ny<1 || ny>=N+1) || map[nx][ny] == 2) {
					Change_State(x,y,nx,ny,2);
				}else {
					Change_State(x,y,nx,ny,map[nx][ny]);
				}
			}

 

Change_State를 보자 정말 간단하다.

생각해보면 체스를 이동시킬 때 다음칸이 흰색, 레드, 블루, 범위밖 이렇게 나오기 때문에 분기를 생성해준다. 

그리고 각 블락에 대한 예외처리가 하나 더 생긴다. 그건 그 넥스트 포지션에 체스가 이미 있는지 없는지 그 처리를 해주면 된다.

다만, 체스를 움직일때는 현재 체스의 위치를 다음 위치로 변경하는것과

체스가 여러개 겹칠 때 마지막에 내가 있었는지를 항상 체크해주면서 문제를 풀어가야 한다.

예를 들어서 (0,0)에는 체스 1이 있어서 마지막위치니까 below(구조체에서 만든 변수) 를 true 시켜주었다.

그런데 다음 위치의 체스를 둘때는 이 (0,0)에 below를 false로 만드는것이 중요하다 그 얘기였다. 

그리고 하나 더 챙겨야 할건 파란색과 범위밖의 경우에는 방향만 바뀐다. 그런데 방향이 바뀌고 이동할 수 있으면 이동하지만

그렇지 못하면 스탑해줘야 한다. 이 경우는 프로그래밍적으로 봤을 때

넥스트포지션으로 이동 -> 그런데 파란색 or 범위밖 그러면 방향을 reverse 로 set! -> 그리고 여기서 한번 더 재귀를 태워서 

흰색, 빨간색, 파란색 혹은 범위밖을 체크할 수 있도록 하면 된다. 당연히 한번 더 파란색 혹은 범위밖의 경우에는 예외 처리를 둬서 그냥

스탑을 하게 만들면 된다. (근데 이게 사실 메인에서 한번 호출하고 함수내에서 한번 더 호출하는건 이미 stop 시켜라 의미이기도 하다.)

- 파란색이나 범위밖이면 스탑시켜주세요! 

if(nnx>=1 && nny>=1 && nnx<=N && nny<=N) {
				if(map[nnx][nny]!=2)
					Change_State(x,y,nnx,nny,map[nnx][nny]);
			}

- Change_State

if(Ms == 0) {
			//말이 있는 경우 
			if(al[nx][ny].size()!=0) {
				for(int i=0; i<al[x][y].size(); i++) {
					int idxChess = al[x][y].get(i);
					al[nx][ny].add(idxChess);
					
					chess[idxChess].x = nx;
					chess[idxChess].y = ny;
					chess[idxChess].below=false;
				}

				al[x][y].clear();

			//말이 없는 경우 
			}else {
				for(int i=0; i<al[x][y].size(); i++) {
					int idxChess = al[x][y].get(i);
					al[nx][ny].add(idxChess);
					chess[idxChess].x = nx;
					chess[idxChess].y = ny;
					chess[idxChess].below=false;
				}
				chess[al[x][y].get(0)].below = true;
				al[x][y].clear();
			}
			
		//빨간색 칸으로 이동한 경우 
		}else if(Ms == 1) {
			
			//말이 있는 경우 
			if(al[nx][ny].size()!=0) {
				
				for(int i=0; i<al[x][y].size(); i++) {
					chess[al[x][y].get(i)].below=false;
				}
				
				for(int i=al[x][y].size()-1; i>=0; i--) {
					int idxChess = al[x][y].get(i);
					al[nx][ny].add(idxChess);
					chess[idxChess].x = nx;
					chess[idxChess].y = ny;
				}
				
				
				al[x][y].clear();
				
		
			//말이 없는 경우 
			}else {
			
				
				int size = al[x][y].size();
				int firstChessNumber = al[x][y].get(size-1);
				
				for(int i=al[x][y].size()-1; i>=0; i--) {
					int idxChess = al[x][y].get(i);
					
					al[nx][ny].add(idxChess);
					chess[idxChess].x = nx;
					chess[idxChess].y = ny;
				}
				al[x][y].clear();
				
				//옮긴 후에 다 false처리
				for(int i=0; i<al[nx][ny].size(); i++) {
					chess[al[nx][ny].get(i)].below = false;
				}
				chess[firstChessNumber].below = true;
				
			}
		}else if(Ms == 2) {
			
			int dir = reverseDirection(chess[al[x][y].get(0)].dir);
			//방향을 바꾼다 
			chess[al[x][y].get(0)].dir = dir;
			int nnx = chess[al[x][y].get(0)].x + dx[dir];
			int nny = chess[al[x][y].get(0)].y + dy[dir];
			if(nnx>=1 && nny>=1 && nnx<=N && nny<=N) {
				if(map[nnx][nny]!=2)
					Change_State(x,y,nnx,nny,map[nnx][nny]);
			}
		}

 

거의 다왔다. 이제 체스를 돌면서 체스가 위치한 곳에 만약 체스가 4개 이상이면 그 자리에서 while 을 탈출하면 된다. 그 조건이 충족되지 않으면 횟수를 증가시켜 주면 된다 + 횟수가 1000초과 되면 answer를 -1로 set하면 된다. 

	//기저 조건
			if(moveComplete()) {
				answer = depth;
				break k;
			}
			depth++;

 

전체 소스 코드

 

 

말이 안되거나 이해가 안되면 뒤에 내용도 참고 부탁드립니다.

감사합니다.