[SWEA] 4615. 재미있는 오셀로 게임

문제

오셀로라는 게임은 흑돌과 백돌을 가진 사람이 번갈아가며 보드에 돌을 놓아서 최종적으로 보드에 자신의 돌이 많은 사람이 이기는 게임이다.

보드는 4x4, 6x6, 8x8(가로, 세로 길이) 크기를 사용한다. 6x6 보드에서 게임을 할 때, 처음에 플레이어는 다음과 같이 돌을 놓고 시작한다(B : 흑돌, W : 백돌).

4x4, 8x8 보드에서도 동일하게 정가운데에 아래와 같이 배치하고 시작한다.

그리고 흑, 백이 번갈아가며 돌을 놓는다.

처음엔 흑부터 시작하는데 이 때 흑이 돌을 놓을 수 있는 곳은 다음과 같이 4군데이다.

플레이어는 빈공간에 돌을 놓을 수 있다.

단, 자신이 놓을 돌과 자신의 돌 사이에 상대편의 돌이 있을 경우에만 그 곳에 돌을 놓을 수 있고, 그 때의 상대편의 돌은 자신의 돌로 만들 수 있다.

(여기에서 "사이"란 가로/세로/대각선을 의미한다.)

(2, 3) 위치에 흑돌을 놓은 후의 보드는 다음과 같다.

이런 식으로 번갈아가며 흑, 백 플레이어가 돌을 놓는다.

만약 돌을 놓을 곳이 없다면 상대편 플레이어가 다시 돌을 놓는다.

보드에 빈 곳이 없거나 양 플레이어 모두 돌을 놓을 곳이 없으면 게임이 끝나고 그 때 보드에 있는 돌의 개수가 많은 플레이어가 승리하게 된다.

 

풀이방법

DFS(깊이 우선 탐색) 알고리즘을 활용해 문제를 해결한다.

 

흑 또는 백의 좌표가 주어질 때마다, 주어진 좌표의 가로, 세로, 대각선에 있는 모든 노드를 탐색해

 

흑에서 백 또는 백에서 흑으로 교체해야할 노드가 있는지 확인하고 있을 경우 교체해준다.

 

교체해야할 노드가 있는 경우란 

 

만약 입력된 돌이 흑이라면 세로, 가로, 대각선으로 돌이 놓여져있는 모든 노드를 탐색하다가 흑인 정점을 만날 경우이다.

 

그럴 경우 사이부분의 모든 백의 돌은 흑이 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_4615 {
	static int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1};
	static int[] dy = {0, 1, 0, -1, -1, 1, 1, -1};
	static int[][] v;
	static int[][] a;
	static int n;
	public static void dfs(int x, int y, int d_x, int d_y, int k, int idx) {
		if(a[x][y] == k) {
			for(int i = 0; i < idx; i++) {
				a[v[i][0]][v[i][1]] = k;
			}
			return;
		}
		v[idx][0] = x;
		v[idx][1] = y;
		
		int nx = x + d_x;
		int ny = y + d_y;
		
		if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
			if(a[nx][ny] != 0)
				dfs(nx, ny, d_x, d_y, k, idx+1);
		}
		v[idx][0] = 0;
		v[idx][1] = 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			int m = sc.nextInt();
			a = new int[n][n];
			v = new int[n][2];
			int b = 0;
			int w = 0;
			
			a[n/2][n/2] = 2;
			a[n/2-1][n/2-1] = 2;
			a[n/2-1][n/2] = 1;
			a[n/2][n/2-1] = 1;
			
			for(int i = 0; i < m; i++) {
				int x = sc.nextInt() - 1;
				int y = sc.nextInt() - 1;
				int k = sc.nextInt();
				
				a[x][y] = k;
				
				for(int j = 0; j < 8; j++) {
					int nx = x + dx[j];
					int ny = y + dy[j];
					if(nx >= 0 && ny >= 0 && nx < n && ny < n && a[nx][ny] != 0) {
						dfs(nx, ny, dx[j], dy[j], k, 0);
					}
				}
			}
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(a[i][j] == 1)
						b++;
					if(a[i][j] == 2)
						w++;
					
				}
			}
			System.out.println("#" + t + " " + b + " " + w);
		}
	}
}