[백준] 2615 오목 java 풀이

1. 문제 설명 📌

(1) 링크🔗

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

(2) 해설🕵

주의해야할 점

• 1️⃣ 바둑알이 가로 세로 혹은 대각선으로 동시에 6개 이상 9개 이하로 놔두는 곳도 있다.
  (이 경우, 문제의 승리 조건인 '5개가 연속되어서 놓아졌다.' 를 위배하기에 답이 아니다.)
• 2️⃣ 재귀가 바둑판을 벗어나는 순간을 감지해서 오류를 방지해야 한다.

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: 재귀, SIMULATION

해당 문제는 진짜 오목을 두듯이, 흰색 혹은 검은색 바둑알이 나온 시점부터, 가로, 세로, 대각선으로 5개가 연속되는지 확인해주면 되는 문제이다.

ⓐ 구해야할 방면 정하기

그럼 8방면을 다 구해야 할까? 아니다. 그 절반만 구하면 된다. 우리는 왼쪽 상단[0,0]부터 오른쪽 하단[18,18]까지 차레로 계산할 것임으로, (우측 상단 대각), (우측 가로), (우측 하단 대각), (하단 세로) 4가지만 확인해주면 된다. 왜냐하면 이렇게 계산한다면, 이전에 계산했던 해당 4방면이 어떤 시점의 바둑알에겐 (좌측 하단 대각), (좌측 가로), (좌측 상단 대각), (상단 세로)가 될 것이기 떄문이다.

ⓑ 바둑알을 확인하며 주의할 점

해당 문제는 구현이 엄청 어렵다기 보단, 생각해야할 테스트 케이스가 많아서 까다롭다.

• 1️⃣ 5개의 바둑알을 확인할 때, 현재 보고 있는 좌표가 바둑판을 벗어나는지 확인 (OOB Error 방지)
• 2️⃣ 6번째 바둑알도 연속되는지 확인 (이건 이기는 조건이 아니기에 넘어가야함)
• 3️⃣ 제일 첫 번째로 보는 바둑이 현재 확인하려는 직선, 대각선의 연속 도중에 있는 바둑인지 확인

   (예를 들어, (5,0),(4,1), (3,2), (2,3),(1,4),(0,5)는 6개가 연속하는 점이라서 안되는 경우이다. 하지만 우리는 좌 상단부터 확인하다 보니 **(4,1)을 먼저 만나게 되고, 5개가 연속된다고 답을 내놓게 된다.** 따라서 이를 방지해야 한다.)

• 4️⃣ 2번의 경우처럼 바둑알이 6개 이상 연속되는 경우는 해당 바둑알을 그대로 놔둘 경우, 3번 처럼 다음 계산에 혼선을 주므로 전부 제거한다.

(2) SUDO CODE 📜

• 0️⃣ 바둑알 받기
• 1️⃣ 검은알 혹은 흰 알을 만나면 (우측 상단 대각), (우측 가로), (우측 하단 대각), (하단 세로)을 각각 확인하기 (재귀)
• 2️⃣ 현재 확인하려는 좌표가 바둑판을 벗어나는지 확인
• 3️⃣ 현재 확인하려는 연속이 6개 이상인지 확인 (6개 이상이면 해당 연속된 바둑알 지우기)
• 4️⃣ 현재 확인하려는 연속의 첫 번째 바둑알이 다른 연속의 도중 값인지 확인 (이건 우측 상단 대각을 확인할 때만 확인하면 된다. 왜냐하면, 우리는 좌상단 부터 값들을 확인하기 떄문에 나머지 3가지 경우, 연속의 도중 값보다 연속의 시작점을 먼저 만나기 때문이다.)

(3) 시간복잡도 분석 🕓

$O(19^{2}*4*5)$

19*19 바둑판에서 하나의 바둑알 당 (우상대각, 가로, 세로, 우하대각)을 최대 5번씩 확인해야함.

3. 구현 코드 🔎

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


