SWEA 4615 - 재미있는 오셀로 게임 ( JAVA )

 

SW Expert Academy

[ 문제,  출처 - SW Expert Academy ]

 

---

 + 고려해야 할 부분 ( 부분오답이 생겼을 경우, ) 

1. 플레이어가 '놓을 돌' 과 '놓여진 돌' 사이에 빈공간이 있으면 안된다. 

    ex)

'검'

흰

흰

검

 '검'을 놓을 수 없다.

 

2. 플레이어가 '놓을 돌'을 기준으로 처음 '놓여진 돌' 까지만 바뀐다. 

    ex)

'검'

흰

검

흰

검

일 경우,  

'검'

검

검

흰

검

이 된다. 

 

3. 플레이어가 '놓을 돌' 과 '놓여진 돌' 사이에 하나 이상의 돌이 있을 수 있다. 

    ex)

'검'

흰

흰

흰

검

일 경우, 

'검'

검

검

검

검

모두 바뀐다. 

---

 

[ 알고리즘 ] 

( 구현 , 팔방탐색 ) + 인덱스 위치 맞추기,, 

 

 

1. 흑 = 1, 백 = 2 로 주어지기 때문에 N x N 크기의 int[][] 배열을 사용한다. 

 

2. 보드의 중간에 처음 돌을 배치한다. ( N/2 = 중간 ) 

 

3. 주어진 돌의 위치에 맞게 흑 / 백 돌을 배치한다. 

 : int[][] 배열의 인덱스는 0 부터 시작하여 [행][열] 이지만, 문제에서는 1부터 시작하여 열 - 행 으로 주어진다. 

   그렇기 때문에, 주어진 위치를 -1 하여 바꿔준다. ex ) 1 2 1 일 경우, map[1][0]  = 흑돌 (1)

 

4. 가로/세로/대각선으로 8방탐색을 한다. 

   4-1. 탐색 범위가 map 의 범위를 벗어나거나, 탐색한 값이 빈칸이라면 다음 방향으로 탐색한다. 

   4-2. 탐색 값이 '놓을 돌' 과 다른 색의 돌이라면 아래 과정을 수행한다, ( ex) '검' - 흰 or '흰' - 검 ) 

• 탐색한 방향 ( 한방향으로 쭉 ) 으로 한칸씩 이동한다. 
• '놓을 돌'과 다른색의 돌이라면 Queue 에 삽입한다. ( * Queue : 색 바꿀 돌들 ) 
• map 의 범위를 벗어나거나, 빈칸을 만난다면 해당 과정을 종료한다. 
• '놓을 돌' 과 같은 돌의 색을 만났다면, 현재 Queue 에 담겨있는 돌을 '놓을 돌' 과 같은 색으로 만든다. 
• ex)  '검' 흰 흰 검 일 경우, Queue 에 흰 흰 을 담아두었다가 검을 만났을 경우 검정색으로 바꾼다. 

 

---

[ 코드 ] 

import java.util.*;
import java.io.*;

public class Solution_SWEA_4615_D3 {
	static int dx[] = {-1,-1,-1,0,0,1,1,1};
	static int dy[] = {-1,0,1,-1,1,-1,0,1}; // 팔방탐색
	private static int N;
	private static int[][] map;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st; 
		
		int t = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=t; tc++) {
			st= new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()); // 보드의 한변 길이 ( 4,6,8 ) 
			int M = Integer.parseInt(st.nextToken()); // 돌을 놓는 횟수 
			
			// 흑돌 : 1 , 백돌 : 2 
			map = new int[N][N];
			// 보드의 중간에 처음 돌을 배치한다. 
			map[N/2-1][N/2] = map[N/2][N/2-1] = 1;  
			map[N/2-1][N/2-1] = map[N/2][N/2] = 2;
			
			while(M-->0) {
				st= new StringTokenizer(br.readLine(), " ");
				int r= Integer.parseInt(st.nextToken());
				int c= Integer.parseInt(st.nextToken());
				int color= Integer.parseInt(st.nextToken());
				//인덱스와 위치 맞추기
				int x = c-1;
				int y = r-1;
				// 돌 놓기 
				map[x][y] = color;
	
				for(int dir=0; dir<8; dir++) {
					int nx = x+dx[dir];
					int ny = y+dy[dir];
					
					if(isOut(nx,ny)||map[nx][ny]==0) {
						continue; 
					}
					if(map[nx][ny] != color) {
						find(x,y,dir);
					}	
				}
			}
			
			int black = 0; 
			int white = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j]==1) black++;
					if(map[i][j]==2) white++; 
				}
			}
	
			System.out.print("#"+tc+" "+black+" "+white);
			System.out.println();
		}// end of testcase for 
	}// end of main 
    
	static class Point{
		int r;
		int c;
		public Point(int r, int c) {
			this.r=r;
			this.c=c;
		}
	}
	private static void find(int r, int c, int direction) {
		int rock= map[r][c]; //방금 '놓은 돌'의 색깔 
		Queue<Point> que = new LinkedList<>();
        //같은 색을 만나서 끝난것인지, 벽이나 빈칸 만난것인지 판단 값 
		boolean flag = true; 
        
		while(true) {
			r += dx[direction]; 
			c += dy[direction]; 
			
			//가다가 벽을 만났으면, 같은 색 못만난 것  or 빈칸이 나왔을 경우 
			if(isOut(r,c) || map[r][c] ==0 ) {
				flag= false; 
				break; 
			}
			//방금 놓은 돌과 같은 색의 말 만남 
			if(map[r][c] == rock) break; 
            
			//다른색 돌일 경우 
			que.add(new Point(r,c)); 
			
		}
		
		// flag = flase 일 경우에는, 돌의 색을 바꿀 필요 x 
		if(!flag) return ;
		
		while(!que.isEmpty()) {
			Point p= que.poll();
			map[p.r][p.c] = rock; 
		}
	}
	
	private static boolean isOut(int r, int c) {
		return (r<0 || r>=N || c<0 || c>=N); 
	}
}// end of class

끗 ! 길다 길어