코드트리 - 구현, 완전탐색, 최적화

문제 링크 

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-O-mok/description

오목 설명 | 코드트리

import java.util.*;
import java.io.*;

/*
시작 돌 하나를 잡고 오른쪽, 아래쪽, 대각선 우상, 대각선 좌상
*/

public class Main {
    static int[][] board = new int[19][19];
    static int N = 19;
    static int[] di = {0,1,-1,-1};
    static int[] dj = {1,0,1,-1};
   
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        boolean found = false;
        StringBuilder sb = new StringBuilder();

        outer:
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                if(board[i][j] == 0)
                    continue;
                int curType = board[i][j];

                for(int d = 0; d<4; d++){
                    // 중복된 검사를 피하기 위해 
                    // 지금 방향 기준 한칸 전을 검사함
                    int pi = i - di[d];
                    int pj = j - dj[d];
                    // 인덱스 문제 없고 같은 색이면 중복되니까 안함
                    if(pi >= 0 && pj >= 0 && pi < N && pj < N && board[pi][pj] == curType)
                        continue;
                    
                    int cnt = 1;
                    int ni = i;
                    int nj = j;
                    while(true){
                        ni = ni + di[d];
                        nj = nj + dj[d];
                        if(ni < 0 || nj < 0 || ni >=N || nj >= N)
                            break;
                        if(board[ni][nj] != curType)
                            break;
                        cnt++;
                    }
                    if(cnt == 5){
                        found = true;
                        sb.append(curType).append("\n");
                        // 시작점이 i,j니까 그걸로 출력
                        sb.append(i + 2*di[d] + 1).append(" ").append(j + 2*dj[d] +1);
                        break outer;
                    }
                }
            }
        }
        if(!found)
            System.out.print(0);
        else
            System.out.print(sb);
    }
}

 

정리

19 x 19 크기의 오목판이 있을때 연속된 5개의 돌 종류와 승리 조건이 만족됬을때 가운데 돌의 좌표를 출력하고

만약 승리한 사람이 없을땐 그냥 0 출력하는 문제 

입력은 0 : 빈칸, 1 : 검은돌, 2 : 흰돌

 

풀이

1) 탐색 방향은 오른쪽, 아래쪽, 우상, 좌상 방향 4가지만 보면 되고 풀이처럼 8개를 다 볼 필요가 없다.

2) 중복을 제거하기 위해 각 방향마다 바로 전칸이 만약 같은 타입이면 또 탐색을 한게 되기 때문에 제외함

3) break 'alias' 구문으로 바로 빠져나감