public class Main {
    static int [][][] boards = new int [5][19][19]; // 0 - 원본, 1 - 가로, 2 - 세로, 3 - 우밑 대각, 4 - 우상 대각
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 19; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            for (int j = 0; j < 19; j++) {
                boards[0][i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 19; j++) {
                System.arraycopy(boards[0][j],0, boards[i][j], 0, 19);
            }
        }
        int ans = 0;
        int ans_x = 0; int ans_y = 0;
        for (int i = 0; i < 19; i++) {
            for (int j = 0; j < 19; j++) {
                if(boards[0][i][j] == 1 || boards[0][i][j] == 2){
                    int stone_num = boards[0][i][j];
                    if(horizontal(i,j,0,stone_num) || vertical(i,j,0,stone_num)
                        || diagonal_row(i,j,0,stone_num) || diagonal_high(i,j,0,stone_num)){
                        ans = stone_num; ans_x = i+1; ans_y = j+1;
                    }
                }
            }
        }
        System.out.println(ans + (ans != 0? ("\n"+ans_x+" "+ans_y) : ""));

    }

    public static boolean horizontal(int x, int y, int depth, int stone_num){
        if(depth == 5){
            if(OOB(x,y)) return true;
            else if(boards[1][x][y] != stone_num) return true;
            else Arrays.fill(boards[1][x], -1);
            return false;
        }

        if(OOB(x,y)) return false;
        else if(boards[1][x][y] == stone_num) return horizontal(x,y+1, depth+1, stone_num);
        else return false;
    }

    //---------------------------------------------------------------------------------------

    public static boolean vertical(int x, int y, int depth, int stone_num){
        if(depth == 5){
            if(OOB(x,y)) return true;
            else if(boards[2][x][y] != stone_num) return true;
            else for (int i = 0; i < 19; i++) boards[2][i][y] = -1;
            return false;
        }

        if(OOB(x,y)) return false;
        else if(boards[2][x][y] == stone_num) return vertical(x+1,y, depth+1, stone_num);
        else return false;
    }

    // ---------------------------------------------------------------------------------

    public static boolean diagonal_row(int x, int y, int depth, int stone_num){
        if(depth == 5){
            if(OOB(x,y)) return true;
            else if(boards[3][x][y] != stone_num) return true;
            else {
                for (int i = 0; i < 6; i++) boards[3][x-i][y-i] = -1;
                return false;
            }
        }

        if(OOB(x,y)) return false;
        else if(boards[3][x][y] == stone_num) return diagonal_row(x+1,y+1, depth+1, stone_num);
        else return false;
    }

    // ---------------------------------------------------------------------------------

    public static boolean diagonal_high(int x, int y, int depth, int stone_num){
        if(depth == 0 && !OOB(x+1, y-1) && boards[4][x+1][y-1] == stone_num) return false;
        if(depth == 5){
            if(OOB(x,y)) return true;
            else if(boards[4][x][y] != stone_num) return true;
            else {
                for (int i = 0; i < 6; i++) boards[4][x+i][y-i] = -1;
                return false;
            }
        }

        if(OOB(x,y)) return false;
        else if(boards[4][x][y] == stone_num) return diagonal_high(x-1,y+1, depth+1, stone_num);
        else return false;
    }

    public static boolean OOB (int x, int y){
        return (x < 0 || y < 0 || x > 18 || y > 18);
    }
    /*
     * 범위 벗어나느지 확인
     * 기저 조건
     *    1. depth = 5번째 바둑알이 존재하고 그 바둑알 번호가 현재랑 같다. false 반환
     *        1에서 사용된 바둑 모두 -1로 바꾸어 사용 표시 남기기
     *    2. depth = 5번째 바둑알이 존재하지 않는다. true 반환
     * 계산
     *    1. 한칸씩 전진헤기먀 비득일 같은지 확인
     * */
}

4. 배운 것들 🎯

해당 문제는 SSAFY 첫 번째 시험에서 나온 것 같은데, 거진 1년 반만에 다시 풀어서 맞췄다... 참 세월이 무상하고, 하루하루 적극적으로 살아야겠다는 감회가 교차했다.

코드에 대해서도 방향 배열을 쓰면 4개의 함수를 하나로 줄여 더 깔끔하게 풀 수 있을 듯 싶다. 또한 굳이 재귀를 쓰기 보단 5개 밖에 안되고, 방향도 도중에 바뀌지 않으므로, 반복문을 써도 더 깔끔했을 것 같다. 다음에 풀게 되면, 한 번 그렇게 바꿔봐야 겠다.