백준 16955 자바 - 오목, 이길 수 있을까? (boj 16955 java)

문제 : boj16955

 

 

  '.'인 곳 중 한 곳을 'X'로 바꾸었을 때, 'X'가 가로, 세로 혹은 대각선으로 연속으로 5개 이상인지 체크해보면 된다. 10x10의 입력값에서 '.'인 곳 모두를 한번씩 'X'로 바꿔보면서 위의 사항을 체크해보면 된다! 대략 O(10x10x5x4) 정도 될 것으로, 매우 널널하다(10x10은 오목판의 크기, 4는 가로 확인, 세로 확인, '↗'형태의 대각선, '↘' 형태의 대각선이다. 5는 대강 5 이상 됬으면 답일테니 5 미만으로만 갈테니 5이다 ㅋㅋ)

 

  이 때 매번 전체 오목판을 모두 확인하면서 5개가 연속인지 확인하면 비효율적이다. 그러니 현재 '.'을 'X'로 변경한 위치부터 다음과 같이 가로, 세로, 대각선을 각각 확인하면 된다.

 

위의 경우 가로로는 4개, 세로로는 3개, 대각선↗은 4개, 대각선↘은 5개로 '1'을 출력하면 된다. 위와 같은 방식을 모든 '.'이 있는 위치에서 수행하면 답을 구할 수 있다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    char[][] arr;

    private boolean chk(int r, int c) {
        // horizon chk
        int cnt = 0;
        for (int i = c-1; i >= 0 && arr[r][i] == 'X'; i--) cnt++;
        for (int i = c+1; i < 10 && arr[r][i] == 'X'; i++) cnt++;
        if (cnt >= 4) return true;

        // vertical chk
        cnt = 0;
        for (int i = r-1; i >= 0 && arr[i][c] == 'X'; i--) cnt++;
        for (int i = r+1; i < 10 && arr[i][c] == 'X'; i++) cnt++;
        if (cnt >= 4) return true;

        // '/' diagonal chk
        cnt = 0;
        for (int i = r+1, j = c-1; i<10&&j>=0 && arr[i][j] == 'X'; i++, j--) cnt++;
        for (int i = r-1, j = c+1; i>=0&&j<10 && arr[i][j] == 'X'; i--, j++) cnt++;
        if (cnt >= 4) return true;

        // '\' diagonal chk
        cnt = 0;
        for (int i = r+1, j = c+1; i<10&&j<10 && arr[i][j] == 'X'; i++, j++) cnt++;
        for (int i = r-1, j = c-1; i>=0&&j>=0 && arr[i][j] == 'X'; i--, j--) cnt++;
        if (cnt >= 4) return true;

        return false;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new char[10][10];
        for (int i = 0; i < 10; i++) {
            String s = br.readLine();
            for (int j = 0; j < 10; j++) {
                arr[i][j] = s.charAt(j);
            }
        }
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (arr[i][j] != '.') continue;
                if (chk(i, j)) {
                    System.out.println(1);
                    return;
                }
            }
        }
        System.out.println(0);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}