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

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

접근 방법

8 방향으로 백트래킹을 했다.

내 돌을 놓을 때마다 그 수의 8 방향에 상대 돌이 있는지 마지막은 내 돌인지 확인해야 했다.

내가 이해한 바로는 한 곳 이상은 내 돌과 내 돌 사이에 빈틈없이 상대 돌이 있다는 거였다.

그러므로 도중 리턴을 해야 하는 경우는

(1) 위치 인덱스가 초과한 경우

(2) 해당 위치가 빈 경우

(3) 해당 위치가 내 돌인 경우 이다. 3번의 경우 check(ck)를 유효화했다. 이후 지나온 자리를 내 돌로 교체해 준다.

해당 위치가 상대 돌인 경우에는 이후에도 여러 개 존재할 수 있으므로 check(ck)를 무효화하고 재귀했다.

 

소스 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int N;
    static int[] cnt;
    static int[][] map;
    static int ck;
    static int[] dx = {1, 1, 0, -1, -1, -1,  0, 1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
         
        for(int tc=1; tc<=T; tc++) {
            ck = 0;
            cnt = new int[2];
            Arrays.fill(cnt, 2);
            N = sc.nextInt();
            map = new int[N][N];
            map[N/2-1][N/2-1] = 2; // w
            map[N/2-1][N/2] = 1; // b
            map[N/2][N/2-1] = 1; // b
            map[N/2][N/2] = 2; // w
             
            int M = sc.nextInt();
            for(int i=0; i<M; i++) {
                int x = sc.nextInt()-1;
                int y = sc.nextInt()-1;
                int d = sc.nextInt();
                 
                map[x][y] = d;
                cnt[d-1] += 1;
                 
                for(int j=0; j<8; j++) {
                    back(x + dx[j], y + dy[j], dx[j], dy[j], d);
                }
            }
             
            System.out.println("#" + tc + " " + cnt[0] + " " + cnt[1]);
        }
    }
    static void back(int x, int y, int xx, int yy, int dd) {
        if (N-1 < x || N-1 < y || x < 0 || y < 0)
            return;
        if (map[x][y] == 0 || (map[x][y] == dd && map[x-xx][y-yy] == map[x][y]))
            return;
        if (map[x][y] == dd) {
            ck = 1;
            return;
        }
        if (map[x][y] != dd) {
            ck = 0;
            back(x+xx, y+yy, xx, yy, dd);
            if (ck == 1) {
                cnt[map[x][y]-1] -= 1;
                map[x][y] = dd;
                cnt[dd-1] += 1;
            }
        }
    }
}