코테 - 오목(2615)

⭐ 문제링크

❤️ 알고리즘

: BruteForce, 재귀함수

📒 접근방법

1. 입력값을 받을 배열을 [21][21]로 설정. 배열 인덱스 초과를 피하기 위함
2. (0,0)인덱스를 기준으로 8가지의 방향을 미리 directionInfo 배열에 저장해둠
   
3. baduk 배열을 따라 돌다 0이 아닌 값을 발견한다면, 설정해둔 방향을 모두 돌 수 있도록 dfs를 실시한다.
4. 모든 방향을 돌았을때, count가 5라면 성공!

🤔 주의할 점

1. 5목이 완성되었을때, 가장 왼쪽의 돌의 위치를 출력해야 한다.
   

2. 6목이상이 나올 경우, 정답으로 간주하지 않고 무시한다.
   -> 해당 조건은 6목의 중간 부분 돌이 현재 바둑돌로 걸릴 경우에도 6목임을 알아야 하기에 코드 내에서 항상 양방향 검사를 진행해줌.

📒 코드

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

public class Main {
    static int [][] baduk = new int[21][21];
    static int directionInfo[][] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
    static int count;
    public static void main(String[] args) throws IOException {
        init();

        for(int i=1; i<20; i++) {
            for(int j=1; j<20; j++) {
                int color = baduk[i][j];
                if(color==0) continue;
                int k;
                for(k=0; k<4; k++) { //방향별로 dfs 탐색
                    count=1; //카운트 초기화
                    if(!dfs(i,j,k)||!dfs(i,j,k+4)) continue; //양방향 동시 검사
                    if(count==5)break;
                }
                if(count==5) {
                    if(k==3) print(i+4,j-4,color);
                    else print(i,j,color);
                    return;
                }
            }
        }
        System.out.println(0);
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for(int i=1; i<20; i++){ //바둑배열 초기화
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1; j<20; j++){
                baduk[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    public static boolean dfs(int row, int col, int direction){
        if(count>5) return false;

        int nextRow = row+directionInfo[direction][0];
        int nextCol = col+directionInfo[direction][1];
        int color = baduk[row][col];

        if(color==baduk[nextRow][nextCol]) {
            count++;
            dfs(nextRow, nextCol, direction);
        }
        return true;
    }

    public static void print(int i, int j, int color){
        System.out.println(color);
        System.out.print(i+" "+j);
    }
}