BOJ 2615 오목 Java

알고리즘 공부 - 완전탐색

문제 보기

정답 코드 (228ms)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Problem2615 {

    private static final int BOARD_SIZE = 19;
    private static final char EMPTY = '0';
    private static final char BLACK = '1';
    private static final char WHITE = '2';
    private static final int X = 0;
    private static final int Y = 1;
    private static final int WINNING_COUNT = 5;

    private static char[][] readInput() {
        char[][] board = new char[BOARD_SIZE][BOARD_SIZE];
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
            for (int i = 0; i < BOARD_SIZE; i++) {
                String input = br.readLine();
                for (int j = 0, cidx = 0; j < BOARD_SIZE; cidx += 2, j++)
                    board[i][j] = input.charAt(cidx);
            } 
        } catch (Exception ioe) {  }

        return board;
    }

    public static void main(String[] args) {
        char[][] board = readInput();
        List<List<Integer>> linkedPositions = findLinkedStones(board);
        printGameResult(linkedPositions, board);
    }

    /**
     * 연결된 돌이 없으면 size() == 0인 리스트 반환.
     */
    private static List<List<Integer>> findLinkedStones(char[][] board) {

        for (int i = 0; i < BOARD_SIZE; i++)
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == EMPTY)
                    continue;
                List<List<Integer>> tmp = linkedPositionsFrom(i, j, board);
                if (tmp.size() == WINNING_COUNT)
                    return tmp;
            }
                
        return new ArrayList<>(WINNING_COUNT);
    }

    private static List<List<Integer>> linkedPositionsFrom(int i, int j, char[][] board) {
        List<List<Integer>> positions = new ArrayList<>(WINNING_COUNT);
        char color = board[i][j];
        // 하 우하 우 우상
        int[][] direction = {\{1, 0}, {1, 1}, {0, 1}, {-1, 1}\};
        for (int d = 0; d < direction.length; d++) {
            positions.clear();
            positions.add(Arrays.asList(i, j));
            // 순방향
            int x = i + direction[d][X];
            int y = j + direction[d][Y];
            while (x >= 0 && x < BOARD_SIZE &&
                y >= 0 && y < BOARD_SIZE && board[x][y] == color) {
                positions.add(Arrays.asList(x, y));
                x += direction[d][X];
                y += direction[d][Y];
            }
            // 반대방향
            x = i - direction[d][X];
            y = j - direction[d][Y];
            while (x >= 0 && x < BOARD_SIZE &&
                y >= 0 && y < BOARD_SIZE && board[x][y] == color) {
                positions.add(Arrays.asList(x, y));
                x -= direction[d][X];
                y -= direction[d][Y];
            }
            System.out.println(String.format("(%d, %d) 방향: %d 길이: %d" + positions, i+1, j+1, d+1, positions.size()));
            if (positions.size() == WINNING_COUNT)
                return positions;
        }
        positions.clear();
        return positions;
    }

    private static int printGameResult(List<List<Integer>> positions, char[][] board) {
        if (positions.size() == 0) {
            System.out.println(0);
            return 0;
        }
        // 세로 방향
        if (positions.get(0).get(Y) - positions.get(1).get(Y) == 0)
            positions.sort((o1, o2) -> o1.get(X) - o2.get(X));
        // 대각선 방향
        else
            positions.sort((o1, o2) -> o1.get(Y) - o2.get(Y));
        System.out.println(board[positions.get(0).get(X)][positions.get(0).get(Y)]);
        System.out.println((positions.get(0).get(X) + 1) + " " + (positions.get(0).get(Y) + 1));
        return 0;
    }
}