Q. 4615. 재미있는 오셀로 게임(D3)

Q. 4615. 재미있는 오셀로 게임(D3)

 

0. 문제

 

D3 난이도의 문제이고, 어려운 구현 문제라고 생각된다.

오셀로 게임에 대한 문제이다.처음에 전체 판의 크기가 주어지고, 중앙에 돌 4개는 기본으로 놓여져 있다.이후에 놓는 돌의 색깔과 좌표가 주어지고, 돌을 놓을 때 마다 오셀로의 규칙에 맞춰서 돌의 색깔이 계속 바뀔 때,마지막에 흰색/검정색 돌의 개수를 출력하는 문제이다.

---

1. 풀이

 

다 풀고나서 자꾸 틀리길래 좀 찾아보다 보니.. 좋은 팁을 발견했다.

바둑돌의 색깔이 1 또는 2로 주어지는데, 그렇다면 3에서 내 색깔을 빼면 상대편의 색깔이 나오게 된다.

이를 이용해서 다행히도 맞추게 되었고 아래와 같은 방식으로 풀었다.

좀 복잡해서 함수별로 기능을 최대한 분리해서 풀려고 노력했다.

 

0) dy, dx

for문을 이용해 방향성을 표현하기위해 사용한 배열로

오셀로에서 상대 돌을 판단하기 위해 현재 위치를 제외한 8방향에 대한 방향을 표현한 배열.

 

1) init()

처음 바둑판의 크기가 주어졌을 때 중앙에 흑/백 돌 각각2개씩 놓는다.

 

2) existColor()

바둑돌을 놨을 때 8방향을 보고 상대 돌이 있는 경우 그 뒤에 내 돌이 있는지

dy, dx를 이용해 판별한다.

 

3) change()

2번과 유사하고, 2번 함수에서 만약 내 돌 사이에 상대 돌이 있는 경우에 호출된다.

만약 2번 조건을 만족한 경우 해당 방향에 있는 상대 돌의 색을 모두 변경한다.

 

4) pro()

1 2 3 4번 함수를 모두 호출하는 전체적인 프로세스에 대한 함수이다.

처음 1번 함수를 호출하고,

좌표가 주어졌을 때 바둑돌을 놓는 역할을 하고,

이후 2 3번 함수를 호출한다.

이 때 만약 바둑돌을 둔 위치 근처 8방향중 내 돌이 있는 경우

해당 방향에 대해서는 2번 함수를 호출하지 않는다.

 

5) countColor()

모든 바둑돌의 색깔을 세는 함수이다.

---

아래는 코드이다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

	static BufferedReader br;
	static StringBuffer sb = new StringBuffer();
	static StringTokenizer st;
	static int N, M;
	static int[][] board;
	
	static int[] dy = {0, 1, 0, -1, 1, -1, 1, -1};
	static int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
	
	static int[] colorCnt;
	
	static void input() throws IOException {
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		board = new int[N + 1][N + 1];
	}
	
	static void init() {
    // 처음에 중앙에 흑/백돌을 4개 놓는 함수
		int x = N / 2; 
		board[x][x] = 2; // W
		board[x + 1][x + 1] = 2; // W
		board[x + 1][x] = 1; // B
		board[x][x + 1] = 1; // B
	}
	
	
	static boolean existColor(int y, int x, int dy, int dx, int color) {
		// dy, dx 방향에 하나라도 상대 돌이 있는지 판단하는 함수
		boolean res = false;
		int ny = y;
		int nx = x;
		
		while(true) {
			ny += dy;
			nx += dx;
			if (ny <= 0 || nx <= 0 || ny > N || nx > N) break;

			if (board[ny][nx] == (3 - color)) continue;
			
			if (board[ny][nx] == 0) break;
			if (board[ny][nx] == color) {
				res = true;
				break;
			}
		}
		return res;
	}
	
	static void change(int y, int x, int dy, int dx, int color) {
		// 만약 dy dx 방향에 상대 돌이 있는 경우
        // 모든 상대 돌을 내 돌로 바꾸는 함수
		int ny = y;
		int nx = x;
		while(true) {
			ny += dy;
			nx += dx;
			if (ny <= 0 || nx <= 0 || ny > N || nx > N) {
				break;
			}
			if (board[ny][nx] == (3 - color)) {
				board[ny][nx] = color;
			} else break;
		}
	}
	
	static void countColor() {
		// 마지막에 전체 돌의 수를 구하는 함수
		colorCnt = new int[3];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				colorCnt[board[i][j]]++;
			}
		}
	}
	
	static void pro(int tc) throws Exception{
		
		init();
		while(M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int color = Integer.parseInt(st.nextToken());
			board[y][x] = color;

			for (int i = 0; i < 8; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny <= 0 || nx <= 0 || ny > N || nx > N) continue;
				if (board[ny][nx] == color) continue;
				if (existColor(y, x, dy[i], dx[i], color)) {
					change(y, x, dy[i], dx[i], color);
				}
			}

		}
		countColor();
		sb.append(String.format("#%d %d %d \n", tc, colorCnt[1], colorCnt[2]));
	}
	
	public static void main(String[] args) throws Exception{
		
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
		
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1; tc <= T; tc++) {
			input();
			pro(tc);
		}
        System.out.println(sb);
		
	}

}

---

2. 시간복잡도 계산

 

0) N의 최대값은 8이다.

1) 바둑돌 놓는 좌표의 수 - O(N^2)

2) 풀이 2번 - O(N)

3) 풀이 3번 - O(N)

모든 연산은 연관이 있으므로 세 연산을 곱해줘야 한다.

따라서 시간복잡도는 O(N^4)이고, 최대 4096번 연산이 필요하다.

시간제한은 2초이므로 1초에 약 1억번 연산을 한다고 가정하면, 1초 이내에 풀 수 있다.

---