Sw expert 11315. 오목 판정 D3 - dfs

 

● ○ ● ● ● .. ㅎㅎ 제성함다

 

 

대각선을 포함하여 연달아 5개가 되는지 판단해주면 된다.

대각선이 포인트다.

대각선을 어떻게 나타낼까

예시

public static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
public static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };

 

늘쓰던 요놈이죠 뭐. 상하좌우에서 대각선도 추가해줍니다.

 

dfs()에 d 를 통해서 방향을 지정해주었다.

연속적인게 5개라면 오목 가능 return.

 

import java.util.*;
 
public class Solution { // 11315. 오목 판정 D3 
    public static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
    public static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };
    public static char[][] arr;
    public static int N;
    public static String answer;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            arr = new char[N][N];
            for (int i = 0; i < N; i++) {
                String s = sc.next();
                for (int j = 0; j < N; j++) {
                    arr[i][j] = s.charAt(j);
                }
            }
            answer = "NO";
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (arr[i][j] == 'o') {
                        dfs(i, j, 9, 1);
                    }
                }
            }
 
            StringBuilder sb = new StringBuilder();
 
            sb.append("#" + tc);
            sb.append(" " + answer);
            System.out.println(sb);
 
        } // tc
    }
 
    public static void dfs(int r, int c, int d, int cnt) {
        if (cnt == 5) {
            answer = "YES";
            return;
        }
        if (d == 9) {
            for (int k = 0; k < 8; k++) {
                int next_r = r + dr[k];
                int next_c = c + dc[k];
                if (!rangechk(next_r,next_c))
                    continue;
                if (arr[next_r][next_c] != 'o')
                    continue;
                dfs(next_r, next_c, k, cnt + 1);
            }
        } else {
            int next_r = r + dr[d];
            int next_c = c + dc[d];
            if (rangechk(next_r,next_c))
                if (arr[next_r][next_c] == 'o')
                    dfs(next_r, next_c, d, cnt + 1);
        }
    }
 
    public static boolean rangechk(int r, int c) {
        return (r >= 0 && c >= 0 && r < N && c < N);
    }
 
}
 

 

dfs 안에 중복되는 함수로 보일텐데

시작점 때문에 넣어줬습니다.

방향을 정하지 않은 상태에서 방향을 정하려고 d에 9 값을 넣어주었고, 이후로는 k 0~8 방향을 탐색.