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

문제요약

• 흑돌과 백돌중 누가 이겼는지 판별하고 이긴 돌의 맨 왼쪽과 위의 좌표를 출력하는 문제

풀이 방법

• 모든 위치를 순차적으로 탐색해 나가면서 승부가 결정 났는지 완전탐색으로 판별해나감

어려웠던 점

• 처음에는 완전탐색으로 풀릴 만한 간단한 문제인줄 알고 풀었지만 생각보다 처리해야 하는 경우의 수가 많아서 반례를 찾기 어려웠다
• 비효율적인 flag 사용으로 코드의 복잡도를 증가 시켰다

  flag의잘못된 사용
  어느 상태를 만족시킬때 flag값을 변화시킴으로써 기록할때 사용해야 하는데 "오목"문제에서 나는 'flag값이 변화하지 않았으면 어떤 상태를 만족시킨다'라는 방식으로 사용하였다. 이때문에 flag값을 변화시키는 5목을 만족하지 않는 모든 경우에 대한 처리를 해주어야 했고 여기서 논리적인 빈틈이 생겨 문제를 풀기 어려웠었다

풀이코드

/*
 * 문제 : 오목을 누가 이겼는지 판별하기 -> 상,하,좌,우,대각선에서 5개가 연속으로 나타나는 경우 찾기
 * 생각해볼 것 : 
 * 반례 : 6목 확인을 위해 이전돌을 확인하는 과정에서 잘못된 if문과 flag값 세팅으로 반례발생
 * 
 * 문제풀이 : 완전탐색
 * 무엇을 탐색해야 하나? 모든 돌을 차례대로 탐색해나가야 한다.
 * 어떻게 탐색하나? 이긴돌의 가장 왼쪽 위의 돌을 출력 해야 하므로 가장 왼쪽부터 아래방향으로 탐색을 진행한다.
 * 탐색 해야 할 경우는? 모든 돌에 대하여 탐색
 * 각 돌을 탐색하는 방법은? 현재돌의 오른쪽, 아래, 대각선 탐색
 *  현재돌을 포함해 5번째 까지는 같은 돌이어야함, 6번째는 같지 않아야함
 *  또한 현재돌의 이전돌이 현재돌과 같지 않아야함
 * 
 */

 import java.util.*;
 import java.io.*;
public class Main {
    static int[][] arr;
    static int[][] Case = {{0,1}, {1,0}, {1,1}, {1,-1}};
    public static void main(String[] args) throws Exception{
        //입력받기
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        arr = new int[19][19];
        for(int i = 0; i<19; i++){
            st = new StringTokenizer(in.readLine());
            for(int j=0; j<19; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //반복문 : 모든 돌에 대한 탐색
        boolean result = false;
        Loop1:
        for(int i=0; i<19; i++){
            for(int j=0; j<19; j++){
                //만약 현재 놓여진 돌이 없거나 승부가 났다면 break
                if(arr[j][i] == 0) continue;

                //결과 출력
                result = check(i, j);
                if(result){
                    System.out.println(arr[j][i]);
                    System.out.println(++j + " " + ++i);
                    break Loop1;
                }
            }
         }
         if(!result) System.out.print(0);
        
    }
     // 현재돌이 조건을 만족하는지 확인
    public static boolean check(int x, int y){
        boolean flag = false;

        //반복문 : 3가지 경우에 대한 탐색 - 가로, 세로, 대각선
        Loop1:
        for(int i = 0; i<4; i++){
            int a = x-Case[i][0];
            int b = y-Case[i][1];
            //육목 확인을 위해 이전돌 확인
            if(a>=0 && b>=0 && a<19 && b<19 && arr[b][a] == arr[y][x]) {
                continue; 
            }
            //반복문 : 6번째 돌까지 확인
            int count = 5;
            for(int j=1; j<6; j++){
                //확인 할 돌의 인덱스 구하기
                int nowX = x + j*Case[i][0];
                int nowY = y + j*Case[i][1];

                //인덱스를 초과하는 경우
                if(nowX>=19 || nowY>=19 || nowX<0 || nowY<0) {
                    if(j==5) break;
                    count-=1;
                    break;
                }
                //if : 5번째 미만의 돌이고, 다른 돌이면
                if(j < 5 && arr[y][x] != arr[nowY][nowX]) count-=1;
                //else if : 5번째 이상의 돌이고, 같은 돌이면
                else if(j==5 && arr[y][x] == arr[nowY][nowX]) count-=1;
            }
            //조건을 만족하는 경우 종료
            if(count == 5){
                flag = true;
                break Loop1; 
            } 
        }
        return flag;
        
    }
}