[JAVA][SWEA] 재미있는 오셀로 게임 (히든 테케, 오류 관련)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQmA4uK8ygDFAXj 

SW Expert Academy

문제의 출처는 위의 사이트에 있습니다.

1. 문제

누구나 해봤을법한 오셀로게임. 필자는 예전에 쥬니어네이버 게임랜드에서 해본듯하다...

 

 [입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 보드의 한 변의 길이 N과 플레이어가 돌을 놓는 횟수 M이 주어진다. N은 4, 6, 8 중 하나이다.

그 다음 M줄에는 돌을 놓을 위치와 돌의 색이 주어진다.

돌의 색이 1이면 흑돌, 2이면 백돌이다.

만약 3 2 1이 입력된다면 (3, 2) 위치에 흑돌을 놓는 것을 의미한다.

돌을 놓을 수 없는 곳은 입력으로 주어지지 않는다.

 [출력]

각 테스트 케이스마다 게임이 끝난 후 보드 위의 흑돌, 백돌의 개수를 출력한다.

흑돌이 30개, 백돌이 34인 경우 30 34를 출력한다.

 

2. 재미있는 오셀로 게임 히든 테케, 오류 관련 포인트

함정 포인트는 크게 4가지 인듯하다.

 1. 가로의 칸, 세로의 칸의 형태로 입력을 주기 때문에 첫번째 입력값을 열에, 두번째 입력값을 행에 넣어줘야함.

 2. 알과 알 사이에 여러 개의 알이 오는 경우도 고려해야함. 예를들어 ●○○○●가 있을때에도 검은돌로 싹 바뀐다.

 3. 입력으로 주어지는 모든 케이스를 계산하고 마지막단계에서 흰돌과 검은돌을 count 할 때 (N*N-흰돌)로 검은돌을 계산.      하면 다친다. 무조건 흰 돌, 검은돌을 같이 카운트 해줄 것. 알고리즘 문제를 풀다보면 이렇게 숫자를 세주어 답을 도출해야.   하는 것들이 있는데 이럴 때 한쪽을 count 하고 나머지는 전체값에서 빼주는 방법을 사용하게 되면 히든테케에서 걸리는 경우가 많으니 컴퓨터에게 일 조금 더 시킨다고 생각하고 그냥 따로! 각각! 꼭! 계산할 것!

 4. 중간에 0이 껴있는 경우를 주의할 것!  ●○0● 이런 케이스는 어떤 것도 바뀌지 않고 그대로라는 사실! 기억하기!

 

3.  DFS로 풀기 

코드1. 아주 난잡하게 작성함. 

배열을 [N+1][N+1]로 했기 때문에 배열의 index를 넘어가지는 않았는지 파악해주야 했음. 그래서 DFS가 더러워졌음.

이부분을 개선하기 위해 코드2에서는 [N+2][N+2] 배열을 만듦.

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

public class Solution {
    static int N,M;
    static int[][] map;
    static int[] dx={-1,1,0,0,-1,-1,1,1};
    static int[] dy={0,0,-1,1,-1,1,-1,1};
    static boolean flag=false;
    static int black;
    static int white;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T=Integer.parseInt(st.nextToken());
        for (int tc = 1; tc <=T ; tc++) {
            st = new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            M=Integer.parseInt(st.nextToken());
            map=new int[N+1][N+1];
            map[N/2][N/2]=2;
            map[N/2][N/2+1]=1;
            map[N/2+1][N/2]=1;
            map[N/2+1][N/2+1]=2;
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int C = Integer.parseInt(st.nextToken());
                int R = Integer.parseInt(st.nextToken());
                map[R][C] = Integer.parseInt(st.nextToken());

                for (int j = 0; j < 8; j++) {
                    flag=false;
                    int xx=R+dx[j];
                    int yy=C+dy[j];
                    if(0<xx&&xx<N+1&&0<yy&&yy<N+1&&map[xx][yy]>0)
                         dfs(j, xx, yy, map[R][C]);
                }
            }
                black =0;
            white=0;
                for (int[] a:map){
                    for(int b:a){
                        if(b==1){
                        black++;
                        }
                        else if(b==2){
                            white++;
                        }
                        
                    }
                }
                System.out.printf("#%d %d %d\n",tc,black, white);
            }
    }
    private static void dfs(int j,int r, int c,int stone) {
        if(map[r][c]==stone){
            flag=true;
            map[r][c]=stone;
            return;
        }
        int xx=r+dx[j];
        int yy=c+dy[j];
        if(0<xx&&xx<N+1&&0<yy&&yy<N+1&&map[xx][yy]>0){
            dfs(j,xx,yy,stone);
        }
        if(flag==true){
            map[r][c]=stone;
        }
    }
}

 

 코드2.  [N+2][N+2] 배열로 선언하여 오셀로판의 주변이 0으로 둘러쌓임. 그렇기 때문에 0인지 아닌지만 판단해주면 되고, 배열의 값이 index를 넘어가는지 판단해주지 않아도 됨. 0을 만나면 return 되므로.

flag를 설정하여 flag가 참일때, 즉 자신과 같은 값을 찾았을때만 돌맹이를 바꿔주는 코드를 구현함.

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


public class Solution{
    static int N, M;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
    static boolean flag = false;
    static int black;
    static int white;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            map = new int[N + 2][N + 2];
            map[N / 2][N / 2] = 2;
            map[N / 2][N / 2 + 1] = 1;
            map[N / 2 + 1][N / 2] = 1;
            map[N / 2 + 1][N / 2 + 1] = 2;
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int C = Integer.parseInt(st.nextToken());
                int R = Integer.parseInt(st.nextToken());
                map[R][C] = Integer.parseInt(st.nextToken());

                for (int j = 0; j < 8; j++) {
                    flag = false;
                    dfs(j, R + dx[j], C + dy[j], map[R][C]);
                }
            }
            black = 0;
            white=0;
            for (int[] a : map) {
                for (int b : a) {
                    if (b == 1) {
                        black++;
                    }else if(b==2){
                        white++;
                    }
                }
            }
            System.out.printf("#%d %d %d", tc, black, white);
            System.out.println();
        }
    }

    private static void dfs(int j, int r, int c, int stone) {
        if(map[r][c]==0) return;
        if (map[r][c] == stone) {
            flag = true;
            return;
        }
        dfs(j, r + dx[j], c + dy[j], stone);

        if (flag) {
            map[r][c] = stone;
        }
    }
}