[BOJ] 2615.오목 (Java)

 

2615번: 오목

 

바둑판에 19개의 가로줄과 19개의 세로줄이 그려져 있을 때, 같은 색의 바둑알이 연속적으로 다섯 알 놓이면 이기게 되는 게임입니다.

여기서 연속적으로는 가로, 세로 또는 대각선 방향을 뜻하며, 여섯 알 이상이 연속적으로 놓은 경우에는 이긴 것이 아닙니다.

바둑판 상태가 주어졌을 때, 검은색은 1, 흰색은 2, 알이 놓이지 않은 자리는 0으로 표시합니다.

검은색이 이기면 1, 흰색이 이기면 2, 아직 승부가 결정되지 않으면 0을 출력합니다.

그리고 검은색 또는 흰색이 이겼을 경우, 둘째 줄에 연속된 다섯 개의 바둑알 중 가장 왼쪽에 있는 바둑알의 가로줄, 세로줄 번호를 순서대로 출력합니다. 연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 바둑알의 가로줄, 세로줄 번호를 순서대로 출력합니다.

 

문제 요약

1. 가로, 세로 또는 대각선 방향으로 바둑알이 연속적으로 다섯 개가 놓이는 경우 찾기

2. 여섯 알 이상이 연속적으로 놓이는 경우 이긴 것이 아님

3. 검은색이 이기면 1, 흰색이 이기면 2, 아직 승부가 결정되지 않으면 0 출력

4. 연속된 다섯 개 바둑알 중 가장 왼쪽에 있는 바둑알 위치 출력 (세로로 놓이면, 가장 위쪽 바둑알 위치 출력)

 

문제 풀이

처음 바둑판의 상태를 불러올 때, 검은색 바둑알의 위치와 흰색 바둑알의 위치를 리스트에 저장해둡니다.

그리고 검은색 바둑알 위치 리스트와 흰색 바둑알 위치 리스트를 순서대로 확인하며 다섯 알이 연속적으로 놓이는지 확인합니다.

여기서 저는 다섯알이 놓인 상태일 때, 출발한 위치 앞쪽에 바둑알이 있는지 확인하여 6개 이상이 되는지 확인했습니다.

출발 위치와 출발 위치 앞쪽에 대한 이미지

 

import java.util.*;

class Position {
    int row;
    int col;

    Position(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {
    public static List<Position> solution(int[][] board, List<Position> positions, int color) {
        int[][] direction = {{0, 1}, {1, -1}, {1, 0}, {1, 1}};
        int[][] checkDirection = {{0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
        int count;
        boolean isBreak = false;
        boolean isExistence;
        List<Position> winPosition = null;

        Queue<Position> queue = new LinkedList<>();

        for (Position position : positions) {
            if (isBreak) break;

            for (int i = 0; i < 4; i++) {
                winPosition = new ArrayList<>();
                queue.add(position);
                count = 0;

                while (!queue.isEmpty()) {
                    Position pos = queue.poll();
                    winPosition.add(new Position(pos.row, pos.col));
                    count++;

                    int nextRow = pos.row + direction[i][0];
                    int nextCol = pos.col + direction[i][1];

                    if (0 <= nextRow && nextRow < 19 && 0 <= nextCol && nextCol < 19) {
                        if (board[nextRow][nextCol] == color) {
                            queue.add(new Position(nextRow, nextCol));
                        }
                    }
                }

                if (count == 5) {
                    int checkRow = position.row + checkDirection[i][0];
                    int checkCol = position.col + checkDirection[i][1];

                    isExistence = false;

                    // 오목이 된 시작점 앞에 돌이 있는지 확인하여 육목 이상인지 체크
                    if (0 <= checkRow && checkRow < 19 && 0 <= checkCol && checkCol < 19) {
                        if (board[checkRow][checkCol] == color) {
                            isExistence = true;
                        }
                    }

                    if (!isExistence) {
                        isBreak = true;
                        break;
                    }
                }
            }

        }

        return winPosition;

    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int[][] board = new int[19][19];
        List<Position> blackPos = new ArrayList<>();
        List<Position> whitePos = new ArrayList<>();

        for (int i = 0; i < 19; i++) {
            for (int j = 0; j < 19; j++) {
                int temp = input.nextInt();
                board[i][j] = temp;
                if (temp == 1) {
                    blackPos.add(new Position(i, j));
                } else if (temp == 2) {
                    whitePos.add(new Position(i, j));
                }
            }
        }

        List<Position> blackWinPosition = solution(board, blackPos, 1);
        List<Position> whiteWinPosition = solution(board, whitePos, 2);

        if (blackWinPosition != null && blackWinPosition.size() == 5) {
            System.out.println(1);
            blackWinPosition.sort(((o1, o2) -> o1.col - o2.col));
            System.out.println((blackWinPosition.get(0).row + 1) + " " + (blackWinPosition.get(0).col + 1));
        } else if (whiteWinPosition != null && whiteWinPosition.size() == 5) {
            System.out.println(2);
            whiteWinPosition.sort(((o1, o2) -> o1.col - o2.col));
            System.out.println((whiteWinPosition.get(0).row + 1) + " " + (whiteWinPosition.get(0).col + 1));
        } else {
            System.out.println(0);
        }
    }
}