[Algorithm] 99클럽 코테 스터디 14일차 TIL | 백준_오목(2615번)

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

 

 

---

오늘도.. 시간을 save 하지 못했다..ㅜ

 

오목 문제라 문제 자체를 이해하는 데는 무리 없었지만 이를 구현함에 있어서 여러 고비가 있었다

 

8방향을 모두 검사하려 했으나 어차피 왼쪽 가장 첫 번째 돌만 구하면 되니 

오른쪽 위, 오른쪽, 오른쪽 아래, 아래 방향만 검사한다. 

재귀를 돌릴 때도 같은 방향에서만 돌린다.

 

가장 골치아팠던 문제는 육목 검사였다.

같은 방향에서 길이가 5가 나오면 오목이거나 오목 이상이거나 인데

둘의 차이점은 반대방향에 같은 돌이 있느냐 없느냐이다.

그래서 나는 현재 위치 기준 반대 방향으로 한 칸만 검사해서 해당 돌이 현재 돌과 같은 색이면 육목 처리를 해주었다.

 

이렇게 하고도 25%에서 틀렸다고 나왔는데... 문제를 제대로 읽지 않은 탓이었다.

승부가 나지 않은 경우는 0만 출력해야한다!

 

전체소스

import java.util.*;
import java.io.*;
class Main{
    static int[][] board;
    static int[] dx = {0, 1, 1, -1};
    static int[] dy = {1, 0, 1, 1};
    static int winner;
    static int locationX, locationY;
    public static int whoWin(int x, int y, int len, int dir) {

        int dx_x = x + dx[dir];
        int dy_y = y + dy[dir];

        if(dx_x >= 0 && dy_y >= 0 && dx_x < 19 && dy_y < 19 && board[dx_x][dy_y] == board[x][y]){
            return whoWin(dx_x, dy_y, len+1, dir);
        }
        return len;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        board = new int[19][19];
        for(int i = 0; i < 19; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 19; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 0; i < 19; i++){
            for(int j = 0; j < 19; j++){
                if(board[i][j] > 0 && winner == 0){
                    for(int k = 0; k < 4; k++){
                        if (whoWin(i, j, 1, k) == 5) {
                            // 육목인 경우 무효화
                            if(i-dx[k]>=0 && i-dx[k] < 19 && j-dy[k]>=0 && j-dy[k] < 19 && board[i][j] == board[i-dx[k]][j-dy[k]]){
                                continue;
                            }
                            winner = board[i][j];
                            locationX = i + 1;
                            locationY = j + 1;
                        }
                    }

                }
            }
        }
        System.out.println(winner);
        if( winner != 0 ){
            System.out.println(locationX + " " + locationY);
        }
    }
}