백준 7682 (틱택토) - java

https://www.acmicpc.net/problem/7682

7682번: 틱택토

백트랙킹 문제입니다. 규칙을 찾아서 푸신 분도 많던데... 백트랙킹 풀이를 올리겠습니다.

틱택토가 종료되는 조건 : (가로 한줄 or 세로 한줄 or 대각선 한줄이 같은 색깔로 완성된 경우) or 모든 자리에 숫자가 채워진 경우

 

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

public class Main {
    static HashSet<String> result = new HashSet<>();
    static boolean[] visit = new boolean[9];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] arr = new int[9];

        tic(0,arr,1); // 틱택토 실행

        while(true)
        {
            String input = br.readLine();
            if(input.equals("end"))
                break;

            if(result.contains(input))
                bw.write("valid\n");
            else{
                bw.write("invalid\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
    // 가로로 1줄이 완성되는 경우
    static boolean garo(int[] arr)
    {
        if(arr[0]!=0&&arr[1]!=0&&arr[2]!=0)
        {
            if(arr[0]==arr[1]&&arr[1]==arr[2])
            {
                return true;
            }
        }

        if(arr[3]!=0&&arr[4]!=0&&arr[5]!=0)
        {
            if(arr[3]==arr[4]&&arr[4]==arr[5])
                return true;
        }

        if(arr[6]!=0&&arr[7]!=0&&arr[8]!=0)
        {
            if(arr[6]==arr[7]&&arr[7]==arr[8])
                return true;
        }

        return false;
    }

    // 세로로 한줄 완성되는 경우
    static boolean sero(int[] arr)
    {
        if(arr[0]!=0&&arr[3]!=0&&arr[6]!=0)
        {
            if(arr[0]==arr[3]&&arr[3]==arr[6])
                return true;
        }
        if(arr[1]!=0&&arr[4]!=0&&arr[7]!=0)
        {
            if(arr[1]==arr[4]&&arr[4]==arr[7])
                return true;
        }
        if(arr[2]!=0&&arr[5]!=0&&arr[8]!=0)
        {
            if(arr[2]==arr[5]&&arr[5]==arr[8])
                return true;
        }

        return false;
    }
    
    // 대각선으로 한줄이 완성되는 경우
    static boolean cross(int[] arr)
    {
        if(arr[0]!=0&&arr[4]!=0&&arr[8]!=0)
        {
            if(arr[0]==arr[4]&&arr[4]==arr[8])
                return true;
        }
        if(arr[2]!=0&&arr[4]!=0&&arr[6]!=0)
        {
            if(arr[2]==arr[4]&&arr[4]==arr[6])
                return true;
        }

        return false;
    }

    // 백트랙킹 
    static void tic(int k,int[] arr,int who)
    {
        if(garo(arr)||sero(arr)||cross(arr)) // 한줄이 완성된 경우
        {
            result.add(convert(arr));
            return;
        }

        if(k==9) // 모든 자리가 채워진 경우
        {
            result.add(convert(arr));
            return;
        }

        for(int i=0;i<=8;i++)
        {
            if(who==1) // X를 놓아야 하는 경우
            {
                if(!visit[i])
                {
                    visit[i] = true;
                    arr[i] = 1;
                    tic(k+1,arr,2);
                    arr[i] = 0;
                    visit[i] = false;
                }
            }

            else{ // O를 놓아야 하는 경우
                if(!visit[i])
                {
                    visit[i] = true;
                    arr[i] = 2;
                    tic(k+1,arr,1);
                    arr[i] = 0;
                    visit[i] = false;
                }
            }
        }
    }

    // 문자열로 변환
    static String convert(int[] arr)
    {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<=8;i++)
        {
            if(arr[i]==0)
            {
                sb.append('.');
            }

            else if(arr[i]==1)
            {
                sb.append('X');
            }

            else{
                sb.append('O');
            }
        }

        return sb.toString();
    }
}