[boj] 백준 2615 오목 (Java) - 완전탐색

[문제]

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

 

[풀이]

완전 탐색 문제인데..신경써야 할 부분이 몇 가지 존재한다.

 

1. 오목이 완성될 경우, 가장 왼쪽에 있는 돌의 좌표를 출력해야 한다. 이를 위해서 탐색 시 j가 증가하는 순 -> i가 증가하는 순으로 2중 for문을 돌린다. 방향도 기준점이 가장 왼쪽이 되도록 오른쪽, 아래쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선 4 방향으로 정하였다.

2. 육목인 경우를 포함해서는 안된다! 따라서 반대 방향에 대해서도 탐색을 진행해서 cnt를 증가시켜 준 후 오목인지 비교해야 한다. 그렇지 않으면 한쪽 방향으로 오목이 완성되어 정답으로 출력할 수 있다...코테에서 히든테케였으면 오백퍼 걸렸을 것 같은 함정..ㅎ

 

[코드]

 

package 브루트포스;

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

public class boj_2615_오목 {
    static int[][] board;
    static int[] dr = {0, 1, -1, 1}; //오, 아, 위대각선, 아래대각선
    static int[] dc = {1, 0, 1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        board = new int[19][19];
        for(int i=0; i<19; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<19; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        
        //검 1, 흰 2	
		for (int j = 0; j < 19; j++) {
			for (int i = 0; i < 19; i++) {
				if(board[i][j]==0) continue;

					for (int d = 0; d < 4; d++) {
						int nr = i;
						int nc = j; 
						int cnt = 1; 
						
						//오른쪽 방향 탐색
						while(true) {
							nr += dr[d];
							nc += dc[d];
                            if(nr<0 || nc<0 || nr>=19 || nc>=19) break;

							if(board[i][j]==board[nr][nc]) cnt++;
                            else break;
						}

						nr = i;
						nc = j;
						
						//반대 방향 탐색
						while( true) {
							nr -= dr[d];
							nc -= dc[d];
							if(nr<0 || nc<0 || nr>=19 || nc>=19) break;
								
                            if(board[i][j]==board[nr][nc]) cnt++;
                            else break;			
						}
						
						//오목이라면
						if (cnt==5) {
							System.out.println(board[i][j]);
							System.out.println((i+1) + " " + (j+1));
							return;
						}
						
					}
				}
			}
		
		
		//아무도 이기지 않았을 경우
		System.out.println(0); 	
    }

}